Although I don’t know Racket
, I hope the following few comments might help a bit:
(reverse-function (simple-reverse (…))
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?
In 2 places you have something similar to
(cons (… first L) (… rest L))
so the order of the top level elements does not change.
Why exactly do you want to derive reverse-function
, 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.
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.