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?

Answer 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.

Answer 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.