category-theory-8-balanced.hs

import Debug.Trace

-- Folable example
-- https://hackage.haskell.org/package/base-4.7.0.0/docs/Data-Foldable.html
data Tree = Leaf | Node (Tree) (Tree) deriving Show

countNode :: Tree -> Int
countNode Leaf = 0
countNode (Node l r) = 1 + countNode(l) + countNode(r)

isBalancedTree Leaf = True
isBalancedTree (Node l r) = let
  (m, n) = (countNode l, countNode r)
  in trace("(m,n)" ++ show (m,n)) $ (3*(m+1)>=n+1) && (3*(n+1)>=m+1) && isBalancedTree(l) && isBalancedTree(r)

foldTree f z Leaf = z
foldTree f z (Node l r) = f (foldTree f z l) (foldTree f z r)

isBalancedTree' args = let
  z = (True, 0)
  f = (\(lb, m) (rb, n) -> trace ("(m,n)" ++ show (m,n)) $ ((3*(m+1)>=n+1) && (3*(n+1)>=m+1) && lb && rb, m+n+1))
  in foldTree f z args

blahTree0 = Node (Leaf) (Leaf)
blahTree1 = Node (Node (Leaf) (Leaf)) (Leaf)
blahTree2 = Node (Leaf) (Node (Leaf) (Node (Node (Leaf) (Leaf)) (Leaf)))
blahTree3 = Node (Node (Node (Node (Leaf) (Leaf)) (Leaf)) (Leaf)) (Leaf)


-- fact