Learn Higher Order Functions - nomssi/abap_scheme GitHub Wiki
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