Haskell for Programming Contest

Haskell k2pc

この夏休みにHaskellを勉強してみることにしました。
最近、趣味でプログラミングコンテストの問題を解いていますが、しばらくはHaskellで解いていきたいと思っています。
しばらく、ここにはHaskellの勉強の内容を書いていきます。よろしくお願いします。


HaskellはCなどの手続き型言語や、Javaなどのオブジェクト指向言語とは全く違う、純粋関数型プログラミング言語であるとのこと。

Haskellは基本的に型安全な言語なので、型が他の言語よりも厳密に検査されます。「Aがaの型である」を「A :: a」と表記します。また、関数Bがb0, b1, ..., bnの型のn個の引数を受け取ってcの型を返す場合、Bの型は「B :: b0 -> b1 -> ... -> bn -> c」となります。また型aのリスト（配列）の型は[a]となります。

とりあえず簡単なプログラムを組んでみようと思い、http://k2pc-easy.contest.atcoder.jp/tasks/k2pc001_e1を解いてみました。C++やJavaで書くなら超簡単な問題です。


Haskellには他の言語のようにいくつかの基本的な型があり、Int、Char、Stringなどがあります。今回はIntとStringを使います。

まず、この問題を解くのに必要なのがIOです。入力をプログラムが読み込まなければなりません。

a b c
N

の入力が与えられたとき（0≦a≦1000、≦b≦2000、0≦c≦3000、0≦N≦1000）、これらをそれぞれ対応する整数としてプログラムに認識させます。以下の関数を組み合わせて使います。

  • getLine :: IO String ・・・ 入力を一行読み込む
  • words :: String -> [String] ・・・ 引数の文字列をスペース区切りで分割する
  • read :: String -> a ・・・ Stringの型の引数をaの型に変える

words getLine
とすれば入力「a b c」を「["a", "b", "c"]」のリストに出来そうですが、これはコンパイルエラーになります。wordsは引数の型がStringといっているのに、getLineは型がIO Stringであるためです
。
僕もまだよく理解していませんが、IOを使うと副作用が出る可能性があるため、getLineの戻り値の型はStringではいけないそうです。
よって、Monadを使ったり（参考 : http://www.shido.info/hs/haskell8.html）、fmapという関数を使って、IO String 型をStringに変換します（fmapは仕組みがよく分かってません・・・。関数適用という効果があるらしいです）。

これで、あとは0未満の整数を0に矯正する関数filを書き（関数、条件分岐の書き方などはhttp://www.shido.info/hs/haskell3.htmlが分かりやすい）、以下の関数を使えばこの問題のプログラムは完成です。

  • show :: a -> String ・・・ aの型の引数をString型に変える
  • putStrLn :: String -> IO () ・・・ 引数を出力する
fil n | n <= 0      = 0
		| otherwise = n
 
main = do
	abc <- fmap words getLine
	n <- getLine
	putStrLn $ show (  fil (read (n) - read ( abc !! 0)) ) ++ " " ++ show ( fil (2 * read (n) - read ( abc !! 1) ) ) ++ " " ++ show ( fil (3 * read (n) - read ( abc !! 2)) )

ちなみに「abc !! i」はリストのi番目の要素の取り出しです。
最後の行の$は便利な記法で、
a $ b $ c
は
a ( b( c ) )
を簡略化した記号です。すごく見やすい。

というわけで、以上が初めて書いたHaskellプログラムでした。所要時間は3時間くらい。

まだまだ書き溜めてあるプログラムがいくつかあるので、少しずつ紹介していきます。