{{ message }}

Instantly share code, notes, and snippets.

jackrusher/fold-and-spindle.clj

Last active Aug 29, 2015
A few words on fold for a friend who had just read http://www.cs.nott.ac.uk/~gmh/fold.pdf
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 ;; 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))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 ;; 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 commented Sep 29, 2014

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