Reversing a list on Scheme with restrictions-CodePudding

I'm trying to reverse a list on 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?

CodePudding user response：

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)

CodePudding user response：

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.

CodePudding user response：

Reverse the cdr, take its car (which will be ... the last element, right?) and its cdr is the reversed core -- the original list without its last and first element.

Then, cons the original car onto the reversed core, reversed, reverse the result, and cons the last element onto it. Simple, right? Yeah, not so much. Here's the illustration:

     a b c ...... m n
       b c ...... m n
                    n m ...... c b
                      m ...... c b
                                 b c ...... m
     a                           b c ...... m
                                            m ...... c b a
                    n                       m ...... c b a

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.