Haskellで競技プログラミング IO編

_この記事は2013年の情報オリンピック夏季セミナーの発表のために

## 動機
Haskellには競技プログラミングに使えるCoolな機能が沢山あります。
パターンマッチやプレースホルダ、パターンガード、柔軟な関数合成などです。

下はAtCoder Regular Contest #14のB問題に対する回答です。
再帰や場合分けがかなりシンプルに書けます。

```haskell:ARC14B
import Control.Monad
import Control.Applicative
import Data.List
 
main :: IO ()
main = do
  n <- readLn
  (w:ws) <- replicateM n getLine
  putStrLn $ case check [w] ws True of
    Nothing -> "DRAW"
    Just True -> "WIN"
    Just False -> "LOSE"
 
check _ [] _ = Nothing
check dict@(la:_) (w:ws) b
  | last la /= head w = Just b
  | w `elem` dict = Just b
  | otherwise = check (w:dict) ws (not b)
```

このコードを見た人は早速Haskellで問題を解いてみたくなってしまうに違いありません。
そして書き始めたとき、ある問題に気づきます。

『入力の受け取り方が分からない(^_^;)』

名著『すごいHaskell楽しく学ぼう』でも入力が出来るようになるのは全15章中の8章とかなり後ろの方です。

これには勿論理由があり、Haskellの素ん晴らしい性質の一つである__参照透過性__と、IOによる副作用を共存させる仕組みとしてモナドというものが用いられますが、こいつがそれなりにややこしく理解に時間が掛かるからなのです。

競技プログラミングに使う分にはモナドを理解する必要は全くなく、いくつかある入力の方法を覚えてしまえばそれで終わりなので、この記事ではそのような方法を紹介したいと思います。

## do記法
まずHaskellでの対話環境であるghciを起動して行入力関数であるgetLine関数の型を調べてみましょう。

```
ghci> :t getLine -- :t はgetLineの型を返す。
getLine :: IO String -- getLineの型は「IO String」である。
```

これは`IO String`型であって`String`型ではないので`String`型を取る関数にこれを渡しても型エラーが出てしまいます。do記法を使うことで`IO String`型から`String`を取り出すことができます。

```haskell:do記法による入力
main = do
  進捗 <- getLine -- input: 進捗
  putStrLn (進捗 ++ "ダメです！") -- output: 進捗ダメです！
```

一行に空白区切りの複数の入力がある場合にはwords関数を用いて文字列の配列に変換出来ます。Haskellの関数合成は`.`を用いて`func2 . func1`と表すことが出来ますが、IOなどに包まれた型の中身をIOから取り出して関数を作用させた後またIOにしまうには`<$>`を用います。わかりにくいですが、`IO String`の`String`の部分だけに関数を適用し、また`IO なんとか`に戻すことが出来るということです。`<$>`と`words`を使うことで`IO String`を`IO [String]`に変換出来ます。

```haskell:空白区切りの入力
import Control.Applicative

main = do
  ss <- words <$> getLine -- input: hoge fuga piyo
  putStrLn (head ss) -- output: hoge
```


```haskell:複数の数字が区切られている時
import Control.Applicative

main = do
  ss <- (map read . words) <$> getLine -- input: 123 456 789
-- ss = [123, 456, 789]
  putStrLn $ show $ foldl (+) 0 ss -- output: 1368
```

`putStrLn $ show $ foldl (+) 0 ss`というのは、foldlに(+)と0を部分適用した関数とshowという関数とputStrLnという関数を関数合成した関数に`ss`という引数を与えるという意味です。


`<-`はパターンマッチを利用してリストの中身を個別の変数に束縛することが出来ます。

```haskell:パターンマッチ
import Control.Applicative

main = do
  [a,b] <- words <$> getLine -- 空白区切り文字列の1番目と2番目をa,bに束縛する
  (c:cs) <- getLine -- 入力文字列の最初の文字と後ろの文字とそれに続く文字列をc,csに束縛する
  puts a  -- input: ちなつ あかり, output: ちなつ
  puts cs -- input: コモナド, output: モナド
```

パターンマッチに失敗すると実行時エラーが出るので一般的なプログラムを書くときは注意が必要です。競技プログラミングで入力フォーマットが保障されている時などは気にしなくてよいでしょう。

## モナド型クラスメソッド
do記法は実はモナドの合成のための専用構文です。この専用構文を用いないと前述のコードは下のようになります。

`>>=`の型は以下のとおりで、`getLine >>= putStrLn . func`は`func`に入力を渡して変換した文字列を出力できます。

```
(>>=) :: (Monad m) => m a -> (a -> m b) -> m b
```

```haskell:普通の入力
main = getLine >>= putStrLn . (++ "ダメです！")
-- input: 進捗
-- output: 進捗ダメです！
```

```haskell:区切られた入力
main = getLine >>= putStrLn . (unwords . map reverse) . words
-- input: hoge fuga piyo
-- output: egoh aguf oyip
```

```haskell:複数の数字が区切られている時
main = getLine >>= putStrLn . solve . map read . words

solve :: [Int] -> String
solve = show . foldl (+) 0
-- input: 123 456 789
-- output: 1368
```

```haskell:テンプレート
main = getLine >>= putStrLn . solve

solve :: String -> String
```

競技プログラミングの範囲だとdo記法よりも簡潔で綺麗になる場合が多いので、出来れば使えるようになりたいテクニックです。

## 便利関数

ghciの`:t`を使うと関数の型がわかります。関数の機能と使い方は型と名前からなんとなく推測してください。

### putStr
文字列を末尾に改行を付加しないで出力します。

### putChar
文字を末尾に改行を付加しないで出力します。

### print
Showのインスタンス型を受け取りshowした結果を表示します。
（GHCiで実行した時表示される文字列になります。）

### when
BoolとIOアクションを受け取り、Bool値がTrueの場合にIOアクションを実行します。

```haskell:when
ghci Control.Monad> when (1 > 0) $ do putStrLn "Tlue"
```

### interact

`String`を引数に取り`String`を返す関数を渡すと、入力をその関数で変換した結果の文字列を出力してくれます。interactは終端文字が与えられるまで関数を繰り返しますが、遅延評価により入力文字列が必要になった時に入力を要求されます。

```haskell:interact
main = interact $ unwords . map reverse . words

-- input: hoge fuga piyo
-- output: egoh aguf oyip
```

### readLn
入力の型を推論します。

```readLn
main = do
  n <- readLn -- input: 55
  putStrLn . show $ n * n -- output: 3025
```

### getContents
終端文字までの全ての文字列（改行含む）を得られます。

```haskell:getContents
main = do
  s <- getContents -- input: 1234\n5678\n90
  putStrLn . show . foldl (+) 0 . map read . lines $ s -- output: 7002
```

### mapM_
リストの要素に対してIOアクションを実行できます。

```haskell:mapM
ghci> mapM_ print [1, 2, 3]
1
2
3
```


### replicateM
N行の入力を取るのに便利です。

```haskell:replicateM
import Control.Monad
main = do
  s <- replicateM 3 getLine -- input: 123\n456\n789
-- s == ["123", "456", "789"]
  putStrLn . show . foldl (+) 0 . map read $ s -- output:1368
```

## 具体例
現在(2013/8/30)でHaskellが使えるオンラインコンテストジャッジはAtCoderとCodeforcesだけです。英語は読めないのでAtCoderの問題を使って入力を受け取ってみましょう。

### ARC14A
1. 1行目にはたこ焼きの番号を表す整数 N(1≦N≦1000) が与えられる。

```plain:入力例
N
```

```haskell:実装例
main = do
  n <- readLn
  putStrLn $ if even n then "Red" else "Blue"
```

### ARC14B
1. 1行目には整数 N(1≦N≦100) が与えられる。
2. 2行目からN+1行までのN行では、文字列Wiが与えられる。

```plain:入力例
N
W_1
W_2
:
W_N
```

```haskell:実装例
import Control.Monad
main = do
  n <- readLn
  ss <- repliciateM n getLine
  putStrLn $ solve n ss

solve :: Int -> [String] -> String
solve = undefined
```

### ARC14D
1. 1行目には空白で区切られた整数all,N,Mが与えられる。
2. 2 行目からN+1行までのN行では整数Liが与えられる。
3. N+2行目からN+M+1行までのM行では整数xi,yiが与えられる。

```plain:入力例
all N M
L1
L2
:
LN
x1 y1
x2 y2
:
xM yM
```

```haskell:実装例
import Control.Monad
import Control.Applicative

main = do
  [all,n,m] <- map read . words <$> getLine
  l <- replicateM n readLn
  xy <- map (map read . words) <$> replicateM m readLn
  
  putStrLn $ solve all l xy

solve :: Int -> [Int] -> [[Int]] -> [Int]
solve = undefined
```


## まとめ

- Haskellは強い
- でもIOが難しい
- do記法が手続きっぽくて書きやすい
- モナドを使うとシンプルに書けて格好良い
- モナドが使えなくても入出力用の関数を使える場合がある
- 競技プログラマで使うようなパターンは限られているので覚えてしまおう