SICP Exercise 2.27: Reversing nested lists

"Life is all about sharing. If we are good at something, pass it on." - Mary Berry

SICP Exercise 2.27: Reversing nested lists

2021-10-12

Exercise 2.27: Modify your reverse procedure of exercise 2.18 to produce a deep-reverse procedure that takes a list as argument and returns as its value the list with its elements reversed and with all sublists deep-reversed as well. For example,
 1(define x (list (list 1 2) (list 3 4)))
 2
 3x
 4((1 2) (3 4))
 5
 6(reverse x)
 7((3 4) (1 2))
 8
 9(deep-reverse x)
10((4 3) (2 1))

First, look at my reverse procedure:

 1#lang racket/base
 2(require racket/trace)
 3
 4(define (reverse items)
 5    (iter items null))
 6
 7(define (iter remaining result)
 8    (trace iter)
 9    (if (null? remaining)
10        result
11        (iter (cdr remaining) (cons (car remaining) result))))
12
13(trace reverse)
14(reverse (list (list 1 2) (list 3 4)))

1$ racket 2.18-reverse-list.rkt
2>(reverse '((1 2) (3 4)))
3>(iter '((3 4)) '((1 2)))
4>(iter '() '((3 4) (1 2)))
5<'((3 4) (1 2))
6'((3 4) (1 2))

The reverse procedure just reverses the order of the top-level list.

To implement deep-reverse, we also need to reverse the order of the nested lists:

Same as reverse, return result if the remaining is null
Check the first item of the remaining:
- If it is a pair: call deep-reverse
- If not: do the same as before

Here’s the code:

 1#lang racket/base
 2(require racket/trace)
 3
 4(define (deep-reverse items)
 5    (iter items null))
 6
 7(define (iter remaining result)
 8    (trace iter)
 9    (cond ((null? remaining) result)
10        ((pair? (car remaining))
11            (iter (cdr remaining) (cons (deep-reverse (car remaining)) result)))
12        (else
13            (iter (cdr remaining) (cons (car remaining) result)))))
14
15(trace deep-reverse)
16(deep-reverse (list (list 1 2) (list 3 4)))

Test:

 1$ racket 2.27-deep-reverse.rkt
 2>(deep-reverse '((1 2) (3 4)))
 3> (deep-reverse '(1 2))
 4> (iter '(1 2) '())
 5> (iter '(2) '(1))
 6> (iter '() '(2 1))
 7< '(2 1)
 8>(iter '((3 4)) '((2 1)))
 9> (deep-reverse '(3 4))
10> (iter '(3 4) '())
11> (iter '(4) '(3))
12> (iter '() '(4 3))
13< '(4 3)
14>(iter '() '((4 3) (2 1)))
15<'((4 3) (2 1))
16'((4 3) (2 1))

Tags: sicp scheme

Edit on GitHub