SICP - exercise 2.27 - reversing elements of a list and sublists

Question

From SICP

Exercise 2.27: Modify your deep-reverse procedure of Exercise 2.18 to produce a deep-deep-reverse procedure that takes a list as argument and returns as its value the list with its elements deep-reversed and with all sublists deep-deep-reversed as well. For example,

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

Please review my code.

(define (deep-deep-reverse lst)
 (cond ((null? lst) '())
 ((list? lst) (append (deep-deep-reverse (cdr lst)) (list (deep-deep-reverse (car lst)))))
 (else lst)))

I spent an hour doing this, and I am actually extremely surprise on how small this code is in the end. How can I improve this code? Perhaps make it faster?

Answer 1

If you actually indented it that way please use an editor that does automatically - usually the individual cases of the cond should align, e.g. like so:

(define (deep-deep-reverse lst)
 (cond
 ((null? lst) '())
 ((list? lst) (append (deep-deep-reverse (cdr lst))
 (list (deep-deep-reverse (car lst)))))
 (else lst)))

The function looks good. For clarity it might make sense to move the middle case to the end, but it's not like that changes much.

However consider that append used in this way is quite expensive because it repeatedly recreates a "long" list (from the cdr recursion) to stick the "short" list (from the car part) at the end.

(As an exercise for the reader) you can use an accumulator instead to avoid append completely (instead cons is enough). The function would look pretty similar:

(define (deep-deep-reverse2 lst)
 (define (aux lst acc)
 ...)
 (aux lst '()))

• lightning_missile: if cons sticks two lists together, it's constant time, right?
• ferada: The cons is constant sure, the whole function definitely not.

Answer 2

As noted above append gets expensive, with time and memory constraints liners to the size of the first argument. Actually recurring on each cdr of the list makes the overall function n^2 when the input is a list of lists.

The other thing to keep in mind is that list? also takes time linear time to complete. (resulting in another n^2 time constraint.) Alternatively pair? runs in constant time but doesn't protect/guard againstimproper list. (however when you are worried about improper input you should just go ahead and check it at the beginning of a function. )

You can reverse a list by folding cons over it as well.

(define (deep-deep-reverse3 x)
 (fold (lambda (x acc) 
 (cons (if (pair? x)
 (deep-deep-reverse3 x)
 x)
 acc))
 '()
 x))

• lightning_missile: fold is nice, but I don't think I should use it at this time since the book doesn't introduce it at this chapter.