## Folds

### February 2, 2018

Here they are:

(define (foldr f a xs) (if (null? xs) a (f (car xs) (foldr f a (cdr xs)))))

(define (foldl f a xs) (if (null? xs) a (foldl f (f a (car xs)) (cdr xs))))

(define (foldr1 f xs) (if (null? (cdr xs)) (car xs) (f (car xs) (foldr1 f (cdr xs)))))

(define (foldl1 f xs) (foldl f (car xs) (cdr xs)))

(define (scan f a xs) (define (scanx f a xs) (if (null? xs) xs (scan f (f a (car xs)) (cdr xs)))) (cons a (scanx f a xs)))

`Foldr`

and `foldl`

are the obvious recursive definitions.`Foldl1`

simply extracts the first item from the input list and calls `foldl`

. Be sure to examine closely the local function and recursion of `scan`

.

By the way, it is possible to implement `foldl`

in terms of `foldr`

:

(define (foldl-from-foldr f a xs) ((foldr (lambda (item accum) (lambda (x) (accum (f item x)))) (lambda (x) x) xs) a))

Here, we accumulate *lambda*s that contain delayed computations, rather than values, and at the end the entire chain of *lambda*s is applied to the base value to ignite the computation; the initial *lambda* is the identity procedure. This works the same way as normal `foldl`

:

> (foldl-from-foldr + 0 '(1 2 3 4)) 10 > (foldl-from-foldr cons '() '(1 2 3 4)) (4 3 2 1)

It’s also possible to write foldr in terms of foldl, but it’s messy and has limitations; see https://wiki.haskell.org/Foldl_as_foldr if you are interested.

Here is the complete list of examples from the first page, including definitions of `plusone`

and `snoc`

:

> (foldr + 0 '(1 2 3 4)) 10 > (foldl + 0 '(1 2 3 4)) 10 > (foldr cons '() '(1 2 3 4)) (1 2 3 4) > (foldl cons '() '(1 2 3 4)) ((((() . 1) . 2) . 3) . 4) > (define (plusone _ n) (+ n 1)) > (foldr plusone 0 '(1 2 3 4)) ; length 4 > (define (snoc xs x) (cons x xs)) > (foldl snoc '() '(1 2 3 4)) ; reverse (4 3 2 1) > (foldr1 max '(1 2 3 4)) 4 > (foldl1 max '(1 2 3 4)) 4 > (scan + 0 '(1 2 3 4)) (0 1 3 6 10) > (map reverse (scan snoc '() '(1 2 3 4))) (() (1) (1 2) (1 2 3) (1 2 3 4))

You can run the program at https://ideone.com/lgKnS1.

Here’s a fully tail-recursive solution in standard R7RS Scheme.

Here’s a solution in C.

Output:

Folds make sense for any algebraic data type, so we can fold over trees, for example:

Implementation of the various derived folds is left as an exercise.

Here’s one that takes a two-argument function:

Here’s some Haskell…