How to Reverse a List?

How to Reverse a List?

What is the function to 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.

Answer by trix for How to Reverse a List?

(define (reverse1 l)    (if (null? l)       nil       (append (reverse1 (cdr l)) (list (car l)))    )  )  

Explanation:

Rules:
1. If list is empty, then reverse list is also empty
2. else behind reverse tail of the list add first element of the list

Look at at this code this way:

reverse1 is name of the function, l is parameter
if list is empty then reverse is also empty else call reverse1 function with (cdr l) which is tail of list and append that to first alement (car l) that you make as a list

in your example (pseudo cod):

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)  

Answer by Theo Belaire for How to Reverse a List?

(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)  

Answer by Anton Holmberg for How to Reverse a List?

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

Answer by Rajesh Bhat for How to Reverse a List?

I used a code similar to insert sort

(define deep-rev-list    (lambda (l)       (cond ((null? l) (quote ()))             ((atom? (car l))               (swap-till-end (carl) (deep-rev-list (cdr l))))             (else               (swap-till-end (deep-rev-list (car l)) (deep-rev-list (cdr l)))))))      (define swap-till-end     (lambda (elm lst)        (cond ((null? lst) (cons elm '()))              (else                 (cons (car lst) (swap-till-end elm (cdr lst)))))))    (define atom?    (lambda (x)      (and (not (null? x)) (not (pair? x)))))  

I am reproducing it from memory. There may be some errors. Will correct the code if thats the case. But the technique used is similar to the commandments for nested lists given in THe Little Schemer :). I checked it in DrRacket

(deep-rev-list '((1 2) (3) ((4 5)))) returns (((5 4)) (3) (2 1))

Answer by E 4 6 for How to Reverse a List?

You could simply reverse the elements in a list using foldr:

(foldr (lambda (a r) (append r (list a))) empty lst)  

Answer by fpmora for How to Reverse a List?

This is a reverse function in Racket which I like much better that 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)  

Answer by fabior for How to Reverse a List?

My solution:

(define (rvrs ls)    (if (null? ls)      empty      (append (rvrs (cdr ls)) (cons (car ls) empty))))  

Fatal error: Call to a member function getElementsByTagName() on a non-object in D:\XAMPP INSTALLASTION\xampp\htdocs\endunpratama9i\www-stackoverflow-info-proses.php on line 72