如何实现双向链表

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块中;你可以把结构分成函数)

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

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

否则,您可能只想使用Zippers,但将它们用于树而不是列表.有关Zippers的更多信息可以在Haskell Wiki上找到.拉链在这种情况下非常适合,因为它们提供了您所追求的确切功能:如果您访问带有拉链的树,您可以访问您正在访问的树部分的"父母",但树本身不必包含父引用.