category-theory-8-average.hs

-- cons
sum' :: Num a => [a] -> a
sum' [] = 0
sum' (x:xs) = x + sum' xs

length' :: Num a => [a] -> a
length' [] = 0
length' (x:xs) = 1 + length' xs

avg' :: (Fractional b) => [b] -> b
avg' ls = sum' ls / length' ls

-- foldr
sum'' :: (Num b, Foldable t) => t b -> b
sum''    = foldr (\a x -> a + x) 0

length'' :: (Num b, Foldable t) => t a -> b
length'' = foldr (\a x -> x + 1) 0

avg'' :: (Fractional b, Foldable t) => t b -> b
avg'' ls = let
  (s, l) = foldr (\a (x,y) -> (a + x, y + 1)) (0, 0) ls
  in s / l

-- Fokkinga example: steep
steep [] = True
steep (x:xs) = x > sum(xs) && steep(xs)

steep' [] = True
steep' ls = let
  (first, _) = foldr (\a (b,s) -> (a > s && b, a+s)) (True, 0) ls
  in first

-- is Balacned Tree ?
-- reference: http://www.geocities.jp/m_hiroi/func/haskell10.html
data Tree a = Nil | Node a (Tree a) (Tree a) deriving Show

blahTree0 = Node 0 (Nil) (Nil)
blahTree1 = Node 0 (Node 0 (Nil) (Nil)) (Nil)
blahTree2 = Node 0 (Node 0 (Nil) (Nil)) (Node 0 (Nil) (Node 0 (Nil) (Nil)))
blahTree3 = Node 0 (Node 0 (Nil) (Nil)) (Node 0 (Nil) (Nil))
blahTree4 = Node 0 (Node 0 (Node 0 (Node 0 (Nil) (Nil)) (Nil)) (Nil)) (Nil)

-- straight forward recursive
countNode :: (Num b) => Tree a -> b
countNode Nil = 0
countNode (Node a b c) = 1 + countNode(b) + countNode(c)

isBalancedTree :: Tree a -> Bool
isBalancedTree Nil = True
isBalancedTree (Node a b c) = let
  (n, m) = (countNode(b), countNode(c))
  in (3*(m+1) >= n + 1) && (3*(n+1) >= m + 1) && isBalancedTree(b) && isBalancedTree(c)