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

The concept of [car and cdr](https://en.wikipedia.org/wiki/CAR_and_CDR) might help you out here. — JDong, Oct 22 '13 at 22:58
Well I know how first(car) and rest(cdr) are used, but I don't understand how to build the proper list for the recursion of the list. — b33k3rz, Oct 22 '13 at 23:04

Will Ness · Accepted Answer · 2020-12-10T06:21:39.300

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

Here's an attempt to make the Scheme version similarly readable: https://gist.github.com/roerd/7117783. — Rörd, Oct 23 '13 at 12:34

score 2 · Answer 2 · answered Oct 23 '13 at 02:54

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

answered Oct 23 '13 at 02:54

WorBlux

1,423
11
20

In a previous (now deleted) answer OP stated that he can't use `append`, either. Your first variant uses a helper, just like my own second variant. I don't think it's possible to strictly adhere to all of OP's restrictions, it's quite likely that he misunderstood the problem description – Óscar López Oct 23 '13 at 03:01

jbm · Answer 3 · 2013-10-22T23:51:38.050

1

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

edited Oct 22 '13 at 23:51

answered Oct 22 '13 at 23:43

jbm

2,575
16
15

I don't, which make it all the more difficult. There is a way to get the last of a list without the actual command though, it would be to call (first (rev-list (rest x))), assuming the base case is like the one I had in my example. – b33k3rz Oct 22 '13 at 23:46
Do you have written requirements for the procedure? It might help us to read them verbatim. – jbm Oct 22 '13 at 23:56
Using only if, cons, first, rest, empty? (endp) or len, write a function that takes in a list (only input) and reverses it. No helper functions allowed. i was given the swap-ends solution using these restrictions, which is conceptually similar. I'm sure if I understood how it worked I'd be able to do something similar for reverse-list. – b33k3rz Oct 23 '13 at 00:06

How to recursively reverse a list using only basic operations?

3 Answers3

Linked

Related