Haskell - 探索とソート(バブルソート(bubble 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-4.をHaskellで解いてみる。

その他参考書籍

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

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

コード(BBEdit)

Sample.hs

{-# OPTIONS -Wall -Werror #-}

main :: IO ()    
main = do
    putStrLn "バブルソートの過程"
    print l
    mapM_ print $ snd $ bubbleSort1 l
    putStrLn "test"
    mapM_ putStrLn $ map (\(a, b) -> if test b then "True" else a) testList

test :: ([Int], [Int]) -> Bool
test (ns, ms) = if bubbleSort ns == ms then True else False

testList :: [(String, ([Int], [Int]))]
testList = [("empty", ([], [])),
            ("one", ([1], [1])),
            ("two ordered", ([1, 2], [1, 2])),
            ("to reversed", ([2, 1], [1, 2])),
            ("three identical", ([3, 3, 3], [3, 3, 3])),
            ("three split", ([3, 0, 3], [0, 3, 3]))]

bubbleSort :: [Int] -> [Int]
bubbleSort [] = []
bubbleSort ns = f (last ns) (init ns) [] []

f :: Int -> [Int] -> [Int] -> [Int] -> [Int]
f x [] [] ls = ls ++ [x]
f x [] ms ls = f (last ms) (init ms) [] (ls ++ [x])
f x ns ms ls =
    let n = last ns
        ks = init ns
    in if x < n then
           f x ks (n:ms) ls
       else
           f n ks (x:ms) ls

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

-- 過程を出力する用
bubbleSort1 :: [Int] -> ([Int], [[Int]])
bubbleSort1 [] = ([], [])
bubbleSort1 ns = g (last ns) (init ns) [] ([], [])

g :: Int -> [Int] -> [Int] -> ([Int], [[Int]]) -> ([Int], [[Int]])
g x [] [] (ls, xs) = (ls ++ [x], reverse xs)
g x [] ms (ls, xs) = g (last ms) (init ms) [] (ls ++ [x], xs)
g x ns ms (ls, xs) =
    let n = last ns
        ks = init ns
    in if x < n then
           g x ks (n:ms) (ls, (ls ++ ks ++ [x] ++ n:ms):xs)
       else
           g n ks (x:ms) (ls, (ls ++ ks ++ [n] ++ x:ms):xs)

入出力結果(Terminal, runghc)

$ runghc Sample.hs
バブルソートの過程
[6,5,4,3,7,1,2]
[6,5,4,3,7,1,2]
[6,5,4,3,1,7,2]
[6,5,4,1,3,7,2]
[6,5,1,4,3,7,2]
[6,1,5,4,3,7,2]
[1,6,5,4,3,7,2]
[1,6,5,4,3,2,7]
[1,6,5,4,2,3,7]
[1,6,5,2,4,3,7]
[1,6,2,5,4,3,7]
[1,2,6,5,4,3,7]
[1,2,6,5,4,3,7]
[1,2,6,5,3,4,7]
[1,2,6,3,5,4,7]
[1,2,3,6,5,4,7]
[1,2,3,6,5,4,7]
[1,2,3,6,4,5,7]
[1,2,3,4,6,5,7]
[1,2,3,4,6,5,7]
[1,2,3,4,5,6,7]
[1,2,3,4,5,6,7]
test
True
True
True
True
True
True
$

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