How to recursively change a list using only basic operations?

Question

I was wondering how to change the list using only basic operations like cons, first, rest, empty? etc.

No auxiliary functions or batteries are allowed, and the function accepts only one input - a list.

I was told that this is possible, although I can not hug his head around him.

This is what I have conceptualized so far. I do not know how to generate 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, you can do something similar with a function that changes the first and last list, although I do not quite understand it. 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: reply at the end of this post) Second 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 are you doing, you ask? Data flow diagram for alternative if clause -

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

(follow the arrows from left to right). In this way,

 [] -> [] [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 really replaces the finite elements of the list. Let this be proved by 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 this is proven. Thus, we need to develop a data flow diagram that, on the assumption of changing the list (N-1) -length, will change the list of N-lengths:

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

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

Haskell's translation in the comments follows the diagram quite naturally. This is really readable: a is the last element, b is the inverse "core" (that is, the input list without its first and last element), so we cancel the inverse core, add the first element to get the value of the input list, then cancel it and add the last item. Just.:)

Answer 2

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

Indeed one of the few ways to do this effectively. But still, some kind of auxiliary procedure.

Another way, but not tail-recursive, and if the append does not use set-cdr! this is really unsuitable 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 as follows (although, as Oscar notes, this is not the way you would normally like to approach the problem):

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

Here are the definitions of last and butlast . It seems that they will not be useful to you for this task, if they are not part of your default environment, but when you start to read well and think about a lot 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))))