在Haskell中是否可以有双向链表?实现双向链表的最佳解决方案是什么?我正在实现一个场景图,其中每个小部件都有一个父级和一个子级,向上和向下遍历对于查找非常有利。
在Haskell中是否可以有双向链表?实现双向链表的最佳解决方案是什么?我正在实现一个场景图,其中每个小部件都有一个父级和一个子级,向上和向下遍历对于查找非常有利。
在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
块中;你可以将构造分成多个函数)。Data.Sequence
, 它支持非常快的插入、删除和迭代,同时仍然是一个纯函数数据结构。[a]
)构建双向链表,这里有一个代码片段:create
函数。可参考链接:http://rosettacode.org/wiki/Doubly-Linked_List_%28traversal%29#Haskell - Vitus(:)
(cons)逐个构建元素。 - Blaisorblade由于 Haskell 通常没有面向对象的对象,因此认为数据具有自我意识是很奇怪的。需要注意的是,在 Haskell 数据类型中通常不使用聚合,而是更喜欢组合。
您可能想查看 XMonad,以查看它们的设计是否符合您的需求(代码令人惊讶地易读)。
您还可以重新构建设计,使其永远不需要向上查找(例如,通过传递子级“回调”)。
您还可以尝试为整个图形编写一个 zipper。