how to implement doubly linked lists

Question

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.

Dangle

Sorry to be pedantic, but IMHO calling haskell's lists "linked lists" or talking about "doubly-linked lists" in the context of pure FP is dragging a lot of imperative baggage (pointers, destructive updates) into the discussion and confuses things. – Submiss

Pertinent to you goal if not directly to your question... There is a scene graph implemented in the paper "Huge Data but Small Programs" eprints.whiterose.ac.uk/5000 - the code should hopefully still be publicly available though it never got put on Hackage. Sadly there doesn't seem to be much published work covering this domain with functional programming, it's a shame as it's a great topic. – Furore

Rather than using a doubly linked list, it's much easier in haskell to store your data as a singly linked tree and then traverse it with a zipper – Swagger

youtube.com/watch?v=-HZ4bo_USvE – Thrust

Answer 1

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.

Sturgill

As for building doubly-linked list from list ([a]), here's one code snippet; it's the create function. – Lobito

nice one for Data.Sequence! Now there's an interesting type! Also Fast access to both ends of the list which was exactly what I was after – Ashcan

@Dmitry No, a single-linked list can be constructed element by element via O(1) (:) (cons). – Author

@Author My bad, in hindsight my comment made absolutley no sense. – Wrecker

Answer 2

Since you don't (usually) have OO-style objects in Haskell, it's weird to think of data being self-aware. It's important to note that you don't usually make use of aggregation in Haskell data types, favoring composition instead.

You might want to look into XMonad to see if their design matches your needs (the code is surprisingly readable).

You also might want to restructure your design so that you never need to look above you (for example, by passing children "callbacks").

You may also want to see if you can write a zipper for your whole graph.

Isolationist

Answer 3

A doubly linked list is not a data type but an implementation detail. What I presume you want is a list-like data structure where you can move both left and right, efficiently. This data structure is the zipper of a list and is simply a pair of lists. The prefix is represented in reversed order. To move left/right you simply shift the head of the postfix list onto the prefix, and vice versa.

Dye

That's not quite true. A doubly linked list can form a FIFO queue with O(1) for queue/dequeue, but to do that with a Zipper would be O(n) every time you swapped between queue and dequeue. You can't meet the big O requirements for a doubly linked list with anything actually resembling a doubly linked list in (non IO) Haskell and have it be anything other than one single frozen list that you can't extend. Sequence offers the right operations, but it's really a clever tree, not a list. You can use a diff-list like DLList to make it extendable later, but that doesn't have the right big O either. – Karlie