「プログラミング Haskell」 読書メモ 6 再帰関数

プログラミング Haskell 6章 再帰関数 6.8 練習問題

-- マージソート
merge :: (Ord a) => [a] -> [a] -> [a]
merge [ ]      ys       = ys
merge xs       [ ]      = xs
merge (x : xs) (y : ys) | x <= y    = x : merge xs       (y : ys)
                        | otherwise = y : merge (x : xs) ys

halve :: [a] -> ([a], [a])
halve xs  = splitAt (length xs `div` 2) xs

msort :: (Ord a) => [a] -> [a]
msort [ ] = [ ]
msort [x] = [x]
msort xs  = merge (msort ys) (msort zs)
              where 
                 (ys, zs)  = halve xs

merge は「x が y 以下であれば x を出力に加え再帰」「y が x より小さければ y を出力に加え再帰」と考えるとすっきりする。