CODEWITHSUNDEEP
schemelispracket
Ranger 22
Ranger 22

Reputation: 445

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

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!

Upvotes: 3

Views: 1901

Answers (3)

Will Ness
Will Ness

Reputation: 71119

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

Upvotes: 2

&#211;scar L&#243;pez
&#211;scar L&#243;pez

Reputation: 236140

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.

Upvotes: 2

Rptx
Rptx

Reputation: 1189

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

Upvotes: 1

Related Questions