Folding is Quite General

The fold function is surprisingly general, and can be used to write many other functions. As a reminder, here is the fold function we’re using:

(define fold
    (lambda (fn empty-val lst)
        (cond
            ((null? lst)  ;; base case
                empty-val)
            (else         ;; recursive case
                (fn (car lst) (fold fn empty-val (cdr lst))))
        )
    )
)

This is a right fold because it starts combining elements at the right end of the list and works towards the left ed.

Mapping

If lst = (a1 a2 ... an), then (map f lst) returns ((f a1) (f a2) ... (f an)), i.e. f is applied to every element of lst.

While map is a standard function built-into Scheme, it is instructive to implement our own version.

First, here is an implementation that uses recursion in a straightforward way:

(define my-map-basic
    (lambda (fn lst)
        (cond
            ((null? lst)
                '())
            (else
                (cons (fn (car lst))
                      (my-map-basic fn (cdr lst)))
            )
        )
    )
)

We can also implement map using our right fold function like this:

(define my-map-fold
    (lambda (fn lst)
        (fold (lambda (a rest) (cons (fn a) rest))
              ()
              lst)
    )
)

This version consists of a single call to fold, and has no recursive calls. The trick is in the function passed to fold:

(lambda (a rest) (cons (fn a) rest))

Like all functions passed to fold, it takes two inputs. The first input is the next item of lst to process, and the second input is the part of the list that has already had fn applied to it. The function applies fn to a, and then uses cons to put it onto the start of the other already- processed list.

How might you come up with this particular implementation? One way is to consider the consed-out form of a list. For example, we can write (1 2 3) like this:

(cons 1 (cons 2 (cons 3 ())))

The call (fold f empty-val lst) is this:

(f 1 (f 2 (f 3 empty-val)))

So fold can be seen as replacing each occurrence of cons with f, and the () at the end with empty-val. That means (fold cons () lst) returns lst without any change. But for map, we do want to make a change: we want to first apply f to the element before consing it onto the list. So intead of cons, we use the function (lambda (a rest) (cons (f a) rest)).

Filtering

We can also implement the standard scheme filter function. The call (filter fn? lst) returns a list that is the same as lst except all elements x in lst that cause (fn? x) to return true are removed.

Our version will be named keep-if. Here is a basic recursive implementation:

(define keep-if
    (lambda (fn? lst)
        (cond
            ((null? lst)
                '())
            ((fn? (car lst))
                (cons (car lst)
                      (keep-if fn? (cdr lst))))
            (else
                (keep-if fn? (cdr lst)))
        )
    )
)

And now here’s a version that uses a single call to fold and no recursion:

(define keep-if-fold
    (lambda (fn? lst)
        (fold (lambda (a rest)
                  (if (fn? a)
                      (cons a rest)
                      rest)
              )
              ()
              lst
        )
    )
)

As with my-map-fold, the trick is in the function passed to fold. It takes two inputs: a, the next item to be processed, and rest, the rest of the already-processed list. So the function calls (fn? a) to see if a satisfies fn?. If it does, then a is consed on to the rest of the list; if it doesn’t, then the rest of the list is returned without change, which effectively removes a.

It’s also interesting to note that the code inside the function passed to fold is a little simpler than the corresponding code in the recursive keep-if. Instead of (car lst) and (cdr lst) we write a and rest.

Exercise

1. Write of version of the standard length function that uses fold, and no recursion, to calculate the length of a list.

2. Consider the (double-up lst) function, which repeats each element of a list:

    > (double-up '(1 2 a cat))
   (1 1 2 2 a a cat cat)
   

Impement two versions of double-up: one that uses cond (or if) and recursion, and another that uses a single call to fold and no recursion.