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!

Answer 1

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.

Answer 2

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