如何实施双向链表 [英] how to implement doubly linked lists

问题描述

是否有可能在Haskell中有一个双向链表，以及实现它们的理想解决方案是什么？我正在实现一个场景图，其中每个窗口小部件都有一个父窗口和一个小窗口，并且在图的上下方向都很有用。

/ div>

在Haskell中有一个双向链表是不现实的，因为你必须一次构建它。

例如，想象一下你有一个名单 [1，2，3，4，5] ，你想双重链接。现在，让我们想象一下如何表示：

  data DoubleList a 
 = LeftEnd a（DoubleList a）
 |中间a（DoubleList a）（DoubleList a）
 | RightEnd a（DoubleList a）
  

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

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

  let e1 = LeftEnd 1 ... 
  

但是要构造第一个元素，您已经需要有第二个元素：

  let e1 = LeftEnd 1 e2 
 e2 =中间2 e1 ... 
  

对于第二个元素，您需要第三个元素等：

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

由于懒惰评估，Haskell可能会这样做;这个策略被称为捆绑结（你不必把它全部放在一个 let 块中;你可以把结构划分成函数）换句话说，要创建一个双向链表，你需要一次构建它，如果你想要改变它的任何部分，你或者需要使用 Zipper 或每次只需制作完整副本。

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

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

Is it possible to have a doubly linked list in Haskell, and what's the ideal solution to implementing them? I'm implementing a scene graph where every widget has a parent as well as a child, and it's beneficial to look both up and down the graph.

解决方案

It isn't really practical to have a doubly linked list in Haskell, because you have to construct it all at once.

For example, imagine that you have a list [1, 2, 3, 4, 5] that you want to make doubly linked. Now, let's imagine how the list is represented:

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

(I use two different constructors for the two ends for simplicity)

To build the list above, you have to first construct the first element:

let e1 = LeftEnd  1 ...

But to construct the first element, you already need to have the second element:

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

And for the second element, you need the third, etc:

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

This is possible to do in Haskell due to lazy evaluation; this strategy is called "tying the knot" (And you don't have to literally put it all in one let block; you can divide up the construction into functions)

But, in other words, to make a doubly-linked list, you need to construct it all at once, and if you ever want to change any part of it, you either need to use a Zipper or just make a complete copy of it every time.

I would recommend to instead use Data.Sequence, which is an optimized finger-tree based sequential storage implementation. It supports very fast insertion, deletion and iteration while still being a purely functional data structure.

Otherwise, you might want to just use Zippers, but use them for Trees instead of for Lists. More information about Zippers can be found on the Haskell Wiki. Zippers would fit very well in this situation, because they offer the exact functionality that you're after: if you visit a tree with a Zipper, you gain access to the "parents" of the part of the tree that you're visiting, but the tree itself doesn't have to contain the parent references.

这篇关于如何实施双向链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！