list - 如何在不创建嵌套列表的情况下在 erlang 中连接列表？

Question

我正在努力成为一个好的 erlanger 并避免使用“++”。我需要在不创建嵌套列表的情况下将元组添加到列表的末尾(希望不必向后构建和反转它)。给定元组 T 并列出 L0 和 L1:

当我使用 [T|L0] 我收到 [元组，list0] .

但是当我使用 [L0|T] , 我得到嵌套列表 [[list0]|元组] .同样， [L0|L1] 返回 [[list0]|list1] .

删除外部列表括号 L0|[T] 产生语法错误。

为什么是“|”不对称？有没有办法使用“|”来做我想做的事？

Answer 1

|不是“对称的”，因为非空列表有一个头部和一个尾部，其中头部是单个项目，尾部是另一个列表。在表达式 [foo | bar] 中foo表示列表的头部和 bar是尾部。如果尾部不是一个正确的列表，结果也不会是一个正确的列表。如果头部是一个列表，结果将只是一个列表，该列表作为它的第一个元素。

无法在小于 O(n) 的时间内追加到链表的末尾。这就是为什么使用 ++因为这通常是回避的。如果有特殊的语法要附加到列表的末尾，它仍然需要花费 O(n) 时间，并且使用该语法不会比使用 ++ 更能让你成为“好erlanger”。将。

如果您想避免每次插入的 O(n) 成本，您需要预先添加然后反转。如果您愿意支付费用，您不妨使用++ .

关于列表如何工作的更多细节:
[ x | y ]是一种叫做 cons 细胞的东西。在 C 术语中，它基本上是一个具有两个成员的结构。正确列表要么是空列表( [] )，要么是第二个成员是正确列表的 cons 单元格(在这种情况下，第一个成员称为其头部，第二个成员称为尾部)。

所以当你写 [1, 2, 3]这将创建以下 cons 单元格:[1 | [2 | [3 | []]]] . IE。该列表表示为一个 cons 单元，其第一个成员(其头部)为 1，第二个成员(尾部)是另一个 cons 单元。另一个 cons 单元格以 2 作为其头部，另一个 cons 单元格作为其尾部。该单元格的头部为 3，尾部为空列表。

遍历这样的列表是通过首先作用于列表的头部然后在列表的尾部调用遍历函数来递归完成的。

现在，如果您想将一个项目添加到该列表中，这非常简单:您只需创建另一个 cons 单元，其头部是新项目，尾部是旧列表。

然而，附加一个项目要昂贵得多，因为创建单个 cons 单元格是不够的。您必须创建一个与旧列表相同的列表，除了最后一个 cons 单元格的尾部必须是一个新的 cons 单元格，其头部是新元素，尾部是空列表。所以你不能在不遍历整个列表的情况下追加到列表，这是 O(n)。