SICP Exercise 2.27: Reversing nested lists
2021-10-12
Categories: Programming
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
, returnresult
if theremaining
is null - Check the first item of the remaining:
- If it is a pair: call
deep-reverse
- If not: do the same as before
- If it is a pair: call
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))
Related Posts:
- SICP Exercise 2.77: expected a procedure that can be applied to arguments, given #f
- SICP Exercise 2.43: Eight queens: interchange the order of the nested mappings
- SICP Exercise 2.42: Eight queens puzzle
- SICP Exercise 2.41: Triple sum
- SICP Exercise 2.35: Counting leaves of a tree