Q: constructing a data structure incrementally?
Matti Nykanen
from Scheme to Haskell. Sorry if this is a FAQ:
I recently came across an algorithm that constructs a binary tree
using single _but not immediate_ assignments. By this I mean that it
attaches a newly created node into the existing tree, but leaves the
children of the totally unspecified. Later the algorithm returns to
fill in the missing pieces.
I tried to write it in Haskell, but couldn't. If I create a node, I
have to give its children some values to start with, and those cannot
be changed later. I don't think uniqueness types (from, e.g., Clean)
help here, because the partially constructed node is referred to by
two places: its parent in the tree, and the "to do" list of the
algorithm for the unfinished nodes.
In logic programming, I would create the new node with something like
"node(Datum,_,_)", which creates fresh uninstantiated variables '_'
for the left and right subtrees. These variables would then get bound
(once) when the algorithm returns to complete this node.
But how can this "delayed binding" be implemented in a pure functional
language like Haskell? Or are there some standard techniques for
converting such algorithms into functional ones? The dreaded "M-word",
perhaps?
Keith Wansbrough
> I recently came across an algorithm that constructs a binary tree
> using single _but not immediate_ assignments. By this I mean that it
> attaches a newly created node into the existing tree, but leaves the
> children of the totally unspecified. Later the algorithm returns to
> fill in the missing pieces.
>
> I tried to write it in Haskell, but couldn't. If I create a node, I
> have to give its children some values to start with, and those cannot
> be changed later. I don't think uniqueness types (from, e.g., Clean)
> help here, because the partially constructed node is referred to by
> two places: its parent in the tree, and the "to do" list of the
> algorithm for the unfinished nodes.
The solution to this is a little trick called `tying the knot'.
Remember that Haskell is a lazy language. A consequence of this is
that while you are building the node, you can set the children to the
final values straight away, even though you don't know them yet! It
twists your brain a bit the first few times you do it, but it works
fine.
Here's an example (possibly topical!). Say you want to build a
circular, doubly-linked list, given a standard Haskell list as input.
The back pointers are easy, but what about the forward ones?
data DList a = DLNode (DList a) a (DList a)
mkDList :: [a] -> DList a
mkDList [] = error "must have at least one element"
mkDList xs = let (first,last) = go last xs first
in first
where go :: DList a -> [a] -> DList a -> (DList a, DList a)
go prev [] next = (next,prev)
go prev (x:xs) next = let this = DLNode prev x rest
(rest,last) = go this xs next
in (this,last)
takeF :: Integer -> DList a -> [a]
takeF 0 _ = []
takeF (n+1) (DLNode _ x next) = x : (takeF n next)
takeR :: Show a => Integer -> DList a -> [a]
takeR 0 _ = []
takeR (n+1) (DLNode prev x _) = x : (takeR n prev)
(takeF and takeR are simply to let you look at the results of mkDList:
they take a specified number of elements, either forward or backward).
The trickery takes place in `go'. `go' builds a segment of the list,
given a pointer to the node off to the left of the segment and off to
the right. Look at the second case of `go'. We build the first node
of the segment, using the given prev pointer for the left link, and
the node pointer we are *about* to compute in the next step for the
right link.
This goes on right the way through the segment. But how do we manage
to create a *circular* list this way? How can we know right at the
beginning what the pointer to the end of the list will be?
Take a look at mkDList. Here, we simply take the (first,last)
pointers we get from `go', and *pass them back in* as the next and
prev pointers respectively, thus tying the knot. This all works
because of lazy evaluation.
Hope this helps.
--KW 8-)
--
: Keith Wansbrough, MSc, BSc(Hons) (Auckland) ------------------------:
: PhD Student, Computer Laboratory, University of Cambridge, England. :
: (and recently of the University of Glasgow, Scotland. [><] ) :
: Native of Antipodean Auckland, New Zealand: 174d47' E, 36d55' S. :
: http://www.cl.cam.ac.uk/users/kw217/ mailto:kw...@cl.cam.ac.uk :
:---------------------------------------------------------------------: