The problem with knot tying exercises is that as soon as you try to update you're in trouble. With an update in a tree with no parent pointers only the spine to get to the node being replaced in the tree need be recreated, all other parts of the tree can simply be referenced as they were before. If you tie the knot on the other hand, every part of the tree must be recreated as soon as you update one node. Bob On 12 Jun 2011, at 23:17, Markus Läll wrote:
Hi Roger,
how that function works depends on what kind of tree you have. Without parent-pointers it's essentially impossible to find the way back to the root. If you have the root, and an instruction of how to get to the leaf, then it's just a matter of prepending nodes to a list until the instruction runs out.
But it actually *is* possible to efficiently have parent-pointers, though it's not obvious when you come into to the language. The technique is called tying the knot. What it basically means is to have circular definitions, e.g having some expression bound to a name and using that name in that same expression. Check it out:
data Tree a = Tree { { left :: Maybe (Tree a) , right :: Maybe (Tree a) }
data PTree a = PTree { pLeft :: Maybe (Tree a) , pRight :: Maybe (Tree a) , pParent :: Maybe (Tree a) }
toP (Tree l r v) = let f :: Tree a -> TreeP -> TreeP f Nothing _ = Nothing f (Just (Tree l r)) parent = let self = TreeP (f l self) (f r self) (Just parent) -- tying the knot here .. in self root = TreeP (f l root) (f r root) Nothing -- .. and here in root
(The Maybes are there to mark lack of children in left and right positions and lack of a parent in the parent position.)
Using this technique you can have all graphy data structures like doubly linked lists and so on. The most simple knot tied is the black hole: x = x , which takes forever to evaluate. And you can explicitly write graphs like:
data Node = Node Char [Node]
g = let a = Node 'A' [b, c] b = Node 'B' [c] c = Node 'C' [g, b, c] in Node 'G' [a]
-- Markus Läll
_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners