[Haskell-beginners] Tying the knot with binary trees

[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.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: alt-linked-tree.hs
Type: text/x-haskell
Size: 3101 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/beginners/attachments/20120414/dfbe8d78/attachment.hs>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: linked-tree.hs
Type: text/x-haskell
Size: 4526 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/beginners/attachments/20120414/dfbe8d78/attachment-0001.hs>