0

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?

Will Ness
  • 70,110
  • 9
  • 98
  • 181
test2
  • 1
  • When creating a list you do the elements in opposite order and when you iterate you do them in order. Reversing is just recursing the CDR while consing the CAR element to an accumulator initialized as the empty list. When your base case hits you evaluate that accumulator since it will have the reversed list. – Sylwester Mar 25 '22 at 11:07
  • the first `cons` in your `my-reverse2` must be changed to `append` to make it work, but you said `append` isn't allowed. the `'()` which you use doesn't appear in your list of allowed symbols either. – Will Ness Mar 26 '22 at 10:08
  • @Sylwester the empty list doesn't appear in the list of allowed entities. – Will Ness Mar 26 '22 at 10:12
  • @WillNess What does `null?` do except checking if the argument is the empty list? Also where does it limit literals in the solution? – Sylwester Mar 26 '22 at 11:49
  • "and any operators”. What is an operator? According to SICP it is the first element in an application. Eg in `(bla ble bli)` `bla` is an operator while `ble` and `bli` are operands. If I can use any operator wony that remove the restriction on valid forms? – Sylwester Mar 26 '22 at 12:00
  • @Sylwester the whitelist in the post includes `null?` but does not include `'()`, is all I'm saying. Indeed the literal `'()` is not used in my solution. – Will Ness Mar 26 '22 at 14:53
  • @WillNess use of `'()` may be implied as it is used in the OP's attempt? – Mulan Apr 13 '22 at 05:38

4 Answers4

1

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.

Oliver Mason
  • 2,240
  • 2
  • 15
  • 23
1

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.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
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))))))))
Mulan
  • 129,518
  • 31
  • 228
  • 259
  • @WillNess, of course now i'm torturing myself trying to solve the problem using delimited continuations... let me know if you see a solution :D – Mulan Apr 13 '22 at 06:20
  • will read later when I have time... :) not for several hours for sure. :( – Will Ness Apr 13 '22 at 08:36
0

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)
Martin Půda
  • 7,353
  • 2
  • 6
  • 13