data Tree a = Leaf a | Fork (Tree a) a (Tree a)
deriving Show
numberTree :: Tree () -> Tree Integer
numberTree tree = fst $ numnum tree 1
where
numnum :: Tree () -> Integer -> (Tree Integer, Integer)
numnum (Leaf ()) n = (Leaf n, n+1)
numnum (Fork l () r) n = (Fork l' ln r', rn)
where
(l',ln) = numnum l n
(r',rn) = numnum r (ln+1)
main :: IO()
main = do
print $ numberTree (Leaf ())
print $ numberTree (Fork (Leaf ()) () (Leaf ()))
print $ numberTree (Fork (Leaf ()) () (Fork (Fork (Leaf ()) () (Leaf ())) () (Leaf ())))