Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.1k views
in Technique[技术] by (71.8m points)

haskell - how to implement doubly linked lists

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.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...