fold-and-spindle.rkt

;; simplest fold definition
(define (fold f init l)
  (if (null? l) init (fold f (f init (car l)) (cdr l))))

;; by this time you are almost certainly comfortable with signatures like:

;; Int -> Int
(fold + 0 '[1 2 3 4 5])
;; => 15

;; ... which is actually isomorphic to:

(apply + '[1 2 3 4 5])
;; => 15

;; let's do something more interesting, starting with a structure
;; preserving fold for nested lists:

;; [[Int]] -> [[Int]]
(fold (lambda (a x)
        (cons (list (apply + x)) a)) '() '[[1 2 3] [4 5 6] [7 8 9]])
;; => ((24) (15) (6))

;; ok, how about structure modification?

;; [[Int]] -> [Int]
(fold append '() '[[1 2 3] [4 5 6] [7 8 9]])
;; => (1 2 3 4 5 6 7 8 9)

;; structure and type modification?

;; [[Int]] -> [String]
(fold (lambda (a x)
        (cons (number->string (apply + x)) a)) '() '[[1 2 3] [4 5 6] [7 8 9]])
;; => ("24" "15" "6")

;; none of which shows you the true universiality of fold, but I think
;; a grouping function makes it clear:

;; partition a list into evens and odds using fold
(fold (lambda (a x)
        (if (even? x)
            (list (cons x (car a)) (cadr a))
            (list (car a) (cons x (cadr a)))))
      '(() ()) '[1 2 3 4 5 6 7 8 9])
;; => ((8 6 4 2) (9 7 5 3 1))

;; ... as you can see, the accumulator ('a') here is a list containing
;; multiple items (in this case, two lists to hold even and odd
;; values). This technique allows one to use an arbitrary set of
;; arguments with a reducing function, making it possible to represent
;; the entire family of recurive functions.

;; compare to a hand-written even-odd and note that it contains both
;; fold and the lambda passed to fold above
(define (even-odd out l)
  (if (null? l) out
      (even-odd (let [(x (car l))]
                  (if (even? x)
                      (list (cons x (car out)) (cadr out))
                      (list (car out) (cons x (cadr out)))))
                (cdr l))))

(even-odd '(() ()) '[1 2 3 4 5 6 7 8 9])
;; => ((8 6 4 2) (9 7 5 3 1))