Reversing a list in Scheme with restrictions

Question

I already have the code to reverse a list:

    (define (myreverse lst)
       (if (null? lst)
          lst
          (append (reverse (cdr lst))
                  (list (car lst)))))

But I want to do this using only lectrec, cons, car and cdr. How can I do that?

You [don't even need `letrec`](https://stackoverflow.com/a/19536834/849891) (besides the one which `define` itself encodes, in effect). — Will Ness, Feb 26 '19 at 12:43
@AlexKnauth not `append` I imagine, but you're right, the other two can't be avoided. — Will Ness, Feb 26 '19 at 13:57
There is a bug in your initial code. Should use `myreverse` and not `reverse`. How it is now you only add the the first elemenet last and use a different procedure to do the rest of the list reversal. — Sylwester, Feb 26 '19 at 14:18
@Sylwester cons car cdr null? and cond is enough, so must be with if instead of cond too. (see the link in my topmost comment) — Will Ness, Feb 26 '19 at 15:46
@WillNess but you don't have `cond`, `define` or `null?`. OP wants a solution using only `lectrec`, `cons`, `car` and `cdr` and then you have no way to do a base case. — Sylwester, Feb 26 '19 at 15:49
@Sylwester if that's what you meant then of course. if and null? are a must. I should expect define be acceptable in place of letrec, which, if not, is unusable without lambda. — Will Ness, Feb 26 '19 at 15:50

score 0 · Answer 1 · answered Apr 25 '19 at 11:50

The standard way to reverse a list without append is to use the helper function REVAPPEND, like this:

(define (reverse x) (revappend x '()))
(define (revappend x y)
  (if (null? x)
      y
      (revappend (cdr x) (cons (car x) y))))

Now if you want to implement reverse as a single function you can use LETREC to locally define the REVAPPEND helper, like this

(define (reverse x)
  (let revappend ((x x) (y '()))
    ...))

This is just a template to get you started, feel free to ask if you need more help.

1 Answers1