为什么像这样添加两个列表返回一个列表而不是两个列表的组合单元格?

Question

一个常见而简单的添加两个列表的方法如下:

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

为什么这个工作?当我们到达a的最后一个元素时，我显然错误的信念是我们将调用(cons [the original list a, built out of many calls to (cons (car a) ...)] [the original list b])。简而言之，我看不出为什么函数不返回(cons a b)，这将是包含两个列表的cons单元格。即使我对a部分的理解是错误的，为什么将b作为一个完整的列表添加到我们的输出中，而不首先将其分解为单个元素?

我想一个实际的例子对一个答案会很有价值。

Answer 1

a和b没有任何关系。相反，a的元素被转换为b，从a的最后一个元素开始。考虑:

(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)