Higher-order Recursive Design

Summary

In this reading, we apply recursive design to higher-order procedures, revisiting the big three list functions: map, filter, and fold.

After writing many recursive functions you may have noticed general patterns in the code you wrote. For example, calculating the length of a list:

(define length
  (lambda (lst)
    (if (null? lst)
        0
        (+ 1 (length (cdr lst))))))

Looks awfully similar to summing the elements of a list:

(define sum
  (lambda (lst)
    (if (null? lst)
        0
        (else (+ (car lst) (sum cdr lst))))))

Which, with a little bit of eye-contortion, is similar to appending lists:

(define append
  (lambda (l1 l2)
    (if (null? l1)
        l2
        (let ([head (car l1)]
              [tail (cdr l1)])
          (cons head (append tail l2))))))

In all three cases:

• We perform a case analysis on list in question.
• In the base case, we return a value that is constant relative to the list we perform case analysis over: 0 and l2.
• In the recursive case, we apply a function (+ or cons) to a value dependent on the head value of the list (1 or x) and the result of recursively calling the function.

In the spirit of functions-as-abstractions, can we write a function that captures this generic behavior? This line of investigation leads us back to the big three list functions, map, filter, and reduce! We motivate the design of higher-order recursive functions by examining their implementation and discuss their limitations in more detail.

Map

Recall that (map f l) returns list l but with every element of l transformed by unary function f. For example, we can (map (section + <> 1) l) to increment all the elements of l by 1 or we can (map zero? l) to turn every element of l into a boolean denoting whether that element was zero.

How can we implement map? Let’s try writing out two functions (corresponding to those examples), inc-list-1 and list-zero?, using recursion and note the similarities.

(define inc-list-1
  (lambda (l)
    (if (null? l)
        null
	(cons (+ x 1) (inc-list-1 (cdr l))))))

(define list-zero?
  (lambda (l)
    (if (null? l)
         null
	 (cons (zero? x) (list-zeros? (cdr l))))))

We can see that the functions are very similar:

• In the base case, we return null because there are no elements to transform.
• In the recursive case, we apply our desired function (+ and zero?) to the head element and cons that onto the result of recursively processing the tail of the list.

We can use this recursive design to drive our implementation of map. We can also observe that the only difference in the two implementation is the function we apply to the head element. If we take one of the implementations and abstract away the applied function to an additional parameter, we also arrive at our desired function.

;;; (map f l) -> listof U?
;;; f : (-> T? U?)
;;; l : listof T?
;;;
;;; Returns list l but every element of l is transformed by function f.
(define map
  (lambda (f l)
    (if (null? l)
        null
	(cons (f (car l)) (map f (cdr l))))))

We have already seen and used map extensively as the backbone of our computational pipelines. Whenever we encounter a recursive function that is really just a map call, we should just use map instead. However, are there situations where we want to transform the elements of a list where we cannot not use map?

Let’s consider the problem of transforming a list of characters, presumed to be letters, into symbols denoting whether that character is a consonant ('c) or a vowel ('v). We can first write a function to test if an individual character is a vowel and then lift that to a list of characters with map.

(define vowel?
  (lambda (c)
    (or (equal? c #\a)
        (equal? c #\e)
        (equal? c #\i)
        (equal? c #\o)
        (equal? c #\u))))

(define list-vowel? (section map vowel? <>))

This seems straightforward enough to write. However, we forgot a pesky corner case: the letter ‘y’:

‘y’ is considered a vowel whenever it follows a consonant. Otherwise it is a consonant itself.

We can see more clearly now why map is now insufficient for perform this vowel? computation over a list of characters. We would need to extend vowel? with an extra argument—the previous letter in the sequence—in order to determine if an occurrence of ‘y’ is a vowel. However, map, by design, only takes functions of one argument!

In general, map operates on each of its elements individually. We say that map is non-contextual: it only “knows” one element at a time and is not “aware” of its prior processing or what is coming up next. If our transformation requires information about the elements surrounding the one in question, we either need to consider another approach, e.g., writing the recursive function by hand or generalizing map appropriately.

Filter

Recall that (filter f l) is like map except:

• We require that f is a function that takes an element of l and then produces a boolean.
• filter uses that boolean to determine whether to keep that element (#t) or drop that element (#f) from the list.

We’ll omit the implementation of filter here because it is very close to map and leave it as a self-check exercise below. However, filter inherits the same non-contextual limitations as map—filter can only decide whether to keep an element based on the current element and no other information. This means that filter cannot remove “all-but-one” of a particular element—it can’t “remember” whether it has previously kept an element yet!

Furthermore, filter must process all the elements of the list. We can’t short-circuit execution of filter because we have no way of specifying to filter when to stop execution. For example, we might want to remove just the first occurrence of a value from a list—filter cannot do this. In this situation, we would need to write a custom recursive function for this task.

Reduce

The reduce function is used to summarize the elements of a list. Unlike map and filter, this means that these functions must be contextual in nature: we have to pass information between successive elements in the computation. This is the accumulated result of the computation so far.

reduce was likely a bit arcane when we first encountered it several weeks ago. Recall that (reduce f l) took two arguments as input:

• A function f of two arguments (a binary function). The first argument is an element of l. The second argument is the result accumulated so far in the computation.
• A list l that reduce traverses in some order.

Here are some examples of reduce in action:

> (reduce + (list 1 2 3 4 5))
15
> (reduce * (list 1 2 3 4 5))
120

To get a better sense of what reduce is doing, let’s again try writing specialized recursive functions reduce-by-+ and reduce-by-* that reduce the list with + and *, respectively.

(define reduce-by-+
  (lambda (l)
    (cond [(null? l)
           (error "(reduce-by-+) received an empty list")]
	  [(null? (cdr l))
	   (car l)]
          [else
	   (+ (car l) (reduce-by-+ (cdr l)))])))

(define reduce-by-*
  (lambda (l)
    (cond [(null? l)
           (error "(reduce-by-*) received an empty list")]
          [(null? (cdr l))
	   (car l)]
	  [else
	   (* (car l) (reduce-by-* (cdr l)))])))

> (reduce-by-+ (list 1 2 3 4 5))
15
> (reduce-by-* (list 1 2 3 4 5))
120

We can see from our implementations that reduce repeatedly applies the binary function (+ or *) to the current element and the result of recursively processing the remainder of the list. With these concrete implementations, we can get more intuition about how reduce works:

    (reduce-by-+ (list 1 2 3 4 5))
--> (+ 1 (reduce-by-+ '(2 3 4 5)))
--> (+ 1 (+ 2 reduce-by-+ '(3 4 5)))
--> (+ 1 (+ 2 (+ 3 (reduce-by-+ '(4 5)))))
--> (+ 1 (+ 2 (+ 3 (+ 4 (reduce-by-+ '(5))))))
--> (+ 1 (+ 2 (+ 3 (+ 4 5))))
--> 15

And with this intuition and our two concrete implementations, we can derive the following recursive design for (reduce f l):

• (If the list is empty, we raise an error.)
• If the list contains 1 element, we return that element.
• Otherwise, the list contains at least 2 elements. We apply f to the head of the list and the result of recursively reducing the rest of the list.

And then turn this design into an implementation of reduce:

(define reduce
  (lambda (f l)
    (cond [(null? l)
           (error "(reduce) received an empty list")]
          [(null? (cdr l))
	   (car l)]
	  [else
	    (f (car l) (reduce f (cdr l)))])))

> (reduce + (list 1 2 3 4 5))
15
> (reduce * (list 1 2 3 4 5))
120

Self-Checks

Check 1: Implementing Filter (‡)

In our discussion of higher-order recursive functions, we elided the implementation of filter. Write (filter f l) based on the recursive design we described in the reading.