Hi Michael
When you have a tree with nodes pointing back to their parents then
you essentially have a graph. If you plan to change that graph, then
you have to rebuild *the entire structure*, and there's no going
around that. (And you cant use any of the nodes you pattern match,
only the numbers.)
They say that for this or similar reasons you have to use a zipper,
but I know nothing more about them than this :-)
On Sat, Apr 14, 2012 at 3:04 PM, Michael Schober
Hi again,
thanks for your comments. I've tried your code, but unfortunately that doesn't seem to do the trick.
The problem is that Leaves do not know their
parents, so one solution is to change your data type to this:
data BinTree a = Leaf { lfather :: BinTree a } | Node { value :: a , left :: BinTree a , right :: BinTree a , father :: BinTree a }
then insert would become insert v' (Leaf parent) = let result = Node v' (Leaf result) (Leaf result) parent insert v' n = ...
I was reluctant to this version at first, but I gave it a try. You can find it attached in the alt-linked-tree.hs (I hope it's okay to attach code in files, but the code grew beyond snippetery and this way it's probably more comfortable to test it).
Unfortunately, this doesn't work as well. The actual insert code in this version looks like this:
-- inserts an element into a binary search tree
insert :: Ord a => a -> BinTree a -> BinTree a insert v' (Leaf parent) = let result = Node v' (Leaf result) (Leaf result) parent in result insert v' n@(Node v l r p) = case compare v' v of EQ -> n LT -> let inserted = insert v' l result = Node v inserted r p in result GT -> let inserted = insert v' r result = Node v l inserted p in result
I think the problem here is, that I don't modify the parent, but I cannot seem to wrap my head around it today.
Otherwise you'll have to pass the parent down along the tree as you modify it as such:
insert v' Leaf = mkRoot v' insert v' n@(Node v l r f) = case compare v v' of EQ -> n GT -> (Node v (insert' v' l n) r f) LT -> (Node v l (insert' v' r n) f)
insert' v' Leaf parent = Node v' Leaf Leaf parent insert' v' n@(Node v l r f) parent = case compare v v' of EQ -> n GT -> let result = Node v (insert' v' l result) r parent in result LT -> let result = Node v l (insert' v' r result) parent in result
You require a base case because the first node has no parent to insert with.
This looks pretty much like my code from the beginning, but it doesn't work as well. However, in the meantime I played around with some complexer trees to come across a deficit pattern, but it's really strange. It seems to me as if random subtrees are missing. Sometimes there are siblings as expected, sometimes even children of these siblings, but there never seems to be a working tree.
I have an intuition that it could be the case that I have to modify the parent as well in the recursive case, but I don't know how yet.
Anyway, I'll let it go for the weekend and return to doubly linked lists for now. Maybe implementing more features for those will help me get a better intuition for these kind of problems.
_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
-- Markus Läll