プログラミング Haskell 第10章 型とクラスの定義 その5

今日は練習問題の 3, 4 です。

• 3.

data Tree = Leaf Int | Node Tree Tree deriving Show

leafs :: Tree -> Int
leafs (Leaf _) = 1
leafs (Node l r) = (leafs l) + (leafs r)

balanced :: Tree -> Bool
balanced (Leaf _) = True
balanced (Node r l) = abs ((leafs r) - (leafs l)) <= 1 &&
                    (balanced r) && (balanced l)

• 4.

import List

divide :: [Int] -> ([Int], [Int])
divide l = ((take half sl), (drop half sl))
           where
             sl = List.sort l
             half = (div (length l) 2) + (mod (length l) 2)

balance :: [Int] -> Tree
balance [] = error "empty list"
balance (x:[]) = Leaf x
balance xs = Node (balance l) (balance r)
             where (l, r) = divide xs