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?

Collinear

Do you expect your code to work with either or both of circular lists and improper lists? – Bonnibelle

instead of your (list A B) use (append A (list B)). – Sect

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.

Byler

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. – Bonnibelle

Answer 2

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)

Watertight

Answer 3

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.

Commensurate

Answer 4

Here's a solution using build-list procedure:

(define reverse
  (lambda (l)
    (let ((len (length l)))
      (build-list len
                  (lambda (i)
                    (list-ref l (- len i 1)))))))

Pittsburgh

Answer 5

This one works but it is not a tail recursive procedure:

(define (rev lst)
 (if (null? lst)
     '()
      (append (rev (cdr lst)) (car lst))))

Biomedicine

Answer 6

Tail recursive solution:

(define (reverse oldlist)
    (define (t-reverse oldlist newlist)
        (if (null? oldlist)
            newlist
            (t-reverse (cdr oldlist) (cons (car oldlist) newest))))
    (t-reverse oldlist '()))

Repent

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

Yep, that looks like the same – Repent

Answer 7

Just left fold the list using cons:

(define (reverse list) (foldl cons null list))

This is also efficient because foldl is tail recursive and there is no need for append. This can also be done point-free (using curry from racket):

(define reverse (curry foldl cons null))

Vierra

Answer 8

(define reverse?
  (lambda (l)
    (define reverse-aux?
      (lambda (l col)
        (cond 
          ((null? l) (col ))
          (else 
            (reverse-aux? (cdr l) 
                          (lambda () 
                            (cons (car l) (col))))))))
    (reverse-aux? l (lambda () (quote ())))))
(reverse? '(1 2 3 4) )

One more answer similar to Oscar's. I have just started learning scheme, so excuse me in case you find issues :).

Almsman

Answer 9

There's actually no need for appending or filling the body with a bunch of lambdas.

(define (reverse items)
  (if (null? items)
      '()
      (cons (reverse (cdr items)) (car items))))

Arnaldo

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

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

Answer 10

I think it would be better to use append instead of cons

(define (myrev l)
  (if (null? l)
      '()
      (append (myrev (cdr l)) (list (car l)))
  )
)

this another version with tail recursion

(define (myrev2 l)
  (define (loop l acc) 
    (if (null? l)
        acc
        (loop (cdr l) (append (list (car l)) acc ))
    )
  )
  (loop l '())
)

Lase