附加两个像这样的列表 return 一个列表而不是两个列表的 cons 单元格是什么意思？

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])。简而言之，我不明白为什么函数没有 return (cons a b)，这将是一个包含两个列表的 cons 单元格。即使我对 a 部分的理解是错误的，为什么将 b 作为一个整体列表添加到我们的输出中而不首先将其分解为各个元素是有效的？

我怀疑一个有效的例子对答案很有价值。

Answer 1

a 无处允许 b。相反，从 a 的 last 元素开始，a 的元素被限制为 b .考虑：

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

附加两个像这样的列表 return 一个列表而不是两个列表的 cons 单元格是什么意思？

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

lisp

scheme

list

append

cons