Haskell - 探索とソート(挿入ソート、選択ソートの比較、入れ替えの回数)

すごい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-6.をHaskellで解いてみる。

その他参考書籍

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

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

コード(BBEdit)

Sample.hs

{-# OPTIONS -Wall -Werror #-}

main :: IO ()
main = mapM_ putStrLn $
    map (\(t, (_, a, b)) -> t ++ ": " ++ show a ++ ", " ++ show b)
        [(t, s ns)| (t, s) <- [("選択", selectionSort), ("挿入", insertionSort)],
                    ns <- ([[0, 1..9], [9, 8..0], take 10 [0, 0..]] :: [[Int]])]

selectionSort :: (Ord a) => [a] -> ([a], Int, Int)
selectionSort ns = f [] ns 0 0

f :: (Ord a) => [a] -> [a] -> Int -> Int -> ([a], Int, Int)
f ns [] cmp cp = (ns, cmp, cp)
f ns (m:[]) cmp cp = (ns ++ [m], cmp, cp)
f ns ms cmp cp =
    let ((a, b), cmp', cp') = findMin ms cmp cp
    in f (ns ++ [a]) b cmp' cp'

findMin :: (Ord a) => [a] -> Int -> Int -> ((a, [a]), Int, Int)
findMin (n:[]) cmp cp = ((n, []), cmp, cp)
findMin (n:ns) cmp cp = g n ns [] cmp cp
findMin [] _ _ = error "空っぽ"

g :: (Ord a) => a -> [a] -> [a] -> Int -> Int -> ((a, [a]), Int, Int)
g x [] ms cmp cp = ((x, ms), cmp, cp)
g x (n:ns) ms cmp cp = if n < x then
                           g n ns (x:ms) (cmp + 1) (cp + 1)
                       else
                           g x ns (n:ms) (cmp + 1) cp

insertionSort :: (Ord a) => [a] -> ([a], Int, Int)
insertionSort ns = h [] ns 0 0

h :: (Ord a) => [a] -> [a] -> Int -> Int -> ([a], Int, Int)
h ns [] cmp cp = (ns, cmp, cp)
h ns (m:ms) cmp cp =
    let (xs, cmp', cp') = i m ns [] cmp cp
    in h xs ms cmp' cp'

i :: (Ord a) => a -> [a] -> [a] -> Int -> Int -> ([a], Int, Int)
i x [] ns cmp cp = (x:ns, cmp, cp)
i x ns ms cmp cp =
    let a = last ns
        as = init ns
    in if a >= x then
           i x as (a:ms) (cmp + 1) (cp + 1)
       else
           (ns ++ x:ms, (cmp + 1), cp)

入出力結果(Terminal, runghc)

$ runghc Sample.hs
選択: 45, 20
選択: 45, 25
選択: 45, 0
挿入: 9, 0
挿入: 45, 45
挿入: 45, 45
$

Pythonの時みたいなindexの操作ではなく、パターンマッチを使ってるから、回数が異なった結果に。(回数をカウントするのが目的だから、要素の追加がリストの先頭とか末尾とかはあえて考慮しないでソートしてみた。)

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