#### [SOLVED] SICP - exercise 2.27 - reversing elements of a list and sublists

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))
``````

``````(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? #### @WorBlux 2016-01-06 02:31:14

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))
`````` #### @morbidCode 2016-01-06 06:58:16

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. 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 '()))
`````` #### @morbidCode 2016-01-06 07:11:15

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

### [SOLVED] Producing a deep-reverse procedure

• 2011-04-07 04:33:34
• jaresty
• 1011 View
• 0 Score