append - What does appending two lists like this return one list rather than a cons cell of two lists?

Question

A common and simple way of appending two lists is as follows:

(define (append a b)
  (if (null? a)
      b
      (cons (car a) (append (cdr a) b))))

Why does this work? When we reach the final element of a, my clearly incorrect belief is that we will be calling (cons [the original list a, built out of many calls to (cons (car a) ...)] [the original list b]). In short, I can't see why function does not return (cons a b), which would be a cons cell containing two lists. Even if I'm wrong about the a part, why is it valid to add b to our output as a whole list, without first breaking it down in to its individual elements?

I suspect that a worked example will be of great value to an answer.

question from:https://stackoverflow.com/questions/65863920/what-does-appending-two-lists-like-this-return-one-list-rather-than-a-cons-cell

Answer 1

Nowhere is a consed to b. Instead, the elements of a are consed to b, starting from the last element of a. Consider:

(append '() '(1 2 3))
--> '(1 2 3)  ; there are no elements in `a` to cons onto `b`

(append '(y) '(1 2 3))
--> (cons (car '(y)) (append (cdr '(y)) '(1 2 3)))
--> (cons 'y (append '() '(1 2 3)))
--> (cons 'y '(1 2 3))  ; the last element of `a` is consed onto `b`
--> '(y 1 2 3)

(append '(x y) '(1 2 3))
--> (cons (car '(x y)) (append (cdr '(x y)) '(1 2 3)))
--> (cons 'x (append '(y) '(1 2 3)))
--> (cons 'x (cons (car '(y)) (append (cdr '(y)) '(1 2 3))))
--> (cons 'x (cons 'y (append '() '(1 2 3))))
--> (cons 'x (cons 'y '(1 2 3)))  ; the last element of `a` is consed onto `b`
--> (cons 'x '(y 1 2 3))  ; then the next-to-last element of `a`, and so on
--> '(x y 1 2 3)