"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

Categories:

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:

Related Posts: