How to reverse list in Scheme?

Question

(define (list-without-last-pair items)
  (let ((s (cdr items)))
    (if (null? s)
    null
    (cons (car items)
          (list-without-last-pair s)))))

(define (only-last-pair items)
  (let ((s (cdr items)))
    (if (null? s)
        (car items)
        (only-last-pair s))))

(define (reverse items)
  (if (null? items)
       null
       (cons (only-last-pair items)
             (reverse (list-without-last-pair items)))))

I have a lot of code duplication inside my main method and auxiliary methods. How to avoid that and improve the solution?

Expected output: (reverse (list 1 2 3)) => (3 2 1)

Answer 1

Defining reverse is as easy as left folding your existing list onto a new empty list using cons

(define (reverse xs)
  (foldl cons '() xs))

To understand how it works, evaluate the fold

(reverse '(1 2 3)) ;; ⇒ ?

;; first iteration
(cons 1 '()) ;; ⇒ '(1)

;; second iteration
(cons 2 '(1)) ;; ⇒ '(2 1)

;; third iteration
(cons 3 '(2 1)) ;; ⇒ '(3 2 1)

---

In your comment you asked how to implement foldl

(define (foldl f y xs)
  (if (empty? xs)
      y
      (foldl f
             (f (car xs) y)
             (cdr xs))))

If you're unfamiliar with folds, I think demonstrating them with a sum function is the easiest.

If you want to sum a list of numbers 1 2 3 4, how would you do it? Probably something like

1 + 2 + 3 + 4

Do you see the + placed between each? Let's see how we'd evaluate this

((1 + 2) + 3) + 4
(3 + 3) + 4
6 + 4
⇒ 10

Well a foldl does exactly this. It takes a binary procedure, a initial value, and a list. In our case we'll demonstrate with the procedure + and the initial value of 0. This time we'll show the evaluation using s-expressions ((+ x y) instead of the infix x + y)

(foldl + 0 '(1 2 3 4))
(+ 4 (+ 3 (+ 2 (+ 1 0))))
(+ 4 (+ 3 (+ 2 1)))
(+ 4 (+ 3 3))
(+ 4 6)
⇒ 10

This initial value is important because if the input is an empty list, we need to know what kind of value to expect back

(foldl + 0 '())
;; ⇒ 0

So, let's define sum in terms of a fold

(define (sum xs) (foldl + 0 xs))
(sum '(1 2 3 4)) ;; ⇒ 10
(sum '())        ;; ⇒ 0

---

Sums are easy for us to understand because they're so familiar to us, but the reverse procedure might not be as clear. A fold reduces to a single value, and in our case, we're reducing our input list to a single output list.

Let's revisit that sum evaluation real quick. Remember the procedure we're folding with is + and the initial value is 0

(foldl + 0 '(1 2 3 4))
(+ 4 (+ 3 (+ 2 (+ 1 0))))
(+ 4 (+ 3 (+ 2 1)))
(+ 4 (+ 3 3))
(+ 4 6)
⇒ 10

Now let's see the reverse evaluation written out. Here the procedure we're folding with is cons and the initial value is '() (empty list)

(foldl cons '() '(1 2 3))
(cons 3 (cons 2 (cons 1 '())))
(cons 3 (cons 2 '(1)))
(cons 3 '(2 1))
⇒ '(3 2 1)

Answer 2

If you process a list using the usual car and cdr procedures you process it from front to back. Constructing a list using cons contructs it from back to front. So you can combine these 2 behaviours to reverse a list; just go over the list and cons the car to an accumulator:

(define (reverse lst)
  (let loop ((lst lst) (acc null))
    (if (null? lst)
        acc
        (loop (cdr lst) (cons (car lst) acc)))))

Note that loop is not a predefined procedure or keyword (as opposed to Common Lisp) but just a name I choose for my inner procedure; the above code is the same as

(define (reverse lst)
  (define (loop lst acc)
    (if (null? lst)
        acc
        (loop (cdr lst) (cons (car lst) acc))))
  (loop lst null))

or, if you want to avoid having 2 procedures you can work with an optional argument which has a default value:

(define (reverse lst (acc null))
  (if (null? lst)
      acc
      (reverse (cdr lst) (cons (car lst) acc))))

Answer 3

It's very rare to use the "back end" of a list for anything, it's both inefficient and tends to cause rather complex code (as you've noticed).

In order to reverse a list, you can save the first element, reverse the rest of it, and then put the old first element at the back of the "reversed rest".
(This is the same as what you're doing, but at the other end of the list.)

That is,

(define (reverse lst)
    (if (null? lst)
        lst
        (append (reverse (cdr lst)) (list (car lst)))))

This is quite inefficient though, so normally you would use a tail-recursive version ("iterative process" in SICP).

A tail-recursive implementation is perhaps most easily understood if you decompose it into a main function and a "helper":

(define (reverse-helper lst acc)
  (if (null? lst)
      acc
      (reverse-helper (cdr lst) (cons (car lst) acc))))

(define (reverse lst)
  (reverse-helper lst '()))

The main difference is that building the result in the acc parameter means that we can use cons and not need to repeatedly traverse the result to add things at the back of it (which is what append does).