Haskell - 探索とソート(マージソート(merge sort)とそのテスト)

すごいHaskellたのしく学ぼう!
(オーム社)
Miran Lipovača (著)
田中 英行 村主 崇行 (翻訳)
[Kindle版]

開発環境

• OS X Mavericks - Apple(OS)
• BBEdit - Bare Bones Software, Inc., Emacs (Text Editor)
• Haskell (純粋関数型プログラミング言語)
• GHC (The Glasgow Haskell Compiler) (処理系)
• The Haskell Platform (インストール方法、モジュール等)

初めてのコンピュータサイエンス(Jennifer Campbell、Paul Gries、Jason Montojo、Greg Wilson(著)長尾 高弘(翻訳))の11章(探索とソート)、11.7(練習問題)、11-9.をHaskellで解いてみる。

その他参考書籍

• プログラミングHaskell (オーム社) Graham Hutton(著) 山本 和彦(翻訳)
• Real World Haskell―実戦で学ぶ関数型言語プログラミング (オライリージャパン) Bryan O'Sullivan John Goerzen Don Stewart(著) 山下 伸夫 伊東 勝利 株式会社タイムインターメディア(翻訳)

11.7(練習問題)、11-9.

コード(BBEdit)

Sample.hs

{-# OPTIONS -Wall -Werror #-}

main :: IO ()
main = mapM_ putStrLn $ map (\(a, b, c) -> if mergeSort b == c then
                                               show True
                                           else
                                               a)
                            testList

mergeSort :: (Ord a) => [a] -> [a]
mergeSort = g . map (:[])

g :: (Ord a) => [[a]] -> [a]
g [] = []
g (ns:[]) = ns
g (ns:ms:nns) = g $ nns ++ [merge ns ms]

merge :: (Ord a) => [a] -> [a] -> [a]
merge ns [] = ns
merge [] ms = ms
merge ns ms = f ns ms []

f :: (Ord a) => [a] -> [a] -> [a] -> [a]
f [] [] ls = ls
f [] ms ls = ls ++ ms
f ns [] ls = ls ++ ns
f (n:ns) (m:ms) ls = if n <= m then
                         f ns (m:ms) (ls ++ [n])
                     else 
                         f (n:ns) ms (ls ++ [m])

testList :: [(String, [Int], [Int])]
testList = [("空のリスト", [], []),
            ("要素が1個のリスト", [1], [1]),
            ("要素が2個でソート済のリスト", [1, 2], [1, 2]),
            ("要素が2個で逆順になっているリスト", [2, 1], [1, 2]),
            ("3個の等しい値によるリスト", [3, 3, 3], [3, 3, 3]),
            ("異なる値が1つ混ざっているリスト", [3, 0, 3], [0, 3, 3])]

入出力結果(Terminal, runghc)

$ runghc Sample.hs
True
True
True
True
True
True
$

慣れるまでは{-# OPTIONS -Wall -Werror #-}の記述を消さずに細かく型を指定していくことに。