gistfile1.txt

-- 二分木が平衡状態であるという事を,各節点で 3(m + 1) ≧ n + 1 かつ 3(n + 1) ≧ m + 1 が成り立つ事とします。(n,mは左右の部分木の節点数)
-- 二分木が平衡状態か否かを判定する関数を相互再帰定理に基いて導出して下さい。
-- https://gist.github.com/eldesh/5970931
data Tree a = Leaf a | Node (Tree a) a (Tree a) deriving(Show, Eq)

instance Foldable Tree where
    foldr f z (Leaf x) = f x z
    foldr f z (Node l k r) = foldr f (f k (foldr f z r)) l


countNodes :: Tree a -> Integer
countNodes (Leaf _) = 1
countNodes (Node l _ r) = countNodes l + countNodes r + 1

isBalanced' :: Tree a -> Bool
isBalanced' (Leaf _) = True
isBalanced' (Node l _ r) = 
    let (n, m) = (countNodes l, countNodes r) 
    in 3 * (m + 1) >= n + 1 && 3 * (n + 1) >= m + 1 && isBalanced' l && isBalanced' r

-- isBalanced :: Tree a -> Bool
-- isBalanced fst . foldr f c
--    where
--        c =  (True, 1)
--         f (lb, n) (rb, m) = (3 * (m + 1) >= n + 1 && 3 * (n + 1) >= m + 1 && lb && rb, n + m)