为什么参数的位置在 cons 中很重要？

Question

简单代码：

> (cons null (cons 1 2))
'(() 1 . 2)
> (cons (cons 1 2)  null)
'((1 . 2))

最初，我希望结果是一样的。我能想到一些模糊的解释，但也想听听有知识的人的强项。

为什么结果不一样？

Answer 1

用数学的说法，有些运算是可交换的。加法是可交换的，所以 (+ 1 2) 和 (+ 2 1) 都有相同的结果。除法不可交换； (/ 1 2) 和 (/ 2 1) 没有相同的结果。

OP 期望 (cons null (cons 1 2)) 和 (cons null (cons 1 2)) 应该有相同的结果实际上是期望 cons 是一个交换过程。它不是。如果 cons 是可交换的，那么 (cons 1 2) 和 (cons 2 1) 将是等价的。但是：

> (cons 1 2)
(1 . 2)
> (cons 2 1)
(2 . 1)

cons 过程创建一个 cons 单元格，它有两个组件，传统上称为 car 和 cdr；它从两个参数创建 cons 单元格。第一个参数放在单元格的car，第二个参数放在单元格的cdr。用(cons 1 2)，1放在car，2放在cdr；但是对于 (cons 2 1)，2 被放置在 car 中，而 1 被放置在 cdr 中。您可以看到 (cons 1 2) 和 (cons 2 1) 必然不同，因为 cons 单元格的 car 和 cdr 是不同的。

OP 示例 (cons null (cons 1 2)) 将空列表放置在 cons 单元格的 car 中，并放置单元格 (1 . 2)（它本身由对 cons) 在该单元格的 cdr 中。这是 虚线列表（如下所述）(() . (1 . 2))；这样的点列表通常在 REPL 中表示为 (() 1 . 2).

但是对于 (cons (cons 1 2) null)，单元格 (1 . 2) 被放置在 cons 单元格的 car 中，而空列表位于 cdr 中该单元格的：((1 . 2) . ()).

现在，在 Lisps 中，列表是 cons 以空列表结尾的单元格链。像 (1 . (2 . 3)) 这样的链有时被称为 虚线列表 或 不正确的列表 ；这是一个 cons 单元格链，不以空列表结尾。在 REPL 中，您经常会看到 (1 . (2 . 3)) 表示为 (1 2 . 3)。另一方面，像 (1 . (2 . ())) 这样的链被称为 proper list；这是一个 cons 单元格链，以空列表结束。您会看到它在 REPL 中表示为 (1 2)。通常当有人使用不合格的术语 list 时，他们的意思是 proper list.

所以，OP代码((1 . 2) . ())等价于包含单个成员(1 . 2)的真列表((1 . 2))，这肯定不同于虚线列表(() 1 . 2) ].

还有另一个过程，append，它的行为符合 OP 的预期。 (append null (append '(1) '(2))) 和 (append (append '(1) '(2)) null) 的计算结果都是 '(1 2)。最后两个表达式的计算结果相同，因为空列表是操作 append 的 标识元素 。也就是说，将一个非空的项目列表与空列表连接起来会返回一个非空列表的副本。类似地，将空列表与非空列表连接会返回非空列表的副本。但是 append 不是可交换的； append returns 包含第一个列表的元素后跟第二个列表的元素的列表。所以，(append '(1 2) '(3 4)) --> '(1 2 3 4)，但是 (append '(3 4) '(1 2)) --> '(3 4 1 2).

还有一个相关的数学属性：关联性。加法是关联的，即 (+ 1 (+ 2 3)) 和 (+ (+ 1 2) 3) 都计算出相同的结果。使用中缀表示法，1 + (2 + 3) 和 (1 + 2) + 3 的计算结果相同。这有一个有趣的结果。由于分组并不重要，所以将上述中缀表达式简单地写成1 + 2 + 3是有意义的。对应的前缀表达式是(+ 1 2 3)，Lisps支持这种多操作数加法的表达方式

cons 不关联。由于 cons 从其参数创建一对，因此它不能关联。使用 (cons 1 2) 创建对 (1 . 2)。使用 (cons 1 (cons 2 3)) 对 (2 . 3) 被放置在另一对的 cdr 中，结果是 (1 . (2 . 3)) （可能在 REPL 中表示为 (1 2 . 3)）。但是使用 (cons (cons 1 2) 3) 会创建对 (1 . 2) 并将其放置在另一对的 car 中，从而得到 ((1 . 2) . 3)。请注意，由于 cons 不是关联的，因此像 (cons 1 2 3) 这样的表达式没有意义；操作分组不清楚。

但是append是关联的。使用 (append '(1) '(2)) 创建列表 (1 2)。使用 (append '(1) (append '(2) '(3))) 创建列表 (2 3)，然后将列表 (1) 与 (2 3) 连接，得到 (1 2 3)。使用 (append (append '(1) '(2)) '(3)) 创建列表 (1 2)，然后将其与列表 (3) 合并，从而得到列表 (1 2 3)。由于分组在这里并不重要，因此简单地写成 (append '(1) '(2) '(3)) 是有意义的，而且与加法一样，Lisps 确实支持这种表达追加操作的方式。

Answer 2

参见 SICP here 中的“框和指针”图。 cons 是成对的 构造函数 - 它只是将两个东西放在一起。如果我们概括这种配对的概念，我们就可以构建树。在 scheme/racket 中，列表只是树的一个特例（每个“左”分支包含列表的一个元素，每个右分支包含列表的其余部分）。

shorthand：由于写(cons 1 (cons 2 (cons 3 null)))比较麻烦，我们简化为：'(1 2 3)。请注意，shorthand 中省略了最后的 null（或 '()）。如果它不是 null 而是 4，我们将得到以下 shorthand 版本：'(1 2 3 . 4)。点表明结构的右侧不是列表。

对于第一个示例，null 只是列表的一个元素 - 出现在左分支上。对于第二个示例，null 是最右边的元素 - 建议列表结束。

    / \          Null is displayed as () in
   /   \         the shorthand version. Whenever
 null            a pair does not have a list
       / \       on the right, we see a dot.
      /   \ 
     1     2


       / \       Note here that the null
      /   \      is on the last right-most
          null   branch. This null is not
    / \          shown in the shorthand.
   /   \
  1     2

为什么参数的位置在 cons 中很重要？

Why does the position of arguments matter in cons?

list

scheme

lisp

racket

cons