Haskell - 探索とソート(挿入ソート(insertion 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-2-b.をHaskellで解いてみる。

その他参考書籍

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

11.7(練習問題)、11-2-b.

コード(BBEdit)

Sample.hs

{-# OPTIONS -Wall -Werror #-}

main :: IO ()    
main = do
    print $ fst $ insertionSort l
    putStrLn $ "0: " ++ show l
    mapM_ putStrLn $ map (\(n, x) -> show n ++ ": " ++ show x) $
                         zip ([1..] :: [Integer]) (snd $ insertionSort l)

insertionSort :: (Ord a) => [a] -> ([a], [[a]])
insertionSort ns = f ns [] []

f :: (Ord a) => [a] -> [a] -> [[a]] -> ([a], [[a]])
f [] ns xs = (ns, reverse xs)
f (n:ns) [] xs = f ns (n:[]) ((ns ++ [n]):xs)
f (n:ns) ms xs = f ns (g n ms) ((ns ++ g n ms):xs)

g :: (Ord a) => a -> [a] -> [a]
g a [] = a:[]
g a (n:ns) = if n <= a then
                 n:g a ns
             else
                 a:n:ns

l :: [Int]
l = [6, 5, 4, 3, 7, 1, 2]

入出力結果(Terminal, runghc)

$ runghc Sample.hs
[1,2,3,4,5,6,7]
0: [6,5,4,3,7,1,2]
1: [5,4,3,7,1,2,6]
2: [4,3,7,1,2,5,6]
3: [3,7,1,2,4,5,6]
4: [7,1,2,3,4,5,6]
5: [1,2,3,4,5,6,7]
6: [2,1,3,4,5,6,7]
7: [1,2,3,4,5,6,7]
$

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