How to reverse the order of elements of a list in Scheme

Question

I got a function to reverse the order of the elements in a list, such as

(define (rvsl sequence)
  (foldl (lambda (x y) 
           (cons y x)) 
         '() sequence))

However, when I ran it in DrRacket with the input

(rvsl (list 2 3 4))

DrRacket told me this

cons: second argument must be a list, but received empty and 2

Could anybody please give me some ideas to solve it?

Thanks in advance!

You defined rvsl to take two arguments and only passed it one when you used it. You can either pass it two arguments from the start, or create another procedure which will pass the proper number of arguments to rvsl. — malisper, Sep 01 '14 at 15:38

Óscar López · Accepted Answer · 2014-09-02T00:57:37.117

The problem with your code is that you're passing the parameters in the wrong order - when using cons to build a list, the first parameter is the new element we want to stick at the beginning of the list, and the second one is the list we've built so far.

Having said that, reversing a list using foldl is a bit simpler and you don't need to use append at all - in fact, it's a bad practice using append when cons suffices:

(define (rvsl sequence)
  (foldl cons
         '()
         sequence))

Why this works? let's rewrite the function being more explicit this time:

(define (rvsl sequence)
  (foldl (lambda (current accumulated)
           (cons current accumulated))
         '()
         sequence))

Now we can see that the lambda procedure receives two parameters: the current element in the input list, and the accumulated value so far - good parameter names make all the difference in the world! this is much, much clearer than calling the parameters x and y, which says nothing about them.

In this case, we just want to cons the current element at the head of the accumulated value (which starts as an empty list), hence producing a reversed list as the output. Given that the lambda procedure receives two parameters and passes them in the same order to cons, we can simplify the whole thing and just pass the cons procedure as a parameter.

score 1 · Answer 2 · edited May 23 '17 at 12:29

You don't have to use foldl or anything else, actually, to define the rev function; the rev function itself is enough:

(define (rev ls)                                 ; rev [] = []
  (cond                                          ; rev [x] = [x]
    ((null? ls) ls)                              ; rev (x:xs) 
    ((null? (rest ls)) ls)                       ;   | (a:b) <- rev xs 
    (else                                        ;   = a : rev (x : rev b)
      (cons (first (rev (rest ls)))
            (rev (cons (first ls)
                       (rev (rest (rev (rest ls))))))))))

(comments in equational pattern-matching pseudocode). Derivation and some discussion here.

(edit: that's obviously a toy code, just to hone your Scheme-fu).

score 1 · Answer 3 · answered Sep 01 '14 at 23:04

1

Here is a simple version, using an internal iterative procedure.

(define (rev lst)
  (define (iter accum lst)
    (if (null? lst)
        accum
        (iter (cons (car lst) accum)
              (cdr lst))))
  (iter '() lst))

answered Sep 01 '14 at 23:04

Rptx

1,159
1
12
17

How to reverse the order of elements of a list in Scheme

3 Answers3