list - 方案:对列表末尾的持续访问？

Question

在 C 中，您可以拥有一个指向单向链表的第一个和最后一个元素的指针，从而提供对列表末尾的恒定时间访问。因此，可以在恒定时间内将一个列表附加到另一个列表。

据我所知，默认情况下，scheme 不提供此功能(即对列表末尾的持续访问)。需要明确的是，我不是在寻找“指针”功能。我知道这在计划中是非惯用的，并且(我认为)是不必要的。

有人可以 1) 展示提供一种在恒定时间内附加两个列表的方法的能力，或者 2) 向我保证这在方案或 Racket 中默认已经可用(例如，告诉我 append 实际上是一个常数操作，如果我不这么认为是错误的)？

编辑:
我应该让自己更清楚。我正在尝试创建一个可检查的队列。我想要一个列表，我可以 1) 在恒定时间内推到前面，2) 在恒定时间内从后面弹出，3) 使用 Racket 的 foldr 或类似的东西(Lisp 右折叠)迭代。

Answer 1

标准 Lisp 列表不能在恒定时间内附加到。

但是，如果您制作自己的列表类型，则可以做到。基本上，您可以使用记录类型(或只是一个 cons 单元格)---让我们称之为“标题”---它保存指向列表头部和尾部的指针，并在每次有人添加到列表时更新它.

但是，请注意，如果您这样做，列表将不再具有结构归纳性。即，较长的列表不仅仅是较短列表的扩展，因为涉及额外的“标题”。因此，你失去了 Lisp 算法的很大一部分简单性，它涉及在每次迭代时递归到列表的 cdr 中。

换句话说，缺乏简单的附加是使递归算法更容易编写的权衡。大多数函数式程序员会同意这是正确的权衡，因为在纯函数意义上的追加意味着您必须复制除最后一个列表之外的所有单元格中的每个单元格——因此无论如何它不再是 O(1)。

ETA 反射(reflect) OP 的编辑

您可以创建一个队列，但行为相反:将元素添加到后面，并在前面检索元素。如果您愿意使用它，这样的数据结构是 easy to implement in Scheme 。 (是的，在恒定时间内添加两个这样的队列很容易。)

Racket 也有类似的 queue data structure ，但它使用记录类型而不是 cons 单元，因为 Racket cons 单元是不可变的。您可以在需要折叠时使用 queue->list(复杂度为 O(n))将队列转换为列表。