「Haskellは競技プログラミングには向いている」と言われたりもするが、競プロやオンラインジャッジにHaskellで取り組もうとすると、最初は問題を解くよりも、「どうやって入力を受けて、出力すれば良いのか？」の方が分からなかったりする。
例えば、AtCorderの「はじめてのあっとこーだー」にある解答例とか。
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競技プログラミング入門」の冒頭に書かれている、このコードとか。
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
これらが何をしているのかスンナリ理解できないという、少し前の私と同じレベルの方と共有したい基礎の基礎。
例
たとえば「各行の数値を加算し、行ごとに出力する」といった問題を仮定して、入力が
10 20
30 40
50 60
だったとする。各行をsumしたいので、これを最終的に
[[10,20],[30,40],[50,60]]
この形で受け取りたい。
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が楽なときもある）
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]
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]]になった
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')となる
これで、やっと標準入力を望んだ形式に変換することができたが、いかにも冗長である。
関数合成等により、記述を簡素化する。
整理
まず、仮の変数にバインドした関数を実体と置き換える。
main = do
input <- getContents
print (map (map read')(map words (lines input)))
read' :: String -> Int
read' = read
かっこを$で置き換える。右から左に進むpipeだと思って置き換えればよい。
hlintなどの力も借りるとmapの繰り返しを合成関数の一回のmapに置き換える、等のサジェストをしてくれるので、良いものは従う。
main = do
input <- getContents
print $ map (map read'. words) $ lines input
read' :: String -> Int
read' = read
最後の$はlinesをその次の関数と合成するために見掛け上移動する。
一番最後の$は無くせないが、途中の$は関数合成の.に置き換えられるので合成に直す。
main = do
input <- getContents
print . map (map read'. words) . lines $ input
read' :: String -> Int
read' = read
これでひとまず完成。
（今は最終結果をprintしているが実際にはここから処理のための関数と出力のための関数が続く）
慣れてくれば最初からこの形で書き下せるが、完全に理解するまではひとつひとつ処理したものを変数にバインドしてはバケツリレーして引き渡し、処理が完成したところで結合して整理した方が間違えにくい。
応用
私が良くお世話になっているHackerRank (www.hackerrank.com)
このサイトの問題では、入力の先頭に行数が付いていることが多い。
これは他言語が入力を繰り返し受け取るためのループカウントとして使うことを意図しているのだろうが、Haskellの場合、getContentsで一括して複数行を受け取れるし、リストの場合、長さの制約はないので、いらない情報。
3
10 20
30 40
50 60
この3は、こんな感じで落とせる
main = do
_ : input <- lines <$> getContents
print . map (map read . words) $ input
1行目の先頭の_はワイルドカードで、リストの先頭要素は参照せず捨ててしまうことを意味する。
<$>はfmapの別記法でIO付きのStringに対して普通の関数であるlinesを適用できる。(functor)
本文書冒頭の両例でも<$>が使われている。
冒頭例ではimport Control.Aplicativeしているが現在はimportなしでPreludeから使える。
冒頭の二番目の例の「複数行バージョン」と比較してみて欲しい。
また、最初の入力の処理への受け渡し方としては別の方法として
-- 入力がこれ
-- 10 20
getLine >>= print.sum.map read.words
-- 出力は
-- 30
このように>>=を使って入力を処理に引き渡すやり方もある。
しかし、見掛け上、データの流れが途中で逆転するので分かりにくいという面もあり、単純なケースをワンライナーで書きたいというようなとき以外は個人的には使っていない。
（データの流れが逆転する、とは、>>=では左から右に入力データが流れるイメージなのに対して、以降はwordsからprintに向かって右から左にデータが流れるイメージのため）
ここまでが入力。これでやっと問題を解くことができるようになる。
そりゃあ、Haskell入り口高いって言われるよね。
（また、本気で競技プログラミングするならStringではなくByteStringのような処理効率の良いものを使うことになるそう。本件、うまくできたら別途記事にします）
出力編に続く・・
追記
@Mizunashi_Mana さんにコメントにてリスト内包表記を使った書き方を教えていただきました。
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) ]
リスト内包表記をこんな風に使えることに驚きました。
感動的なまでに読みやすいです。