プログラミング Haskell 第 10 章練習問題 4

data Tree a = Leaf a | Node (Tree a) (Tree a) deriving Show

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

balance :: [a] -> Tree a
balance []  = error "empty list"
balance [x] = Leaf x
balance lst = Node (balance xs) (balance ys)
  where
    (xs, ys) = split lst

無限リストを食わせてもハングったりしません

> take 10 $ fst $ split [0 ..]
[0,2,4,6,8,10,12,14,16,18]