我正在努力成为一个好的 erlanger 并避免使用“++”。我需要在不创建嵌套列表的情况下将元组添加到列表的末尾（希望不必反向构建和反转它）。给定元组 T 和列表 L0 和 L1：
当我使用[T|L0]时，我得到[tuple,list0]。
但是当我使用[L0|T]时，我得到嵌套列表[[list0]|tuple]。同样，[L0|L1]返回[[list0]|list1]。
删除外部列表括号L0|[T]会产生语法错误。
为什么是“|” 不对称？有没有办法使用“|”做我想做的事？
问问题
3142 次
1 回答
20
|不是“对称的”，因为非空列表具有头部和尾部，其中头部是单个项目，尾部是另一个列表。在表达式[foo | bar] foo中表示列表的头部并且bar是尾部。如果尾部不是正确的列表，则结果也不会是正确的列表。如果头部是一个列表，则结果将只是一个以该列表作为其第一个元素的列表。
没有办法在少于 O(n) 的时间内追加到链表的末尾。这就是为什么++通常避免使用 for 的原因。如果在列表末尾附加特殊语法，它仍然需要花费 O(n) 时间，并且使用该语法不会使您比 using 更加“优秀的 erlanger” ++。
如果您想避免每次插入的 O(n) 成本，您需要预先添加然后反转。如果您愿意支付费用，您不妨使用++.
关于列表如何工作的更多细节：
[ x | y ]是一种叫做缺点细胞的东西。在 C 语言中，它基本上是一个具有两个成员的结构。正确列表是空列表 ( []) 或第二个成员是正确列表的 cons 单元格（在这种情况下，第一个成员称为它的头，第二个成员称为它的尾）。
因此，当您编写[1, 2, 3]此代码时，会创建以下 cons 单元格：[1 | [2 | [3 | []]]]. 即列表表示为一个 cons 单元格，其第一个成员（它的头部）是 1，第二个成员（尾部）是另一个 cons 单元格。另一个 cons 单元格有 2 作为其头部，另一个 cons 单元格作为其尾部。该单元格的头部为 3，尾部为空列表。
遍历这样的列表是递归完成的，首先作用于列表的头部，然后在列表的尾部调用遍历函数。
现在，如果您想在该列表中添加一个项目，这很容易：您只需创建另一个 cons 单元格，其头部是新项目，尾部是旧列表。
然而，附加一个项目要昂贵得多，因为创建单个 cons 单元格是不够的。您必须创建一个与旧列表相同的列表，除了最后一个 cons 单元格的尾部必须是一个新的 cons 单元格，其头部是新元素，尾部是空列表。所以你不能在不遍历整个列表的情况下追加到列表，即 O(n)。
于 2010-07-12T22:40:36.137 回答