tail_recursive.hs

data Node = Leaf Integer | Branch Node Node

depth tree = case tree of
    Leaf _ -> 1
    Branch a b -> 1 + max (depth a) (depth b)

depth_tail tree = depth' tree id
    where
        depth' (Leaf _) cont = cont 1
        depth' (Branch a b) cont =
            depth' a (\c ->
                depth' b (\d ->
                    cont(max (c + 1) (d + 1))
                )
            )

main = do
    print $ depth (Branch (Leaf 2) (Leaf 1))
    print $ depth_tail (Branch (Leaf 2) (Leaf 1))
    print $ depth_tail (Branch (Leaf 2) (Branch (Leaf 2) (Leaf 1)))
    print $ depth_tail (Branch (Branch (Leaf 2) (Leaf 1)) (Leaf 1))
    print $ depth_tail (Branch (Branch (Leaf 2) (Branch (Branch (Leaf 2) (Leaf 1)) (Leaf 1))) (Leaf 1))
    print $ depth (Branch (Branch (Leaf 2) (Branch (Branch (Leaf 2) (Leaf 1)) (Leaf 1))) (Leaf 1))
    print $ depth (Branch (Leaf 1) (Branch (Leaf 2) (Branch (Branch (Leaf 2) (Leaf 1)) (Leaf 1))))