SICP Exercise 2.39: Folding Reverse

Complete the following definitions of reverse (exercise 2.18) in terms of fold-right and fold-left from exercise 2.38:

(define (reverse sequence)
  (fold-right (lambda (x y) <??>) nil sequence))
(define (reverse sequence)
  (fold-left (lambda (x y) <??>) nil sequence))

In both cases we start with the empty list, but, as we discussed in exercise 2.38 we process the elements in different orders: fold-left processes the elements in the list from first to last, while fold-right processes the elements in the list from last to first.

We're starting with the fold-right case first, so we're going to process the elements from last to first. This means that at any particular step in the process we're going to want to combine the results of reversing the later elements in sequence with the current element we're processing. For example, when we finally process the first element of the sequence we want to combine it with the results of reversing the remainder of the sequence. So the current element (x in the lambda expression) needs to go onto the tail of the results of reversing the later elements in the sequence. We know that we can't use cons to append a single item onto the end of a list... But we can use append to combine two lists. If we take the current element of the sequence and turn it into a single-item list then we can append that onto the end of the results of reversing the later elements in the sequence as follows:

(define (reverse sequence)
  (fold-right (lambda (x y) (append y (list x))) nil sequence))

And just to check that works:

> (reverse (list 1 2 3 4 5))
'(5 4 3 2 1)

The fold-left case is a bit easier. We're processing the elements from first to last, so we can simply cons each element onto the accumulated result sequence in turn. We cons the first element of sequence onto an empty list, giving a single item list. Then we cons the second element of sequence onto that, giving us a list of the first two items from sequence, but in reverse order. And we repeat that throughout the list to give us the reverse list:

(define (reverse sequence)
  (fold-left (lambda (x y) (cons y x)) nil sequence))

And again we check it works:

> (reverse (list 1 2 3 4 5))
'(5 4 3 2 1)