A few words on fold for a friend who had just read http://www.cs.nott.ac.uk/~gmh/fold.pdf

fold-and-spindle.clj

;; simplest fold definition
(defn fold [f init l]
  (if (empty? l) init (fold f (f init (first l)) (rest 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 (fn [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 concat '() '[[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 (fn [a x]
        (cons (str (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 more clear:
 
;; partition a list into evens and odds using fold
(fold (fn [a x]
        (if (even? x)
          (list (cons x (first a)) (second a))
          (list (first a) (cons x (second 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 fn passed to fold above
(defn even-odd [out l]
  (if (empty? l) out
      (even-odd (let [x (first l)]
                  (if (even? x)
                      (list (cons x (first out)) (second out))
                      (list (first out) (cons x (second out)))))
                (rest l))))
 
(even-odd '(() ()) '[1 2 3 4 5 6 7 8 9])
;; => ((8 6 4 2) (9 7 5 3 1))

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))

In the Platonic tradition, this is True, and Beautiful, and encourages the Good. Vielen Dank!