reverse list - scheme

Question

I'm trying to reverse a list, here's my code:

(define (reverse list)
  (if (null? list) 
     list
      (list (reverse (cdr list)) (car list))))

so if i enter (reverse '(1 2 3 4)), I want it to come out as (4 3 2 1), but right now it's not giving me that. What am I doing wrong and how can I fix it?

Solution 1

The natural way to recur over a list is not the best way to solve this problem. Using append, as suggested in the accepted answer pointed by @lancery, is not a good idea either - and anyway if you're learning your way in Scheme it's best if you try to implement the solution yourself, I'll show you what to do, but first a tip - don't use list as a parameter name, that's a built-in procedure and you'd be overwriting it. Use other name, say, lst.

It's simpler to reverse a list by means of a helper procedure that accumulates the result of consing each element at the head of the result, this will have the effect of reversing the list - incidentally, the helper procedure is tail-recursive. Here's the general idea, fill-in the blanks:

(define (reverse lst)
  (<???> lst '()))                       ; call the helper procedure

(define (reverse-aux lst acc)
  (if <???>                              ; if the list is empty
      <???>                              ; return the accumulator
      (reverse-aux <???>                 ; advance the recursion over the list
                   (cons <???> <???>)))) ; cons current element with accumulator

Of course, in real-life you wouldn't implement reverse from scratch, there's a built-in procedure for that.

Solution 2

Tail recursive approach using a named let:

(define (reverse lst)
  (let loop ([lst lst] [lst-reversed '()])
    (if (empty? lst)
        lst-reversed
        (loop (rest lst) (cons (first lst) lst-reversed)))))

This is basically the same approach as having a helper function with an accumulator argument as in Oscar's answer, where the loop binding after let makes the let into an inner function you can call.

Solution 3

Here is a recursive procedure that describes an iterative process (tail recursive) of reversing a list in Scheme

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

Using substitution model for (reverse (list 1 2 3 4))

;; (reverse (list 1 2 3 4))                                                                                                                           
;; (go (list 1 2 3 4) ())                                                                                                                             
;; (go (list 2 3 4) (list 1))                                                                                                                         
;; (go (list 3 4) (list 2 1))                                                                                                                         
;; (go (list 4) (list 3 2 1))                                                                                                                         
;; (go () (list 4 3 2 1))                                                                                                                             
;; (list 4 3 2 1)

Here is a recursive procedure that describes a recursive process (not tail recursive) of reversing a list in Scheme

(define (reverse2 lst)
  (if (null? lst) ()
    (append (reverse2 (cdr lst)) (list (car lst)))))

(define (append l1 l2)
  (if (null? l1) l2
      (cons (car l1) (append (cdr l1) l2))))

Using substitution model for (reverse2 (list 1 2 3 4))

;; (reverse2 (list 1 2 3 4))                                                                                                                          
;; (append (reverse2 (list 2 3 4)) (list 1))                                                                                                          
;; (append (append (reverse2 (list 3 4)) (list 2)) (list 1))                                                                                          
;; (append (append (append (reverse2 (list 4)) (list 3)) (list 2)) (list 1))                                                                          
;; (append (append (append (append (reverse2 ()) (list 4)) (list 3)) (list 2)) (list 1))                                                              
;; (append (append (append (append () (list 4)) (list 3)) (list 2)) (list 1))                                                                         
;; (append (append (append (list 4) (list 3)) (list 2)) (list 1))                                                                                     
;; (append (append (list 4 3) (list 2)) (list 1))                                                                                                     
;; (append (list 4 3 2) (list 1))                                                                                                                     
;; (list 4 3 2 1)

Comments

[GoZoner]

I wouldn't advise against using 'list' as a parameter name - the lexical scoping of Scheme is part of its beauty. I would recommend not to conflate a parameter with a 'global' function; one of the errors in the posers code.

[Jack]

I think you meant append instead of cons. Running (reverse '(1 2 3)) yields '(((() . 3) . 2) . 1)

[Ciro Costa]

yep, you're right! @Salvatore Rapisarda got it right

[Will Ness]

isn't this exactly the same as the first solution in this answer here though, up to variables renaming. :)

[Tom el Safadi]

Yep, that looks like the same