By morbidCode

2016-01-05 16:07:26 8 Comments


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

((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?


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

@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.

@ferada 2016-01-06 00:32:01

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)
   ((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?

@ferada 2016-01-06 17:00:04

The cons is constant sure, the whole function definitely not.

Related Questions

Sponsored Content

1 Answered Questions

[SOLVED] Church Numerals

1 Answered Questions

[SOLVED] SICP - exercise 1.11 - tree recursion

1 Answered Questions

1 Answered Questions

1 Answered Questions

[SOLVED] Replacing elements from a list and its sublists - part II

2 Answered Questions

[SOLVED] SICP - exercise 2.20 - same-parity

1 Answered Questions

[SOLVED] Replacing elements from a list and its sublists

1 Answered Questions

[SOLVED] Reversing a list without (append)

1 Answered Questions

[SOLVED] Producing a deep-reverse procedure

  • 2011-04-07 04:33:34
  • jaresty
  • 1011 View
  • 0 Score
  • 1 Answer
  • Tags:   lisp scheme sicp

2 Answered Questions

[SOLVED] Design a procedure to reverse a list

Sponsored Content