SICP Exercise 2.39

sicp

Question

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
   (λ (x y) ⟨??⟩) nil sequence))

(define (reverse sequence)
  (fold-left
   (λ (x y) ⟨??⟩) nil sequence))

Answer

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

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

Let’s test it:

(define x (list 1 2 3 4 5))
(reverse-1 x)
(reverse-2 x)

Results:

(5 4 3 2 1)
(5 4 3 2 1)