開発環境
- 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-3.をHaskellで解いてみる。
その他参考書籍
- プログラミングHaskell (オーム社) Graham Hutton(著) 山本 和彦(翻訳)
- Real World Haskell―実戦で学ぶ関数型言語プログラミング (オライリージャパン) Bryan O'Sullivan John Goerzen Don Stewart(著) 山下 伸夫 伊東 勝利 株式会社タイムインターメディア(翻訳)
11.7(練習問題)、11-3.
コード(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 (n:ns) = f n [] ns [] f :: Int -> [Int] -> [Int] -> [Int] -> [Int] f x [] [] ls = x:ls f x (n:ns) [] ls = f n [] ns (x:ls) f x ns (m:ms) ls = if x > m then f x (ns ++ [m]) ms ls else f m (ns ++ [x]) ms ls l :: [Int] l = [6, 5, 4, 3, 7, 1, 2] -- 過程を出力する用 bubbleSort1 :: [Int] -> ([Int], [[Int]]) bubbleSort1 [] = ([], []) bubbleSort1 (n:ns) = g n [] ns ([], []) g :: Int -> [Int] -> [Int] -> ([Int], [[Int]]) -> ([Int], [[Int]]) g x [] [] (ls, xs) = (x:ls, reverse xs) g x (n:ns) [] (ls, xs) = g n [] ns ((x:ls), xs) g x ns (m:ms) (ls, xs) = if x > m then g x (ns ++ [m]) ms (ls, (ns ++ [m] ++ x:ms ++ ls):xs) else g m (ns ++ [x]) ms (ls, (ns ++ [x] ++ m:ms ++ ls):xs)
入出力結果(Terminal, runghc)
$ runghc Sample.hs バブルソートの過程 [6,5,4,3,7,1,2] [5,6,4,3,7,1,2] [5,4,6,3,7,1,2] [5,4,3,6,7,1,2] [5,4,3,6,7,1,2] [5,4,3,6,1,7,2] [5,4,3,6,1,2,7] [4,5,3,6,1,2,7] [4,3,5,6,1,2,7] [4,3,5,6,1,2,7] [4,3,5,1,6,2,7] [4,3,5,1,2,6,7] [3,4,5,1,2,6,7] [3,4,5,1,2,6,7] [3,4,1,5,2,6,7] [3,4,1,2,5,6,7] [3,4,1,2,5,6,7] [3,1,4,2,5,6,7] [3,1,2,4,5,6,7] [1,3,2,4,5,6,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 #-}の記述を消さずに細かく型を指定していくことに。
0 コメント:
コメントを投稿