how to implement doubly linked lists

by

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.

More Related Contents:

  1. Why give me error? [closed]
  2. What is the difference between . (dot) and $ (dollar sign)?
  3. Good examples of Not a Functor/Functor/Applicative/Monad?
  4. Haskell ranges and floats
  5. Defining a function by equations with different number of arguments
  6. :sprint for polymorphic values?
  7. Small Haskell program compiled with GHC into huge binary
  8. Multi-line commands in GHCi
  9. Writing foldl using foldr
  10. What does the exclamation mark mean in a Haskell declaration?
  11. Haskell function composition operator of type (c→d) → (a→b→c) → (a→b→d)
  12. Haskell: Lists, Arrays, Vectors, Sequences
  13. What are “n+k patterns” and why are they banned from Haskell 2010?
  14. How do I write, “if typeclass a, then a is also an instance of b by this definition.”
  15. Haskell read raw keyboard input
  16. Applicative functor evaluation is not clear to me
  17. Expressing do block using only monadic bind syntax
  18. Why do we need monads?
  19. What constitutes a fold for types other than list?
  20. Defining a new monad in haskell raises no instance for Applicative
  21. How to make a CAF not a CAF in Haskell?
  22. Check whether a type is an instance of Show in Haskell at runtime?
  23. Integral operators quot vs. div
  24. How to interpret bind/>>= of the function instance?
  25. Why should Applicative be a superclass of Monad?
  26. withFile vs. openFile
  27. In what sense is the IO Monad pure?
  28. Why does OCaml sometimes require eta expansion?
  29. Explanation of “tying the knot”
  30. Return specific type within Haskell

Leave a Comment