haskell - 如何实现双向链表

Question

是否有可能在 Haskell 中有一个双向链表，实现它们的理想解决方案是什么？我正在实现一个场景图，其中每个小部件都有一个父级和一个子级，向上和向下查看图形是有益的。

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 block 中；您可以将结构划分为函数)

但是，换句话说，要创建一个双向链表，你需要一次构建它，如果你想改变它的任何部分，你要么需要使用Zipper。或者每次都制作一份完整的副本。

我建议改用 Data.Sequence ，这是一个优化的基于手指树的顺序存储实现。它支持非常快速的插入、删除和迭代，同时仍然是一个纯粹的函数式数据结构。

否则，您可能只想使用 zipper ，但将它们用于树而不是列表。有关 zipper 的更多信息，请访问 Haskell Wiki。 . Zipper 非常适合这种情况，因为它们提供了您所追求的确切功能:如果您使用 Zipper 访问一棵树，您可以访问您正在访问的树部分的“ parent ”，但树本身不必包含父引用。