何かを書き留める何か

数学や読んだ本について書く何かです。最近は社会人として生き残りの術を学ぶ日々です。

Haskellでマージソート

これまた「プログラミングHaskell」の演習問題から。比較のためにクイックソートも記載した。

merge :: Ord a => [a] -> [a] -> [a]
merge xs [] = xs
merge [] ys = ys
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

qsort :: Ord a => [a] -> [a]
qsort []  = []
qsort (x : xs) = qsort smaller ++ [x] ++ larger
                 where
                   smaller = [a | a <- xs, a <= x]
                   larger  = [b | b <- xs, b > x]

実行例は以下の通り。

$ ghci 6-5.hs
GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Main             ( 6-5.hs, interpreted )
Ok, modules loaded: Main.
*Main> msort [3,1,4,5,2]
[1,2,3,4,5]
*Main> qsort [3,1,4,5,2]
[1,2,3,4,5]
*Main>

HaskellでもPythonみたいにタプルのアンパックができるのは便利でよい。