方案:持续访问列表的结尾？

Question

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

据我所知,scheme默认情况下不提供此功能(即不断访问列表的末尾).要清楚,我不是在寻找"指针"功能.我理解这在计划中是非惯用的,并且(我认为)是不必要的.

有人可以1)证明能够提供一种方法来在恒定的时间内附加两个列表或2)向我保证这在默认情况下已经可以在方案或球拍中使用(例如,告诉我,append如果我是一个实际上是一个常量操作不这么认为)？

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

Answer 1

标准Lisp列表不能在常量时间内追加.

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

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

换句话说,缺乏简单的追加是一种权衡,可以更容易地编写递归算法.大多数函数式程序员都会同意这是正确的权衡,因为在纯函数意义上附加意味着你必须复制除最后一个列表之外的所有单元格 - 所以它不再是O(1).

ETA反映了OP的编辑

您可以创建一个队列,但行为相反:您向后面添加元素,并检索前面的元素.如果您愿意使用它,这样的数据结构很容易在Scheme中实现.(是的,很容易在不变的时间附加两个这样的队列.)

Racket也有类似的队列数据结构,但它使用记录类型而不是cons单元格,因为Racket cons单元是不可变的.您可以使用queue->list(在O(n)复杂度下)将队列转换为列表,以便在需要折叠时使用.

Answer 2

你想要一个FIFO队列.user448810提到了纯功能FIFO队列的标准实现.

您对失去"Lisp列表的关键优势"的担忧需要稍微解压缩:

您可以在Lisp中为自定义数据结构编写组合子.如果实现队列类型,则可以轻松地为其编写折叠,映射,过滤等.
然而,Scheme缺乏提供可以在多种序列类型上工作的多态序列功能的领域.您经常最终(a)将数据结构转换回列表以使用丰富的列表函数库,或者(b)为您的自定义类型实现各种这些函数的自己版本.
这非常令人遗憾,因为单链表虽然对大量计算非常有用,但并不是一个全部的数据结构.
但更糟糕的是,有很多Lisp人喜欢假装列表是一种"通用数据类型",可以而且应该用于表示任何类型的数据.我把Lisp编程为生活,哦,天哪,我讨厌这些人生成的代码; 我把它称为"Lisp程序员的疾病",并且经常不得不进入并修复很多n ^ 2,它们使用列表来表示集合或词典来使用哈希表或搜索树.不要落入那个陷阱.为手头的任务使用适当的数据结构.您始终可以使用Racket中的记录类型和模块构建自己的不透明数据类型; 您通过导出类型而不是记录类型的字段访问器使它们变得不透明(而是导出类型的面向用户的操作).