28

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

4

3 回答 3

43

在 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，这是一个优化的基于手指树的顺序存储实现。它支持非常快速的插入、删除和迭代，同时仍然是一个纯粹的函数式数据结构。

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

于 2012-04-30T16:03:03.170 回答
1

由于您（通常）在 Haskell 中没有 OO 样式的对象，因此认为数据具有自我意识是很奇怪的。请务必注意，您通常不会在 Haskell 数据类型中使用聚合，而是倾向于组合。

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

您可能还想重新构建您的设计，以便您永远不需要俯视您（例如，通过传递子“回调”）。

您可能还想看看是否可以为整个图表编写一个拉链。

于 2012-05-10T03:35:47.043 回答
0

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

于 2018-11-11T12:54:03.353 回答