> I wonder if it is possible to simulate a doubly linked list in
> Haskell.
Depends on what you mean.
- Using mutable state in a monad you can implement a doubly
linked list directly.
- If you store all the nodes of the doubly linked list in
an array and simulate the pointers with indices into the
array, then you can easily implement this in Haskell using
some kind of extensible persistent array (probably some flavor
of binary tree). [Here you get a logarithmic slowdown
compared to ordinary doubly linked lists.]
- If you want to be able to add/remove things from the front/back
plus be able to splice two lists together, see my implementation
of catenable deques (ICFP'97 or in my book).
- If you also want to be able to have a "cursor" into the middle
of the list where you can make changes, you can implement this
as a pair of catenable deques, where the first deque represents
the part before the cursor and the second deque represents the
part after the cursor.
- If you want to allow an arbitrary number of cursors, then
the simulation using an extensible persistent array is probably
your best bet.
Chris
