Reverse in Scheme

Question

I wrote the following code that reverses a Scheme list:

(define (my-reverse lst)
  (if (null? lst)
      '()
      (append (my-reverse (cdr lst)) (list (car lst)))))

When I trace this function for the list (list 1 2 3 4 5), Scheme shows this:

>(my-reverse (mcons 1 (mcons 2 (mcons 3 (mcons 4 (mcons 5 '()))))))
> (my-reverse (mcons 2 (mcons 3 (mcons 4 (mcons 5 '())))))
> >(my-reverse (mcons 3 (mcons 4 (mcons 5 '()))))
> > (my-reverse (mcons 4 (mcons 5 '())))
> > >(my-reverse (mcons 5 '()))
> > > (my-reverse '())
< < < '()
< < <(mcons 5 '())
< < (mcons 5 (mcons 4 '()))
< <(mcons 5 (mcons 4 (mcons 3 '())))
< (mcons 5 (mcons 4 (mcons 3 (mcons 2 '()))))
<(mcons 5 (mcons 4 (mcons 3 (mcons 2 (mcons 1 '())))))

What I don't understand, is why at the end 5 is "being appended" to '(), instead of '() being appended to 5? Because in the code there is written (append (my-reverse (cdr lst)) (list (car lst))) and the (my-reverse (cdr lst)) at the end, so (my-reverse (cdr (list 5))) is '()? And the code says (append '() (list 5)?

dratenik dratenik · Accepted Answer · 2020-10-08T15:47:27

As you can see in the forward direction in (my-reverse (mcons 5 '())), the way it says "list with one element equal to 5" is (mcons 5 '()). And when the function returns a list of one element, it is once again displayed as (mcons 5 '()) .

Reverse in Scheme

1 Answers