How to recursively reverse a list using only basic operations?

Question

I was wondering how to reverse a list using only basic operations such as cons, first, rest, empty?, etc.

No helper functions or accumulators allowed, and the function only takes one input - a list.

I was told it was possible, though I can't wrap my head around it.

This is what I have conceptualized so far. I don't know how to form the recursion for the rest of the list.

(defunc rev-list (x)
  (if (or (equal (len x) 0) (equal (len x) 1))
      x
      (cons (first (rev-list (rest x)))
            ???)))

Apparently it is possible to do something similar with a function that swaps the first and last of a list, though I don't fully understand it either. Here is the code for it:

(define swap-ends (x)
  (if (or (equal (len x) 0) (equal (len x) 1))
      x
      (cons (first (swap-ends (rest x))) 
            (swap-ends (cons (first x) 
                             (rest (swap-ends (rest x))))))))

Answer 1

(note: the answer is at the bottom of this post) The 2nd function,

(define (swap-ends x)                                   ; swap [] = []
  (if (or (equal (length x) 0) (equal (length x) 1))    ; swap [x] = [x]
      x                                                 ; swap (x:xs) 
      (cons (first (swap-ends (rest x)))                ;    | (a:b) <- swap xs 
            (swap-ends (cons (first x)                  ;    = a : swap (x : b)
                             (rest (swap-ends (rest x))))))))

(with Haskell translation in the comments) what does it do, you ask? The data flow diagram for if's alternative clause is

                   /-> first ----------------------> cons
x --> first ------/-------------> cons --> swap --/
  \-> rest -> swap ---> rest ---/

(follow the arrows from left to right). So,

[] -> []
[1] -> [1]
                     /-> 2 -----------------------> [2,1]
[1,2] --> 1 --------/------------> [1] --> [1] --/
      \-> [2] -> [2] ---> [] ---/

                           /-> 3 -------------------------> [3,2,1]
[1,2,3] --> 1 ------------/----------> [1,2] --> [2,1] --/
        \-> [2,3] -> [3,2] -> [2] --/

                             /-----> 4 ----------------------------> [4,2,3,1]
[1,2,3,4] --> 1 ------------/---------------> [1,3,2] -> [2,3,1] -/
          \-> [2,3,4] -> [4,3,2] -> [3,2] -/

So far it indeed does swap the end elements of a list. Let's prove it by the natural induction,

true(N-1) => true(N):

                       /-> N --------------------------------------> [N,2..N-1,1]
[1..N] --> 1 ---------/-----------> [1,3..N-1,2] -> [2,3..N-1,1] -/
       \-> [2..N] -> [N,3..N-1,2]   /
                    -> [3..N-1,2] -/

So it is proven. Thus, we need to devise a data flow diagram which, under the supposition of reversing an (N-1)-length list, will reverse an N-length list:

[1..N] --> 1 ------------------------------------\
       \-> [2..N] -> [N,N-1..2] -> N -------------\------------------\
                     \-> [N-1,N-2..2] -> [2..N-1] -> [1..N-1] -> rev -> cons

Which gives us the implementation

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

(rev '(1 2 3 4 5))     ; testing
;Value 13: (5 4 3 2 1)

The Haskell translation in the comments follows the diagram quite naturally. It is actually readable: a is the last element, b is the reversed "core" (i.e. the input list without its first and last element), so we reverse the reversed core, prepend the first element to get the butlast part of the input list, then reverse it and prepend the last element. Simple. :)

2020 update: here's a Scheme version based on the code by @Rörd from the comments, such that it is similarly readable, with arguments destructuring in place of Haskell's pattern matching:

(define (bind lst fun)
  (apply fun lst))

(define (rev lst)
  (if (or (null? lst)
          (null? (cdr lst)))
    lst
    (bind lst
      (lambda (first . rest)
         (bind (rev rest)
           (lambda (last . revd-core)
              (cons last (rev (cons first (rev revd-core))))))))))

Answer 2

(define (reverse x)
  (let loop ((x x) (y '()))
    (if (null? x)
        y
        (let ((temp (cdr x)))
          (set-cdr! x y)
          (loop temp x))))))

Really one of the few ways to do it efficiently. But still sort of a helper procedure.

Other way, but not tail-recursive, and if the append doesn't use a set-cdr! it's really unusable for large lists.

(define (reverse L)
  (if (null? l)
      '()
       (append (reverse (cdr L)) (list (car L)))))

Answer 3

Do you have last and butlast in your environment? If so, the procedure can be defined like this (though as Oscar notes this isn't how you'd normally want to approach the problem):

(define (rev lst)
  (if (null? lst)
      '()
      (cons (car (last lst))
            (rev (butlast lst)))))

Here are definitions of last and butlast. It sounds like they won't do you any good for this assignment if they're not part of your default environment, but when you're starting out it's good to read through and think about lots of recursive procedures.

(define (butlast lst)
  (if (or (null? lst) (null? (cdr lst)))
      '()
      (cons (car lst) (butlast (cdr lst)))))

(define (last lst)
  (if (or (null? lst) (null? (cdr lst)))
      lst
      (last (cdr lst))))