Skip to content

Instantly share code, notes, and snippets.

@ftrain

ftrain/fold-and-spindle.rkt

Forked from jackrusher/fold-and-spindle.clj
Last active August 29, 2015 14:07
Show Gist options
  • Save ftrain/f87af30b64b997497b65 to your computer and use it in GitHub Desktop.
Save ftrain/f87af30b64b997497b65 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. @jackrusher jackrusher created this gist Sep 26, 2014.
    65 changes: 65 additions & 0 deletions fold-and-spindle.rkt
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,65 @@
    ;; 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))