練習問題10-4

バランスのとれた木をつくる。

data Tree = Leaf Int | Node Tree Tree deriving Show

balance :: [Int] -> Tree
balance [x] = Leaf x
balance xs = Node (balance ys) (balance zs)
    where (ys,zs) = splitlr xs
              where splitlr ls = splitAt (length ls `div` 2) ls

いちいちリストの長さを数えるのはあほらしいということで、長さを数えずにリスト分割する別解。

要するにsplitを工夫すればいいのね。

ということでマージソートまわりを漁ってみた。

split :: [a] -> ([a],[a])
split []       = ([],[])
split [x]      = ([x],[])
split (x:y:zs) = (x:xs,y:ys)
  where 
    (xs,ys) = split zs

ってのが直感的に分かりやすいかな。

プログラミングHaskell
Graham Hutton
オーム社 / ￥ 2,940 ()
在庫あり。

という感じで、静岡Haskell読書会をやっています。