Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A few words on fold for a friend who had just read http://www.cs.nott.ac.uk/~gmh/fold.pdf
;; 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))
;; 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))
@limist
Copy link

limist commented Sep 29, 2014

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment