Reverse a linked list in Scheme

Question

I am trying to reverse a linked list in Scheme; and I have no idea why this isn't working. I am using Chez Scheme by the way. It is giving me this error: Exception: incorrect number of arguments to #procedure reverse-ll at reverse-linked-list.scm:59. Does anyone have an idea as to what is happening? Thanks!

(define pi '(3 1 4 1 5 9 2 6 5 3 5))

(define reverse-ll
  (lambda (orig rev)
                (if (null? (cdr orig)) rev
                           (reverse-ll (cons (car orig) rev)))))

(define reverse-pi (reverse-ll pi '()))
(display reverse-pi)

Answer 1

The error says that a call to reverse-ll does not have enough arguments, and there are only two such calls. The call (reverse-ll pi '()) is fine, since reverse-ll takes two list arguments. The other call is the problem:

(reverse-ll (cons (car orig) rev))

Here reverse-ll is given only one argument: (cons (car orig) rev). This expression is adding the first element of the input list to the accumulator. But the code is missing the reduced input list for the recursive step. Instead:

(reverse-ll (cdr orig) (cons (car orig) rev))

There is another problem. As written, the code does not include the last element of the input list in the reversed output. This is because of the base case:

(if (null? (cdr orig)) rev ;; )

In this code the base case is reached when (cdr orig) is '(), and that happens when the input list has been reduced to a length of one element. The last element is then not processed by the reverse-ll procedure. Instead you want an empty list in the input to trigger the return of the accumulator:

(define reverse-ll
  (lambda (orig rev)
                (if (null? orig) rev
                           (reverse-ll (cdr orig) (cons (car orig) rev)))))

Here is the result, showing both input and output:

> (load "scratch.ss")
(3 1 4 1 5 9 2 6 5 3 5)
(5 3 5 6 2 9 5 1 4 1 3)