如何实现双向链表

Question

在Haskell中是否可以有双向链表？实现双向链表的最佳解决方案是什么？我正在实现一个场景图，其中每个小部件都有一个父级和一个子级，向上和向下遍历对于查找非常有利。

- Jonathan Dunlap

---

抱歉有些迂腐，但在我看来，将Haskell的列表称为“链表”，或者在纯函数编程的上下文中谈论“双向链表”，会带入很多命令式的负担（指针、破坏性更新），从而混淆事情。 - jberryman

与您的目标相关，即使不是直接回答您的问题... 在论文“巨大数据但小程序”（http://eprints.whiterose.ac.uk/5000/）中实现了一个场景图 - 该代码应该仍然可以公开获取，尽管它从未被放在Hackage上。遗憾的是，似乎没有太多关于使用函数式编程涵盖这个领域的已发表研究，这真是一个遗憾，因为这是一个很棒的主题。 - stephen tetley

与其使用双向链表，用Haskell编程时更容易将数据存储为单向树，并使用“zipper”来遍历它。具体请参见：http://learnyouahaskell.com/zippers。 - rampion

https://www.youtube.com/watch?v=-HZ4bo_USvE - leftaroundabout

Answer 1

在Haskell中使用双向链表并不实用，因为你必须一次性构建整个链表。

例如，假设你有一个列表[1, 2, 3, 4, 5]，你想要将其变成双向链表。现在，让我们想象一下该列表的表示方式：

data DoubleList a
  = LeftEnd  a (DoubleList a)
  | Middle   a (DoubleList a) (DoubleList a)
  | RightEnd a (DoubleList a)

（我为简单起见使用了两个不同的构造函数）

要构建上面的列表，您首先必须构造第一个元素：

let e1 = LeftEnd  1 ...

但是要构建第一个元素，你已经需要有第二个元素了：

let e1 = LeftEnd  1 e2
    e2 = Middle   2 e1 ...

对于第二个元素，你需要第三个元素以此类推：

let e1 = LeftEnd  1 e2
    e2 = Middle   2 e1 e3
    e3 = Middle   3 e2 e4
    e4 = Middle   4 e3 e5
    e5 = RightEnd 5 e4

在 Haskell 中，由于惰性求值，可以实现这一点；这种策略称为“打结”（你不必真的把它们全部放在一个 let 块中；你可以将构造分成多个函数）。

换句话说，要创建一个双向链表，需要一次性构建整个链表，如果想要更改任何部分，就需要使用Zipper或每次完全复制它。

我建议使用经过优化的基于finger-tree的顺序存储实现 Data.Sequence, 它支持非常快的插入、删除和迭代，同时仍然是一个纯函数数据结构。

否则，您可能只想使用 Zippers，但是将它们用于树而不是列表。关于Zippers的更多信息可以在Haskell Wiki上找到。Zippers非常适合这种情况，因为它们提供了您想要的精确功能：如果您使用 Zipper 访问树，您将获得访问部分树的“父级”的访问权限，但树本身不必包含父引用。

- dflemstr

---

关于从列表（[a]）构建双向链表，这里有一个代码片段：create函数。可参考链接：http://rosettacode.org/wiki/Doubly-Linked_List_%28traversal%29#Haskell - Vitus

Data.Sequence不错！现在有了一个有趣的类型！同时快速访问列表的两端，这正是我想要的。 - JonnyRaa

@Dmitry 不，单向链表可以通过 O(1) 的 (:)（cons）逐个构建元素。 - Blaisorblade

@Blaisorblade 对不起，回想起来，我的评论完全没有意义。 - Dmytro

Answer 2

由于 Haskell 通常没有面向对象的对象，因此认为数据具有自我意识是很奇怪的。需要注意的是，在 Haskell 数据类型中通常不使用聚合，而是更喜欢组合。

您可能想查看 XMonad，以查看它们的设计是否符合您的需求（代码令人惊讶地易读）。

您还可以重新构建设计，使其永远不需要向上查找（例如，通过传递子级“回调”）。

您还可以尝试为整个图形编写一个 zipper。

- Alex R

Answer 3

一个双向链表并不是一个数据类型，而是一种实现细节。我猜您想要的是一种类似列表的数据结构，可以高效地向左和向右移动。这种数据结构是列表的拉链，仅仅是一对列表。前缀以相反的顺序表示。要向左/右移动，只需将后缀列表的头部移到前缀上，反之亦然。

- Dan Ghica

---

这并不完全正确。双向链表可以形成一个FIFO队列，其队列/出队操作的时间复杂度为O(1)，但是使用Zipper实现相同操作的时间复杂度却是每次在队列和出队之间切换时都要O(n)。你无法通过任何实际上类似于双向链表的东西（非IO的Haskell）来满足双向链表的大O要求，并且它不会是除了一个不能扩展的单个冻结列表之外的其他任何东西。Sequence提供了正确的操作，但它实际上是一个聪明的树，而不是一个列表。您可以使用类似于DLList的差分列表来使其可扩展，但这也不符合正确的大O要求。 - Steven Armstrong