Haskellでオンラインジャッジに取り組むときの入出力（前編：標準入力の受け方）

「Haskellは競技プログラミングには向いている」と言われたりもするが、競プロやオンラインジャッジにHaskellで取り組もうとすると、最初は問題を解くよりも、「どうやって入力を受けて、出力すれば良いのか？」の方が分からなかったりする。

例えば、AtCorderの「はじめてのあっとこーだー」にある解答例とか。

atcorderSample.hs

import Control.Applicative
main :: IO ()
main = do
    -- 整数の入力
    a <- readLn
    -- スペース区切り整数の入力
    [b, c] <- map read . words <$> getLine
    -- 文字列の入力
    s <- getLine
    -- 出力
    putStrLn $ show (a + b + c) ++ " " ++ s

Qiitaの@myuon_myonさんの記事「Haskell競技プログラミング入門」の冒頭に書かれている、このコードとか。

sample2.hs

import Control.Applicative
main = do
  -- "L M N" ---> [L,M,N]
  n <- fmap (read :: String -> Int) . words <$> getLine
  -- 複数行バージョン
  ns <- fmap (fmap (read :: String -> Int) . words) . lines <$> getContents

これらが何をしているのかスンナリ理解できないという、少し前の私と同じレベルの方と共有したい基礎の基礎。

例

たとえば「各行の数値を加算し、行ごとに出力する」といった問題を仮定して、入力が

input.txt

10 20
30 40
50 60

だったとする。各行をsumしたいので、これを最終的に

input.hs

[[10,20],[30,40],[50,60]]

この形で受け取りたい。

sample1.hs

main = do
  input <- getContents
  -- "10 20\n30 40\n50 60\n"
  print input

• getContentsで複数行の入力が一つのStringとして取得できる
• getContents :: IO String
• getContentsすると複数行の入力が、改行コードを含む一つの(IO付き）Stringになる
  getContentsの戻りはIO Stringだが<-で変数inputにバインドすると、inputはIOが外れて、ただのStringになる
• 標準入力を受ける関数は複数があるが、原則、getContentsで可（getContentsは入力行が可変となるときに便利。入力行数が固定の場合はgetLineが楽なときもある）

sample2.hs

  input <- getContents
  -- "10 20\n30 40\n50 60\n"
  let strList = lines input
  -- ["10 20","30 40","50 60"]
  print strList

• getContentsで複数行が一つのStringになったものを行単位に分けるためにはlinesを使う
• lines :: String -> [String]

sample3.hs

  input <- getContents
  -- "10 20\n30 40\n50 60\n"
  let strList = lines input
  -- ["10 20","30 40","50 60"]
  let sepList = map words strList
  -- [["10","20"],["30","40"],["50","60"]]
  print sepList

• 1行に複数の値がある場合、linesの結果一行分が一つのStringになっているので、wordsを使ってバラす
• words :: String -> [String]
• 各行（リストの各要素）を全てバラしたいのでwordsをmapする
• ここまでで入力は、Stringのリストのリスト[[String]]になった

sample4.hs

main = do
  input <- getContents
  -- "10 20\n30 40\n50 60\n"
  let strList = lines input
  -- ["10 20","30 40","50 60"]
  let sepList = map words strList
  -- [["10","20"],["30","40"],["50","60"]]
  let ans = map (map read') sepList
  -- [[10,20],[30,40],[50,60]]
-- これでも可
-- let ans = map (map (read :: String -> Int)) sepList
  print ans

read' :: String -> Int
read' = read

• リストのリストの要素がStringのままでは演算できない。そこでreadを使って数値に変換する
• read :: Read a => String -> a
• readは多相関数のため、このままだと何型に変換したいのかが分からないので、ここではread'を定義することでIntへの変換であることを示している
• (read::String->Int)のように関数に直接型を記述する方法でも可
• また、後続で数値演算が行われる処理があることで、型推論により型指定しなくても上手くいくケースもある。冒頭のAtCorderの例はread後に加算していることから型指定がなくともreadした結果を数字として扱ってくれる
• まず内側のリストの各要素にread'をmapするにはmap read'とすれば良いのはすぐわかる (map read' ["10,"20"] ----> [10,20])
• 更に外側のリストの各要素に、この関数を喰わせたいので結果としてmap (map read')となる

これで、やっと標準入力を望んだ形式に変換することができたが、いかにも冗長である。
関数合成等により、記述を簡素化する。

整理

まず、仮の変数にバインドした関数を実体と置き換える。

sample5.hs

main = do
  input <- getContents
  print (map (map read')(map words (lines input)))

read' :: String -> Int
read' = read

かっこを$で置き換える。右から左に進むpipeだと思って置き換えればよい。
hlintなどの力も借りるとmapの繰り返しを合成関数の一回のmapに置き換える、等のサジェストをしてくれるので、良いものは従う。

sample5.hs

main = do
  input <- getContents
  print $ map (map read'. words) $ lines input

read' :: String -> Int
read' = read

最後の$はlinesをその次の関数と合成するために見掛け上移動する。
一番最後の$は無くせないが、途中の$は関数合成の.に置き換えられるので合成に直す。

sample6.hs

main = do
  input <- getContents
  print . map (map read'. words) . lines $ input

read' :: String -> Int
read' = read

これでひとまず完成。
（今は最終結果をprintしているが実際にはここから処理のための関数と出力のための関数が続く）
慣れてくれば最初からこの形で書き下せるが、完全に理解するまではひとつひとつ処理したものを変数にバインドしてはバケツリレーして引き渡し、処理が完成したところで結合して整理した方が間違えにくい。

応用

私が良くお世話になっているHackerRank　(www.hackerrank.com)
このサイトの問題では、入力の先頭に行数が付いていることが多い。
これは他言語が入力を繰り返し受け取るためのループカウントとして使うことを意図しているのだろうが、Haskellの場合、getContentsで一括して複数行を受け取れるし、リストの場合、長さの制約はないので、いらない情報。

input2.txt

3
10 20
30 40
50 60

この3は、こんな感じで落とせる

sample6.hs

main = do
  _ : input <- lines <$> getContents
  print . map (map read . words) $ input

1行目の先頭の_はワイルドカードで、リストの先頭要素は参照せず捨ててしまうことを意味する。

<$>はfmapの別記法でIO付きのStringに対して普通の関数であるlinesを適用できる。(functor)
本文書冒頭の両例でも<$>が使われている。
冒頭例ではimport Control.Aplicativeしているが現在はimportなしでPreludeから使える。
冒頭の二番目の例の「複数行バージョン」と比較してみて欲しい。

また、最初の入力の処理への受け渡し方としては別の方法として

bind.hs

-- 入力がこれ
-- 10 20
getLine >>= print.sum.map read.words
-- 出力は
-- 30

このように>>=を使って入力を処理に引き渡すやり方もある。
しかし、見掛け上、データの流れが途中で逆転するので分かりにくいという面もあり、単純なケースをワンライナーで書きたいというようなとき以外は個人的には使っていない。
（データの流れが逆転する、とは、>>=では左から右に入力データが流れるイメージなのに対して、以降はwordsからprintに向かって右から左にデータが流れるイメージのため）

ここまでが入力。これでやっと問題を解くことができるようになる。
そりゃあ、Haskell入り口高いって言われるよね。

（また、本気で競技プログラミングするならStringではなくByteStringのような処理効率の良いものを使うことになるそう。本件、うまくできたら別途記事にします）

出力編に続く・・

追記

@Mizunashi_Mana さんにコメントにてリスト内包表記を使った書き方を教えていただきました。

sample6'.hs

main = do
  _ : input <- lines <$> getContents
  print . map (map read . words) $ input

-- これをこう書けるそうです

main = do
  input <- getContents
  print [ [ read x :: Int | x <- words line ] | line <- tail (lines input) ]

リスト内包表記をこんな風に使えることに驚きました。
感動的なまでに読みやすいです。