[Haskell-beginners] Tying the knot with binary trees

[Michael Schober]

Hi folk,

as an exercise I'm trying to write a binary tree whose nodes also 
include a reference to its parent. I've got the data structure I want to 
use and some helper functions, but there seems to be a bug in insert or 
find or both (although I assume it's in insert).

Here's what I got so far:

data BinTree a = Leaf
   | Node { value :: a
          , left :: BinTree a
          , right :: BinTree a
          , father :: BinTree a
          }

instance Show a => Show (BinTree a) where
   show Leaf = "[]"
   show (Node v l r _) = "(Node " ++ show v
                      ++ " " ++ show l ++ " " ++ show r ++ ")"

mkRoot :: a -> BinTree a
mkRoot value = let root = Node value Leaf Leaf root
                in root

member :: Ord a => a -> BinTree a -> Bool
member v Leaf = False
member v (Node v' l r _) =
   if v == v' then True
   else if v <= v' then member v l
        else member v r

find :: Ord a => a -> BinTree a -> Maybe (BinTree a)
find v Leaf = Nothing
find v n@(Node v' l r _) =
   if v == v' then Just n
   else if v <= v' then find v l
        else find v r

insert :: Ord a => a -> BinTree a -> BinTree a
insert v' Leaf = mkRoot v'
insert v' n@(Node v l r f) = insert' v' n f
   where
     insert' :: Ord a => a -> BinTree a -> BinTree a -> BinTree a
     insert' v' Leaf f' = Node v' Leaf Leaf f'
     insert' v' n@(Node v l r f) f' =
       if v' == v then n
       else if v' <= v
            then let inserted = insert' v' l result
                     result = Node v inserted r f
                 in  result
            else let inserted = insert' v' r result
                     result = Node v l inserted f
                 in  result

I thought this should do the trick, but here's what I get in ghci:

*Main> find 3 (insert 7 (insert 3 (insert 5 Leaf))) >>= return . parent
Just (Node 5 (Node 3 [] []) [])

I'm expecting to see

Just (Node 5 (Node 3 [] []) (Node 7 [] []))

Inserting into an empty tree (i.e. a leaf) works fine, as does mkRoot. 
Also, it seems as inserting an existing value works fine as well - but 
obviously I couldn't test that one exhaustingly so far.

I'm grateful for any pointers towards a solution.

Best regards,
Michael

P.S.: For those unfamiliar with this problem, here is a list of URLs of 
what I read of the subject:
[1] 
http://www.haskell.org/haskellwiki/Tying_the_Knot#Migrated_from_the_old_wiki
[2] 
http://debasishg.blogspot.de/2009/02/learning-haskell-solving-josephus.html
[3] http://blog.sigfpe.com/2006/12/tying-knots-generically.html