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

问题描述

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

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.

推荐答案

在 Haskell 中拥有双向链表并不实际，因为您必须一次构建它.

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

例如，假设您有一个列表 [1, 2, 3, 4, 5] 想要进行双向链接.现在，让我们想象一下列表是如何表示的:

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

由于惰性求值，这在 Haskell 中是可能的；这种策略被称为打结"(而且您不必将其全部放在一个let 块中；您可以将构造分解为函数)

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)

但是，换句话说，要创建一个双向链表，您需要一次构建它，如果您想更改其中的任何部分，则需要使用 Zipper 或者每次都制作一个完整的副本.

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.

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

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.

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

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屋！