deep-reverse for scheme

Question

When entering the list of ((1 2) (3 4)), I want to reverse it, but not so it's ((3 4) (1 2)), which is what reverse does, so I'm trying to write a deep-reverse procedure:

(define (deep-reverse l)
  (cond ((null? l) nil)
        (not (pair? (car l)) l)
        (else (append (deep-reverse (cdr l)) (list (car l))))))

but it just throws back ((1 2) (3 4)). What's wrong and how do I get this to work?

Answer 1

A good start is the reverse procedure that works for a list. Then modify it to recursively apply to each car of the list:

(define (reverse x)
  (define (go items tail)
    (if (null? items) tail
        (go (cdr items) (cons (car items) tail))))
  (go x ()))

(define (deep-reverse x)
  (define (go items tail)
    (cond ((null? items) tail)
          ((not (pair? items)) items)
          (else (go (cdr items) (cons (go (car items) ()) tail)))))
  (go x ()))

An application of deep-reverse would be:

    (define x (list (list 1 (list 2 3) 4) 5 6 (list 7 8) 9 10)) (display x) (deep-reverse x)

   ((1 (2 3) 4) 5 6 (7 8) 9 10)
=> (10 9 (8 7) 6 5 (4 (3 2) 1))

Answer 2

Try:

(define (deep-reverse l) (map reverse l))

The above is the simplest possible answer; a real answer depends on exactly what you expect deep-reverse to do. See my comment to your question.

If you want everything, all the way down:

(define (deep-reverse l)
  (if (list? l)
      (reverse (map deep-reverse l))
      l))

Here is how it works (correctly):

> (deep-reverse '(1 2 ((3.1 3.2) (4) "abc")))
(("abc" (4) (3.2 3.1)) 2 1)

Answer 3

You have to also deep reverse the car in the code. Otherwise you are not deep reversing the front-most part of the list.

(define (deep-reverse l)
  (cond ((null? l) nil)
        (not (pair? (car l)) l)
        (else (append (deep-reverse (cdr l)) (list (deep-reverse (car l)))))))