Exercise 2.18 asks us to define a procedure
reversethat takes a list as its argument and returns a list with the same elements in reverse order.
We'll be using the
appendprocedure given in the text which takes two lists and appends the second list to the end of the first:
(define (append list1 list2)
(if (null? list1)
(cons (car list1) (append (cdr list1) list2))))
We can reverse a list by appending the
carof the list to the reverse of the
cdrof the list. (See how easy it is to start thinking in Scheme?) In other words, we just move the first item to the end of the list after reversing the remaining items. This means
reversewill make a recursive call to itself, so we also need a base case to make the recursion stop. We can just stop when we reach an empty list.
(define (reverse items)
(if (null? items)
(append (reverse (cdr items)) (list (car items)))))
Once again, we can test it out with a few example lists from the text.
> (reverse (list 1 2 3 4))
(4 3 2 1)
> (reverse (list 1 4 9 16 25))
(25 16 9 4 1)
> (reverse (list 1 3 5 7))
(7 5 3 1)
> (reverse (list 23 72 149 34))
(34 149 72 23)
For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.