Herewith the comp.lang.functional version of my article. I may have tidied it up a little for the Wiki; if so, those changes are lost. Let it hereby enter the Haskell List archive!
The following message is a courtesy copy of an article that has been posted as well. Matti Nykanen <[EMAIL PROTECTED]> writes: > 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:[EMAIL PROTECTED] : :---------------------------------------------------------------------:
-- : Keith Wansbrough, MSc, BSc(Hons) (Auckland) -------------------: : PhD Student, Computer Laboratory, University of Cambridge, UK. : : Native of Antipodean Auckland, New Zealand: 174d47'E, 36d55'S. : : http://www.cl.cam.ac.uk/users/kw217/ mailto:[EMAIL PROTECTED] : :----------------------------------------------------------------:
