Jan Brosius writes:
> I wonder if it is possible to simulate a doubly linked list in Haskell.
Interesting question. Usually you don't need any kind of "double-linkedness"
because there are no imperative effects, but sometimes it is useful to
simulate something analogous. The idea is to treat "locations" in a list
rather than the list as a whole, a location in xs being some tail of xs; this
is done indirectly by modelling the context as a path from the start of the
list, along with the elements contained along the path.
type Loc a = ([a],[a])
first xs = ([],xs)
last xs = (reverse xs, [])
next (ys,x:xs) = (x:ys,xs)
back (y:ys,xs) = (ys,y:xs)
So you see, for a list, the context of a location happens to be representable
as another list, with its elements reversed. However, this idea can be
generalized to arbitrary first-order datatypes, and in general the contexts
aren't isomorphic to the datatype in question. For example, suppose we have a
binary tree:
data Tree a = Leaf a | Fork (Tree a) (Tree a)
Its contexts look like this
data Cxt a = Top | L (Cxt a) (Tree a) | R (Tree a) (Cxt a)
and a location, as usual, is
type Loc a = (Cxt a, Tree a)
with navigation functions like
top t = (Top, t)
left (c, Fork l r) = (L c r, l)
right (c, Fork l r) = (R l c, r)
up (L c r, l) = (c, Fork l r)
up (R l c, r) = (c, Fork l r)
Gerard Huet published an article about this technique, which he called "The
Zipper" because of the way it inverts a data structure as you descend into it,
in the Journal of Functional Programming (I think in 1998, but I'm too lazy to
check).
Incidentally, one way to make use of this is to elaborate the context by
adding some state which depends on the location. For example, for trees you
could keep track of the depth; for terms, the free variables; etc.
However, although I think this is a neat trick, I admit I have not found much
use for it in Haskell programs. For example, one problem is that the
navigation functions are necessarily partial. It would be nicer in a language
with some subtyping or something which could ensure that you can only use,
say, "left" when you're not at a leaf. Another issue is that if you use the
contexts to track state, you really want some kind of inheritance to be able
to quickly define variants of the context datatype and its associated
functions.
In short, what you want is an OO language. For Haskell, using monads or arrows
to keep track of the computation state is more appropriate, I think.
--
Frank Atanassow, Dept. of Computer Science, Utrecht University
Padualaan 14, PO Box 80.089, 3508 TB Utrecht, Netherlands
Tel +31 (030) 253-1012, Fax +31 (030) 251-3791
