Reversing a list in Scheme with some restrictions

Question

I'm trying to reverse a list in Scheme, but I can only use define, car, cdr, list?, null?, if, cond, cons, display, begin, and any operators. I cannot use append, loops (must be pure recursion), lambda and any other functions that I have not mentioned. I'm also not allowed to use helper functions. Everything should be in one function.

It's been hours now and I've tried multiple solutions and I still cannot solve this. This is the closest solution that I got:

(define (my-reverse2 lis)
    (if (null? (cdr lis)) lis
        (cons (my-reverse2 (cdr lis)) (cons (car lis) '()))))

And this is the output:

> (my-reverse2 '(3 2 1))
Output: (list (list (list 1) 2) 3)

The output should be something like (1 2 3). How should I proceed?

Answer 1

Probably the most inefficient reverse ever written but it does meet the criteria in your question. By the end of this exercise you should be fairly comfortable thinking purely in terms of car and cdr -

(define (reverse t)
  (if (null? t)
      t
      (if (null? (cdr t))
          t
          (cons (car (reverse (cdr t)))
                (reverse
                 (cons (car t) 
                       (reverse
                        (cdr (reverse (cdr t))))))))))

(reverse '(1 2 3 4 5 6 7 8 9))

'(9 8 7 6 5 4 3 2 1)

Well dangit, this is basically what @WillNess wrote :D

If let is allowed, you can remove two instances of (reverse (cdr t)) -

(define (reverse t)
  (if (null? t)
      t
      (if (null? (cdr t))
          t
          (let ((q (reverse (cdr t))))
            (cons (car q)
                  (reverse (cons (car t)
                                 (reverse (cdr q)))))))))

If or is allowed, we can collapse the two if -

(define (reverse t)
  (if (or (null? t) (null? (cdr t)))
      t
      (let ((q (reverse (cdr t))))
        (cons (car q)
              (reverse (cons (car t)
                             (reverse (cdr q))))))))

Answer 2

First, reverse the cdr and take its car -- which will be ... the last element, right? -- and its cdr will be the reversed core, i.e. the original list without its last and first element.

Then, cons the original car onto the reversed core, reversed, thus getting all the elements of the list without the last one, in original order. So then now we can reverse that, and cons the last element onto the result.

Simple, right? Yeah, not so much. So here's an illustration:

a b c ...... m n                                         ; car, cdr:
  b c ...... m n                                         ; reversen-1:
|              n m ...... c b                            ; car, cdr:
|                m ...... c b                            ; reversen-2:
|              |            b c ...... m                 ; cons a:
a              |            b c ...... m                 ; reversen-1:
               |                       m ...... c b a    ; cons n:
               n                       m ...... c b a    ; =: reversen

All this needs is cdr, car, cons, null?, cond, and recursion. let/define will help a lot but is not strictly necessary. Do not forget to take care of the corner cases.

See also: this related answer of mine.

Answer 3

The easiest way would be to use an accumulator value:

(define (my-reverse the-list acc)
  (if (null? the-list)
      acc
      (my-reverse (cdr the-list)
                  (cons (car the-list) acc))))

You call this (my-reverse '(1 2 3) '()). If there were optional arguments in Scheme you could make the acc optional with a default value of the empty list. In my code I would usually have a wrapper around this with a single argument only which then calls the two argument version with the empty list.

Answer 4

Are you allowed to use optional arguments?

(define (my-reverse lst [lst2 '()])
  (if (null? lst) lst2
      (my-reverse (cdr lst)
                  (cons (car lst) lst2))))

Test:

> (my-reverse '(3 2 1))
'(1 2 3)