How to Write a Reverse Function in Scheme?

Question

I have to write a scheme function which does the following:

Define a SCHEME function, named (rev p), which takes a pair as an argument and evaluates to another pair with the first and second elements in the pair p in reverse order. For instance,

( rev ( cons 1 2))
> (2 . 1)

Here is my code:

(define (rev p)
  (cond ((null? p) '())
        (not (pair? (car p)) p)
        (else (append (rev (cdr p)) (list (rev (car p))))

However, my code returns (1 . 2) when I test it when it should be returning (2 . 1).

From the description you provided it seems like you are only dealing with pairs and not with lists. — Ryan Schaefer, Mar 03 '20 at 21:39

alinsoar · Answer 1 · 2020-03-07T08:46:55.513

1

(define rev
  (lambda (l acc)
    (if (null? l)
        acc
        (rev (cdr l)(cons (car l) acc)))))

(rev '(1 2 3) '())

And here is an apparently obfuscate version, but the ideas may be useful.

(define rev
  (lambda (l k)
    (if (null? l)
        (k (lambda (x) x))
        (rev (cdr l)
             (lambda (k0)
               (k (lambda (r) (k0 (cons (car l) r)))))))))

((rev '(1 2 3) (lambda (x) x)) '())

--

As suggested by Will, here is other variant, non-tail recursive, hence not completely cps'd, it's a combination of classic recursion and cps.

(define rev
  (lambda (l k)
    (if (null? l)
        (k '())
        (rev (cdr l)
             (lambda (r)
               (cons (car l)
                     (k r)))))))

edited Mar 07 '20 at 08:46

answered Mar 04 '20 at 05:57

alinsoar

15,386
4
57
74

1

here's [some quite crazy way to reverse a list](https://stackoverflow.com/a/19536834/849891), for your perusal. :) re your code, it *is* quite complicated, I could only make sense of it after doing [some sample reductions](https://pastebin.com/YQgTtRBd). there's a simpler way to do it with CPS, too. – Will Ness Mar 05 '20 at 16:27
@WillNess completed your variant, too. – alinsoar Mar 07 '20 at 08:49
you're right, I thought about it also, that it is not really CPS, it just builds the lambda function to do the job. – Will Ness Mar 07 '20 at 11:06

score 0 · Accepted Answer · answered Mar 03 '20 at 21:53

If it's just a pair that you want to reverse, it's pretty simple, you don't even need to do recursion! And remember to use cons, not append:

(define (rev p)
  (cond ((not (pair? p)) p)
        (else (cons (cdr p) (car p)))))

For example:

(rev '())
=> '()
(rev 5)
=> 5
(rev (cons 1 2))
=> '(2 . 1)

score 0 · Answer 3 · answered Mar 04 '20 at 03:26

0

Or the same expressed as:

(define (rev p)
  (if (pair? p)
      (cons (cdr p) (car p))
      p))

answered Mar 04 '20 at 03:26

Gwang-Jin Kim

9,303
17
30

score 0 · Answer 4 · answered Mar 01 '22 at 17:15

0

All you need to do for this function is use the car and cdr function for your pair p.

(define (rev p)
    (cons (cdr p) (car p))
    )

answered Mar 01 '22 at 17:15

Amogh Chaubey

1
1

How to Write a Reverse Function in Scheme?

4 Answers4