data Zero = Zero
data Suc n = Suc n
nat :: Suc (Suc Zero)
nat = Suc (Suc Zero)
-- data Fork = Fork a a
type Fork a = (a,a)
data BalTree a = Leaf a | Branch (BalTree (Fork a)) deriving Show
{- the 3 smallest values of type BalTree ():
Leaf ()
Branch (Leaf (Fork () ()))
Branch (Branch (Leaf (Fork (Fork () ()) (Fork () ()))))
with type Fork instead of data Fork:
Leaf ()
Branch (Leaf ((),()))
Branch (Branch (Leaf (((),()),((),()))))
-}
-- balanced tree of given height with leafs numbered from zero
balTree :: Int -> BalTree Int
balTree = fst . balTree' 0
balTree' :: Int -> Int -> (BalTree Int, Int)
balTree' x 0 = (Leaf x,x+1)
balTree' x n = (Branch (fork l r),z)
where
(l,y) = balTree' x (n-1)
(r,z) = balTree' y (n-1)
fork :: BalTree a -> BalTree a -> BalTree (Fork a)
fork (Leaf x) (Leaf y) = Leaf (x,y)
fork (Branch x) (Branch y) = Branch (fork x y)