How can I reverse a list?
Solution 1
Use:
(define (reverse1 l)
(if (null? l)
nil
(append (reverse1 (cdr l)) (list (car l)))
)
)
Explanation:
Rules:
- If the list is empty, then the reverse list is also empty
- Else behind the reverse tail of the list, add the first element of the list
Look at this code this way:
reverse1
is name of the function and l is a parameter. If the list is empty then the reverse is also empty.
Else call the reverse1
function with (cdr l) which is the tail of the list and append that to the first alement (car l) that you make as a list.
In your example (pseudocode):
1st iteration
l=>(a (bcd)e)
car l => a
cdr l => (bcd)e
list(car l) =>(a)
------------------
reverse( cdr l)"+"(a)
------------------
2nd iteration
l=>((bcd)e)
car l => (bcd)
cdr l =>e
list(car l)=>(bcd)
--------------------
reverse(cdr l)"+"((bcd))+(a)
-----------------------
3rd iteration
l=>e
car l=> e
cdr l => nil
list (car l) =>(e)
-------------------------
(e (bcd)a)
Solution 2
(define (my-reverse ls)
(define (my-reverse-2 ls acc)
(if (null? ls)
acc
(my-reverse-2 (cdr ls) (cons (car ls) acc))))
(my-reverse-2 ls '()))
This uses an accumulator variable to reverse the list, taking the first element off the incoming list and consing it to the front of the accumulator. It hides the accumulator taking function and just exposes the function that takes a list, so the caller doesn't have to pass in the empty list. That's why I have my-reverse-2.
(my-reverse-2 '(a (b c d) e) '()); will call
(my-reverse-2 '((b c d) e) '(a)); which will call
(my-reverse-2 '(e) '((b c d) a)); which will call
(my-reverse-2 '() '(e (b c d) a)); which will return
'(e (b c d) a)
Because the last function call in my-reverse-2
is a call to my-reverse-2
, and the return value is passed right through (the return value of the first call is the return value of the second call, and so on) my-reverse-2
is tail optimized, which means it will not run out of room on the stack. So it is safe to call this with a list as long as you like.
If you want it to apply to nested lists use something like this:
(define (deep-reverse ls)
(define (deep-reverse-2 ls acc)
(if (null? ls)
acc
(if (list? (car ls))
(deep-reverse-2 (cdr ls) (cons (deep-reverse (car ls)) acc))
(deep-reverse-2 (cdr ls) (cons (car ls) acc)))))
(deep-reverse-2 ls '()))
This checks to see if the element is a list before adding it to the list, and if it is, reverses it first. Since it calls itself to revers the inner list, it can handle arbitrary nesting.
(deep-reverse '(a (b c d) e))
-> '(e (d c b) a)
which is in reverse alphabetical order, despite the fact that there is a nested list.
It evaluates as so:
(deep-reverse-2 '(a (b c d) e) '()); Which calls
(deep-reverse-2 '((b c d) e) '(a))
(deep-reverse-2 '(e) (cons (deep-reverse-2 '(b c d) '()) '(a)))
(deep-reverse-2 '(e) (cons (deep-reverse-2 '(c d) '(b)) '(a)))
(deep-reverse-2 '(e) (cons (deep-reverse-2 '(d) '(c b)) '(a)))
(deep-reverse-2 '(e) (cons '(d c b) '(a)))
(deep-reverse-2 '(e) '((d c b) a))
(deep-reverse-2 '() '(e (d c b) a))
'(e (d c b) a)
Solution 3
This is one way that you can make a reverse function that applies to nested lists:
(define (reverse-deep l)
(map (lambda (x) (if (list? x) (reverse-deep x) x)) (reverse l)))
Explanation in pseudo-code:
Start by reversing the list as you would normally do
Then for each element in the reversed list:
- If the element is a list itself: Apply the procedure recursively
- Else: Don't touch the element
Solution 4
You could simply reverse the elements in a list using foldr:
(foldr (lambda (a r) (append r (list a))) empty lst)
Solution 5
This is a reverse function in Racket which I like much better than Scheme.
It uses the match pattern matching function only.
(define/match (rev l)
[('()) '()]
[((list a ... b)) (cons b (rev a))])
> (rev '(a (b c d) e))
'(e (b c d) a)
Related videos on Youtube
安杰帅
Updated on July 06, 2021Comments
-
安杰帅 almost 3 years
What is the function to reverse a list in Scheme?
It needs to be able to handle nested lists. So that if you do something like
(reverse '(a (b c d) e))
you'll get(e (b c d) a)
as the output.How should I approach this problem? I'm not just looking for an answer, but something that will help me learn.
-
wowest about 13 yearsBetter answer: (define (rev1 lst) (foldl cons '() lst))
-
-
erjiang over 13 yearsNote that this answer is written in Common Lisp, which uses
nil
instead of'()
. -
okonomichiyaki over 13 years@erjiang that's not really true - while Common Lisp uses
nil
and Scheme doesn't, the function defined at the top of this answer is really Scheme, not Common Lisp. You would need to do something like(define nil '())
in order for it to work though. -
Puterdo Borato almost 11 yearsThis works for me perfectly with just one minor edit (return items instead of nil): (define (rev items) (if (null? items) items (append (rev (cdr items)) (list (car items))) ) ) I run this in Petite Chez (scheme.com)
-
Puterdo Borato almost 11 yearsAlso there is built-in (reverse) procedure that returns the same result.
-
Joshua Taylor over 8 yearsTo avoid the nil/empty list issue, since you already know that l is empty from (null? l),that case could just return l. That will work regardless of exactly what null? checks for.
-
Hugo Barauna about 8 yearsBe aware that this implementation may have performance problems. Take a look at this to see a better performant version of list reversing implementation: cs.sfu.ca/CourseCentral/310/pwfong/Lisp/2/tutorial2.html
-
Sylwester about 8 yearsThis uses O(n^2) time and O(n^2) space. Thus the longer the list gets the less likely you are ever going to get an answer before your patience go out or your memory runs out.
-
Peter Mortensen over 3 yearsWhat is "THe Little Schemer" and "DrRacket"? A book and an online tool, respectively?
-
Peter Mortensen over 3 yearsAn explanation would be in order. E.g., what is the idea? How is it different from previous answers?