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)