If you know Lisp/Scheme, I need assistance (specifically in Racket)

[kernan373]

Hey all,

I'm trying to write a function in Racket to reverse a list, including the lists within the list. The input should be one list and the output should be the reversed list.

I made a function that reverse a list's elements without going into the lists within the lists.
so
(simple-reverse (list 1 2 (list 'a 'b 'c) 3 4))
would return:
(list 4 3 (list 'a 'b 'c) 2 1)

Here's what I have so far of the function I want to make:


(define reverse-function
(lambda (L)
(cond
((empty? L) empty)
((list? (first L)) (cons (reverse-function (first L)) (reverse-function (rest L))))
(else (cons (first L) (reverse-function (simple-reverse (rest L)))))))

The output expected from input (list 1 2 3 (list 'a 'b 'c) 4 5) should be (list 5 4 (list 'c 'b 'a) 3 2 1). How do I go about doing this? what am I doing wrong?

[SaGS]

Although I don’t know Racket, I hope the following few comments might help a bit:

(A)
(reverse-function (simple-reverse (…))
If reverse-function did what it is supposed to do, and since simple-reverse also reverses the top level of the list, then the 2 function calls cancel each other from the point of view of the top level of the argument. Why do you apply one to the result of the other?

(B)
In 2 places you have something similar to
(cons (… first L) (… rest L))
so the order of the top level elements does not change.

(C)
Why exactly do you want to derive reverse-function from simple-reverse, as opposed to implementing the reversing from scratch?

Certainly this does not avoid iterating through all elements, because simple-reverse does not care about nested lists and while it processes a list you do not know there are such ones to handle them yourself. If you absolutely want to use simple-reverse (as in an assignment that explicitly requires this), you could:

Iterate through all top level elements of the list received as an argument.
Call your reverse-function recursively on each such element that is a list; the atoms are left unchanged.
Collect all these results (atoms + deep-reversed nested lists) into a list, in the original order. Note this list is almost what you want, except the top level is not yet reversed.
Apply simple-reverse to the list obtained in the previous step.

(D)
But if you have to iterate through all elements, at all levels, why bother with simple-reverse?

A small change to (C) allows you to get the result you want directly: while collecting the results in the 3rd step, put them in a list in reverse order. Then the 4th step isn’t necessary anymore, less memory is used (there’s no need to allocate the intermediary almost-fully-reversed list) and the reversing should be faster.

I’ve done the 2 in Lisp as an exercise, and the complexity is comparable. The difference came from making the ‘from scrach’ version to work with ‘improper lists’ (those who’s last cdr is not NIL, like (a b c . d)); the Lisp reverse function (which seems to correspond to your simple-reverse) does no work with such constructs, and I didn’t bother to implement a workaround in this case.