<< Previous exercise (2.26) | Index | Next exercise (2.28) >>
A solution that uses reverse to do the work:
(define (deep-reverse t)
(if (pair? t)
(reverse (map deep-reverse t))
t))
Another solution without append
(define (deep-reverse items)
(define (iter items result)
(if (null? items)
result
(if (pair? (car items))
(let ((x (iter (car items) ())))
(iter (cdr items) (cons x result)))
(iter (cdr items) (cons (car items) result)))))
(iter items ()))
Solution that is a simple modification of reverse
(define (deep-reverse tree) (define (iter t result) (cond ((null? t) result) ((not (pair? (car t))) (iter (cdr t) (cons (car t) result))) (else (iter (cdr t) (cons (deep-reverse (car t)) result))))) (iter tree '())) #| > (deep-reverse '((1 2) (3 4))) '((4 3) (2 1)) > (deep-reverse '(1 2 (3 4) 5 (6 (7 8) 9) 10)) '(10 (9 (8 7) 6) 5 (4 3) 2 1) > |# >>>
there is another solution. it may be simpler.
(define (deep-reverse li)
(cond ((null? li) '())
((not (pair? li)) li)
(else (append (deep-reverse (cdr li))
(list (deep-reverse (car li)))))))
Took me a while to implement it without append and reverse.
(define (deep-reverse L) (define (rev L R) (cond ((null? L) R) ((not (pair? (car L))) (rev (cdr L) (cons (car L) R))) (else (rev (cdr L) (cons (rev (car L) '()) R))))) (rev L '())) (define x '((1 2) (3 4))) (deep-reverse x) ;; ((4 3) (2 1))
Solution with no use of append. Would be nice to have a full iterative process, but this problem is naturally recursive.
(define (deep-reverse l) (define (update-result result picked) (cons (if (pair? picked) (deep-reverse picked) picked) ;; recursive process result)) (define (iter source result) (if (null? source) result (iter (cdr source) (update-result result (car source))))) (iter l '())) ;; testing (deep-reverse '(1 2 (a b c (d1 d2 d3)) 4)) ;; returns '(4 ((d3 d2 d1) c b a) 2 1)
My solution which is very similar to the original.
(define (deep-reverse items) (define (try-deep item) (if (not (list? item)) item (iter item '()))) (define (iter old new) (if (null? old) new (iter (cdr old) (cons (try-deep (car old)) new)))) (iter items '())) ;; Testing (define x (list (list 1 2) (list 3 (list 4 5)) (list (list 2 3) 3))) ;; ((1 2) (3 (4 5)) ((2 3) 3)) (deep-reverse x) ;; ((3 (3 2)) ((5 4) 3) (2 1))
I though I'll found my version. Very close to some version here tough, but using map for clarity. It looks like it is working. May I be wrong somewhere?
(define (deep-reverse tree) (cond ((null? tree) nil) ((not (pair? tree)) tree) (else (map deep-reverse (reverse tree))))) (display (deep-reverse (list (list 1 2) (list 3 4)))) (newline) (display (deep-reverse (list (list 1 (list 5 6)) (list 3 4)))) (newline)
The most briefly solution
This solution only works with list of lists
(define (deep-reverse l)
(reverse (map reverse l)))
This solution doesn't require to check for the end of list.
(define (deep-reverse lst) (if (not (pair? lst)) lst (append (deep-reverse (cdr lst)) (list (deep-reverse (car lst)))))) ;;Testing (define x (list (list 1 2) (list 3 (list 4 (list 5 6 7) (list 8 9 10) 11)))) (deep-reverse (deep-reverse x)) ;; ((1 2) (3 (4 (5 6 7) (8 9 10) 11)))
(define (reverse item) (define (reverse-iter item result) (if (null? item) result (reverse-iter (cdr item) (cons (car item) result)))) (reverse-iter item nil)) (define (deep-reverse item) (define (deep-reverse-iter item result) (cond ((null? item) result) ((pair? (car item)) (deep-reverse-iter (cdr item) (cons (deep-reverse (car item)) result))) (else (deep-reverse-iter (cdr item) (cons (car item) result))))) (deep-reverse-iter item nil)) ;;Testing > (define x (list (list 1 2) (list 3 4))) > x (mcons (mcons 1 (mcons 2 '())) (mcons (mcons 3 (mcons 4 '())) '())) > (reverse x) (mcons (mcons 3 (mcons 4 '())) (mcons (mcons 1 (mcons 2 '())) '())) > (deep-reverse x) (mcons (mcons 4 (mcons 3 '())) (mcons (mcons 2 (mcons 1 '())) '())) > (deep-reverse (list 1 2 3)) (mcons 3 (mcons 2 (mcons 1 '()))) > (deep-reverse (list (list 1 2 3))) (mcons (mcons 3 (mcons 2 (mcons 1 '()))) '())
My first try: this is the same solution as joshwarrior's, except that the last two of cond's operands are reversed.
(define (deep-reverse l)
(define (rev l res)
(cond ((null? l) res)
((not (pair? (car l))) (rev (cdr l)
(cons (car l)
res)))
(else (rev (cdr l)
(cons (rev (car l)
'())
res)))))
(rev l '()))
Then I realized that car'ing before pair? was unnecessary, and here's my final answer.
(define (deep-reverse l)
(define (rev l res)
(cond ((null? l) res)
((not (pair? l)) l)
(else (rev (cdr l)
(cons (rev (car l)
'())
res)))))
(rev l '()))
I think this is better in terms of simplicity. This solution is also efficient because it does not use append or any operation that travels down the intermediate list from its head every time the function is called.
I think the solution can be much shorter by using map and list?.
(define (deep-reverse x)
(if (list? x)
(reverse (map deep-reverse x))
x))
This method is a very slight and (in my opinion) intuitive alteration of the reverse procedure. Instead of cons'ing the car of z to result (as in the original reverse procedure), the reverse of car of z is cons'ed to the result.
(define (deep-reverse items)
(define (iter-reverse z result)
(cond ((null? z) result)
((not (pair? z)) z)
(else (iter-reverse (cdr z) (cons (iter-reverse (car z) '()) result)))
)
)
(iter-reverse items '())
)
I felt that this solution was very 'conforming' to the spirit of doing things the Scheme way, and added minimum complexity over the vanilla version of reverse, and therefore might be a useful addition here
My first contribution to this wiki
(define (deep-reverse l) (define atom? (lambda (x) (and (not (pair? x)) (not (null? x))))) (define (reverse l) (if (null? (cdr l)) l (append (reverse (cdr l)) (list (car l))))) (cond ((null? l) nil) ((pair? (car l)) (append (deep-reverse (cdr l)) (list (deep-reverse (car l))))) ((atom? (car l)) (append (deep-reverse (cdr l)) (list (car l)))) (else (reverse l)))) (deep-reverse '(13 14 (1 2 3) ((3 4) (1 2)) (6 (7 8 9) (7))))
results in
(((7) (9 8 7) 6) ((2 1) (4 3)) (3 2 1) 14 13)
(first-timer here)
I think zerol's solution wins the cake for simplicity, readability, clarity AND application of newly learned material.
But here is mine, as it is somewhat different from the others:
(define (deep-reverse items)
(if (pair? items)
(reverse (cons (deep-reverse (car items))
(reverse (deep-reverse (cdr items)))))
items))
I think using list? as condition is better than pair? since list? is strict thant pair? and the element of list could be just pair but not list. Consider a case like (list (cons 1 2) (cons 3 4)). Of course, pair? is enough for this execise.
Review history comments:
jz: first 2 are iterative implementation of the latter 2 where the last combines (null? lst) and else into one x.
"A solution that uses reverse to do the work:": most straightforward to translate book "the list with its ele-ments reversed and with all sublists deep-reversed as well". yves's is same as this but calls reverse first. Lambdalef's is similar as it says. zerol's is same but uses list? (difference here from pair? see the following).
---
shyam's, varoun's, Daniel-Amariei's, atrika's, adam's (but use list? which in the context here will return #t for '(). This have no difference for (car old) since that can't be '() in the context here.), joshwarrior's are same as jz's first two.
"Then I realized that car'ing before pair? was unnecessary" (Also see jz's implementation of sicp-ex-2.30): it delays manipulating the case when (car l) is one number to (not (pair? l)) with one more recursion. tf3's (with explanation. TODO I don't know what he means "doing things the Scheme way") is same as ybsh's 2nd.
chessweb's is same but (atom? (car l)) may be better to be else since (car l) can't be nil here and (not (pair? x)) is already implied by that this case follows (pair? (car l)). So (else (reverse l)) is also redundant. This is as chessweb says.
---
meteorgan's, DeepDolphin's are same as jz's last implementation. rwitak's is similar but uses one different order of cons and so we need also use (reverse (deep-reverse (cdr items))).
---
My implementation based on count-leaves before reading this wiki. Here I think of the all-leaf list is one base case:
(define (deep-reverse lst) (cond ((not (pair? lst)) lst) ((= (count-leaves lst) (length lst)) (reverse lst)) (else (append (deep-reverse (cdr lst)) (list (deep-reverse (car lst))))))) (define x (list (list 1 2) (list 3 4))) (assert (equal? '((4 3) (2 1)) (deep-reverse x))) (define x (list (list 1 2) (list 3 (list 4 (list 4 5))))) (assert (equal? '((((5 4) 4) 3) (2 1)) (deep-reverse x))) (assert (equal? (list 3 2 1) (deep-reverse (list 1 2 3))))
although this implementation is a bit redundant compared with jz's last implementation.
Here's Eli Bendersky's code, translated into Scheme. It's pretty sharp, and better than my own since it's more concise:
This works for me:
(define (deep-reverse x) (if (pair? x) (append (deep-reverse (cdr x)) (list (deep-reverse (car x)))) x))