When would a cons return a cascaded list?

Question

I was doing exercise 2.18 of SICP(Structure and Interpretation of Computer Programs, 2nd edition) to make a program to reverse a list. And here is my code:

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

When I tested it with (rev (list 1 2 3 4 5)), it returned:

(((((5) . 4) . 3) . 2) . 1)

It was odd to me. Why did it return a cascaded list?

When I put:

(cons 1
      (cons 2
            (cons 3 '())))

it returned (1 2 3) but not (((1) 2) 3).

---

I'm doing SICP exercises in DrRacket with language R5RS.

Did I make any mistakes or choose a wrong language?

Answer 1

You need to learn what a list is ang get quite intimate with it to be a good lisper. The list (1 2 3) is just visual sugar for the pairs (1 . (2 . (3 . ()))) and can be made with (cons 1 (cons 2 (cons 3 '())))

The structure (((((5) . 4) . 3) . 2) . 1) is not a list except (5) which is visual sugar for (5 . ()). It can be made with (cons (cons (cons (cons (cons 5 '()) 4) 3) 2) 1)

When you make a list you need to make it from end to beginning. When you traverse a list you traverse it from beginning to the end. To get a list in the same order as your argument when processing you either need to use recursion so that your current step waits until the processing of the tail is finished until the final result is cones together or you use an accumulator to process the list in reverse and reverse the result when you're done.

It seems you are trying to reverse a list and that is then just accumulating the list while you iterate it:

(define (reverse lst)
  (define (reverse-aux lst acc)
    (if (null? lst)
        acc
        (reverse-aux (cdr lst) (cons (car lst) acc))))
  (reverse-aux lst '()))

As you can see I define an auxiliary function to get a third parameter and then use it. Most Schemers would prefer to do both in one operation with a named let

(define (reverse lst)
  (let reverse-aux ((lst lst) (acc '()))
    (if (null? lst)
        acc
        (reverse-aux (cdr lst) (cons (car lst) acc)))))

These are exactly the same. Usually when making something iterative many use the name loop in place of reverse-aux but it can be any name and i choose to keep the name from the first example.

There is no shortcut. You need to be able to look at ((a b) c (d)) and think (( a . (b ())) . (c . ((d . ()) . ()) so you need to do many exercises.

For what language in DrRacket to use when doing SICP have a look at my previous answer about it.