Learn Higher Order Functions

Fold

Fold Right

(define (fold-right f init seq)
    (if (null? seq)
        init
        (f (car seq)
         (fold-right f init (cdr seq)))))

Filter

(define (filter pred? lst)
    (fold-right (lambda (x y) (if (pred? x)
                                  (cons x y)
                                  y) )
                 '() lst))

(filter (lambda (n) (> n 4))
     '(1 2 3 4 5 7) )
=> ( 5 7 )

(filter odd? (list 1 2 3 4 5))
=> ( 1 3 5 ) 

Fold Left

(define (fold-left f init seq)
    (if (null? seq)
       init
       (fold-left f
                 (f init (car seq))
                 (cdr seq))))

Fold Left with accumulator

(define (fold-left op initial sequence)
  (define (iter result rest)
    (if (null? rest)
        result
        (iter (op result (car rest))
              (cdr rest))))
  (iter initial sequence))

Tests

(fold-left + 0 (list 1 2 3))
=> 6 
(fold-right / 1 (list 1 2 3))
=> 3/2
(fold-left / 1 (list 1 2 3))
=> 1/6
(fold-right list '() (list 1 2 3))
=>  ( 1 ( 2 ( 3 '() ) ) )
(fold-left list '() (list 1 2 3))
=>  ( ( ( '() 1 ) 2 ) 3 )

Map

(define (my-map f lst)
  (if (null? lst)
    '()
    (cons (f (car lst)) (my-map f (cdr lst)))))

(my-map (lambda (n) (+ n 3)) '(1 2 3 4 5) )
=> ( 4 5 6 7 8 )

Apply

(apply + (list 3 4))
  ==> 7

Fib

(define (fib n)
  (if (< n 2.)
    n
    (+ (fib (- n 1.))
       (fib (- n 2.)))))

(fib 3) = (fib 2) + (fib 1) = (fib 1) + (fib 0) + 1 = 1 + 0 + 1 => 2.0

(fib 35) time out

Fast Fibonacci

;;
;; Function: fast-fibonacci
;; ------------------------
;; Relies on the services of a helper function to generate the nth fibonacci number
;; much more quickly. The key observation here: the nth number is the Fibonacci 
;; sequence starting out 0, 1, 1, 2, 3, 5, 8 is the (n-1)th number in the Fibonacci-
;; like sequence starting out with 1, 1, 2, 3, 5, 8. 
;; The recursion basically slides down the sequence n or so times in order to 
;; compute the answer. As a result, the recursion is linear instead of binary,
;; and it runs as quickly as factorial does.
;;
(define (fast-fibonacci n)
(fast-fibonacci-helper n 0 1))
(define (fast-fibonacci-helper n base-0 base-1)
(cond ((zero? n) base-0)
((zero? (- n 1)) base-1)
(else (fast-fibonacci-helper (- n 1) base-1 (+ base-0 base-1)))))

Y Combinator

http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html

What is missing?

https://csl.name/post/lambda-macros-continuations/