AtCoder に登録したら解くべき精選過去問 10 問を Haskell で解いてみた

#はじめに

[AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～](https://qiita.com/drken/items/fd4e5e3630d0f5859067) で紹介されていた10問をHaskellで解きました。他の人の記事([Rust](https://qiita.com/tubo28/items/e6076e9040da57368845), [Python](http://delta114514.hatenablog.jp/entry/2018/03/15/014555), [C#](https://qiita.com/NotFounds/items/7b166af69a6f52a332de), [Java](https://qiita.com/0x841/items/0ce887c86cf081312a08#_reference-97c7d0ae8f053253d35b), [Kotlin](https://sites.google.com/view/ymatsux/atcoder-abs-kotlin)) も参考にした ~~6番煎じ~~ （この記事を書いている途中に[JavaScript](https://qiita.com/mochi8k/items/caf7bf0ba287da81b20f#_reference-0126b0f91689ed0ad876)も出たので）7番煎じとなっております。
[AtCoder Beginners Selection コンテストページ](https://beta.atcoder.jp/contests/abs)

# 対象
言語の解説を多めに入れていきますので、あまりHaskellに詳しくない人でもなんとか追えるかと思います。（その分とても長くなっているが）
「[すごいHaskellたのしく学ぼう!](https://www.amazon.co.jp/すごいHaskellたのしく学ぼう-Miran-Lipovača/dp/4274068854)」とか読み終えている人なら余裕で追えると思います（し、0問目とかの長ったらしい解説は飛ばして大丈夫だと思います）。

# 入出力 & 0問目 [PracticeA はじめてのあっとこーだー（Welcome to AtCoder）](https://abs.contest.atcoder.jp/tasks/practice_1)
[Rust](https://qiita.com/tubo28/items/e6076e9040da57368845) の記事に
> どの言語でも最初に躓くのが入力だと思います。

と書いてありますが、Haskellは特に入出力が難しいイメージを持たれている気がするので、解説していきます[^a]。とはいえ、具体的なコードがないのも分かりにくいと思いますので、0問目も同時に解説していきましょう。

```haskell
main = do
 a <- readLn
 [b,c] <- map read . words <$> getLine
 s <- getLine
 putStrLn $ unwords [show (a + b + c), s]

```

（注: 「すごいHaskell」読み終わってる人は`readLn`の解説だけ読めば十分です。簡単にいうと`read`と`getLine`を合わせた感じの関数です。[^pp]）

---

`main` はI/Oアクション（入出力にまつわる命令書）です。この `do` と `<-` を使った構文で複数のI/Oアクションをまとめ、単一のI/Oアクションにすることができます。[^k]以下、それぞれの行が何をやっているのか解説していきます。

まず、4行目の`getLine`から。これは、入力を1行取って入力された文字列を生成するI/Oアクションです。それを`s`に`<-`してやることで、`s`には入力された文字列が入ります。

次に、1行目の`readLn`ですが、これは`getLine`して得られた文字列を解釈（例えば、文字列が`"4"`なら数値の`4`を、文字列が`"[1,2,3,4]"`だったらリスト`[1,2,3,4]`を）してくれるI/Oアクションです。数値を返すこともリストを返すこともできる関数なので、「どの型で解釈してほしいのか」を何らかの形で教えてあげないといけませんが、今回は`readLn`した結果の`a`が5行目で`+`されているので、Haskellは無事に型を推論してやることができます[^u]。（推論できない場合に失敗する、という話も後で言及します。）

---

さて、難関[^w]は2行目の`map read . words <$> getLine`です。順を追って解説していきましょう。
まず、`map read . words`は`map read`と`words`を関数合成した関数（つまり、`(map read . words) x == map read (words x)`）です。`words`は文字列を空白で区切ってくれる関数なので、例えば

```haskell
words "1 2 3 4" == ["1","2","3","4"]
words "alpha beta    gamma" == ["alpha","beta","gamma"]
```

です。
`read`は、先程言及した`readLn`と似た感じで文字列を解釈してくれる関数なので、それを`map`という関数でリストの各要素に適用してやることで

```haskell
map read (words "1 2 3 4") == [1,2,3,4]
```

となるので、結果として `map read . words` は「スペース区切りされた数が書かれた文字列を、数値のリストにしてくれる」関数[^qrs]ということになります。

さて、最後に`<$>`ですが、これの詳細な解説[^fmap]はここではしません。

```haskell
do
 hoge <- action
 let a = f hoge
 ...
```

というコード（`let a = f hoge`は、単に`f hoge`という値に`a`という名前をつけるという意味）を、

```haskell
do
 a <- f <$> action
 ...
```

と書けるようにするおまじないだと思ってください。[^excuse]

まとめると、`map read . words <$> getLine`は、「スペース区切りされた数が書かれた入力を1行受け取って数値のリストを生成するI/Oアクション」という、競プロでとても便利な定型句となります。以下の解説でも多用します。

---

最後に、`putStrLn $ unwords [show (a + b + c), s]` です。`putStrLn hoge`は定数`hoge`に入っている文字列を出力して改行するI/Oアクションです。`unwords`は`words`の逆の役割をする[^inverse]関数で、

```haskell
unwords ["a","b"] == "a b"
```

のように、文字列のリストをスペース区切りの文字列にまとめてくれます。（ちなみに、スペースが要らないときには`concat`という関数が使えます。）

`show`は`read`の逆の役割をする関数[^inv2]で、ここでは数値`a + b + c`を文字列に変換してくれます。`s`は元から文字列なので変換してはいけません。

`$`は、`(foo bar)(hoge baz)`を`foo bar $ hoge baz`と書けるようにするおまじないだと思っておけばそんなに問題ないでしょう[^dollar]。なお、右結合なので、`a b $ c d $ e f`と書いてあったら`(a b)(c d $ e f)`なので`(a b)((c d) (e f))`です。

---

以上で0問目の解説は終わりです。長い説明にお付き合い下さりありがとうございます。[もうちょっとだけ続くんじゃ](http://dic.nicovideo.jp/a/もうちっとだけ続くんじゃ)。

# 1問目 [ABC086A  Product](https://abs.contest.atcoder.jp/tasks/abc086_a)
```haskell
main = do
 [a,b] <- map read . words <$> getLine
 if (a * b) `mod` 2 == 0 then putStrLn "Even" else putStrLn "Odd"
```
2行目で先程解説したコードを使って`a`と`b`を読み込み、それの積の剰余で条件分岐をしています。剰余を取る関数には`mod`と`rem`の2つがあり、負の数での挙動が違います。

```haskell
(-6) `mod` 5 == 4
```

```haskell
(-6) `rem` 5 == (-1)
```

大抵の場合は`mod`を使っておけば問題ないでしょう。なお、商を求める関数にも同様に`div`と`quot`があります。`div`と組になるのが`mod`で、`quot`と組になるのが`rem`です。
とはいえ、`quot`と`rem`は私は未だに使ったことがないですし、実用上も`div`と`mod`を覚えておけば十分でしょう。


ちなみに、最後の行は

```haskell
 putStrLn $ if (a * b) `mod` 2 == 0 then "Even" else "Odd"
```

とも書けます。この場合、`$`が無いと構文エラーになるので気をつけましょう。

#2問目 [ABC081A Placing Marbles](https://abs.contest.atcoder.jp/tasks/abc081_a)

```haskell
main = getLine >>= print . length . filter (=='1')
```
無駄に簡潔に書いているので解説が面倒ですが、面倒臭がっていても始まらないのでちゃんと解説していきます[^simple]。

---

まず、`print . length . filter (=='1')`から見ていきましょう。恒例のごとく、これは`print` と `length` と `filter (=='1')`を関数合成したものです。

第一引数に条件を指定し、第二引数にリストを指定することで、リストの中から条件を満たす値だけを抜き出せる関数が`filter` です。`(=='1')`は「文字 `'1'`と等しい」という条件を表すこと[^partial]、Haskellで文字列は文字のリストであることを考慮すると、

```haskell
filter (=='1') "1foo2bar1hoge31415" == "1111"
```

というように、`filter (=='1')`は「文字列から文字`'1'`のみを抜き出す関数」となることがわかります。

これに、リストの長さを返す関数である `length` を合成してやることで、「文字列から文字`'1'`のみを抜き出し、その長さを数える」＝「文字列の中に`'1'`が何個あるか数える」関数が出来上がります。

```haskell
length (filter (=='1') "1foo2bar1hoge31415") == 4
(length . filter (=='1')) "1foo2bar1hoge31415" == 4
```

最後に合成されている`print`という関数は、`show`したものを`putStrLn`する関数です[^docs]ので、結果として、`print . length . filter (=='1')`は「文字列を受け取って、その中の文字`'1'`の個数を出力する命令書を作る」という関数になることが分かります。

---

さて、最後に`>>=`を見ていきましょう。``>>=``というのは、 `` m >>= f `` が

```haskell
do
 a <- m
 f a
```

と等価になるような演算子です[^reverse]。今回の場合は、`getLine`が生成した文字列を先程説明した関数`print . length . filter (=='1')`に渡す役割を担っていることが分かります。

#3問目 [ABC081B Shift only](https://abs.contest.atcoder.jp/tasks/abc081_b)

最初に解いた時に私の提出したコードは

```haskell
import Data.Maybe
main = do
 _ <- getLine
 a_s <- map read . words <$> getLine
 let divisor = foldr1 gcd a_s
 print . subtract 1 . length . takeWhile isJust . iterate (>>=f) $ Just divisor

f x
 | x `mod` 2 == 0 = Just(x `div` 2)
 | otherwise = Nothing
```

なのですが、解法が微妙で、かつあまりにも解説に向かない[^leftasexercise]ので、解説にはIamnoob様（[Twitter](https://twitter.com/_Iamnoob_), [AtCoder](https://atcoder.jp/user/Iamnoob)）の[コード](https://abs.contest.atcoder.jp/submissions/2214285)を元にして私が少々手を加えた、↓のコードで解説していきたいと思います。

```haskell
f x = if x `mod` 2 == 0 then 1 + f (x `div` 2) else 0

main = do
 getLine
 a <- map read . words <$> getLine
 print $ minimum $ map f a
```

---
まずは`main`を読んでいきましょう。
最初に`getLine`をしていますが、その結果生成される文字列を使わずに捨てています。ここには入力される正の整数の個数が書いてあるのですが、`map read . words <$> getLine`を使って一行全部読んでいる現状ではその情報は必要ないからです。
なお、ここで`getLine`の代わりに`n <- readLn`と書くと、

```
error:
      Ambiguous type variable ‘a0’ arising from a use of ‘readLn’
      prevents the constraint ‘(Read a0)’ from being solved.
      Probable fix: use a type annotation to specify what ‘a0’ should be.
```

というエラーが出ます。第0問と異なり、`n`はプログラムの残りの部分で使われていないので、「どの型に変換すればいいのか分からない」と怒られてしまいます。「使われないなら逆にどの型でもいいじゃん」と思われるかもしれませんが、そうもいかないのです。


`map read . words <$> getLine`で得た $A_1$ ~ $A_n$ のリスト`a`に、「2で何回割れるかを数える」関数`f`（後で解説します）を`map`することで、`a`の各要素に`f`が適用されたリストが手に入ります。そのリストの最小値を`minimum`関数を使って求めてやることで、答えを求められます。

---

後は、「2で何回割れるかを数える」関数`f`を読み解いてやれば終了です。長々と説明してもいいですが、具体的な数で挙動を追いかけてみましょう。

```haskell
f 24
if 24 `mod` 2 == 0 then 1 + f (24 `div` 2) else 0 -- fの定義
1 + f (24 `div` 2)  -- 24 `mod` 2 == 0 は真
1 + f 12  -- 24 `div` 2を計算
1 + (if 12 `mod` 2 == 0 then 1 + f (12 `div` 2) else 0) -- fの定義
1 + (1 + f (12 `div` 2) ) -- 12 `mod` 2 == 0 は真
1 + (1 + f 6) -- 12 `div` 2を計算
1 + (1 + (if 6 `mod` 2 == 0 then 1 + f (6 `div` 2) else 0)) -- fの定義
1 + (1 + (1 + f (6 `div` 2))) -- 6 `mod` 2 == 0 は真
1 + (1 + (1 + f 3)) -- 6 `div` 2を計算
1 + (1 + (1 + (if 3 `mod` 2 == 0 then 1 + f (3 `div` 2) else 0))) -- fの定義
1 + (1 + (1 + (0))) -- 3 `mod` 2 == 0 は ††偽††
3 -- 計算
```

要するに、命令型言語ならループで書くような挙動を、`f`の定義の中で`f`を使うことで実現するわけです。これを「再帰」と言います。

#4問目 [ABC087B Coins](https://abs.contest.atcoder.jp/tasks/abc087_b)

```haskell
main = do
 a <- readLn
 b <- readLn
 c <- readLn
 x <- readLn
 print $ length [() | u <- [0..a], v <- [0..b], w <- [0..c], 500*u+100*v+50*w == x]
```

2〜5行目で`a`,`b`,`c`,`x`を読んだあと、6行目で全探索をしています。
命令型言語だったら3重ループを書くところですが、Haskellでやる場合は「リスト内包表記」という構文を上手く使うのが便利です。

`[ ~ ]`の部分がリスト内包表記です。「リスト内包表記」というもの自体は、Pythonなどで目にしたり耳にしたりしたことのある方もいるのではないでしょうか[^python]。

やっていることは簡単です。まず、`|`の右側を見てみましょう。`[0..a]`で0からaまでの整数のリストを作ることができ、そこから`u`を取り出しています。同様に`v`と`w`を取り出した後、`500*u+100*v+50*w == x`の条件を満たす候補だけを残しています。
`|`の左側では、例えば`(u,v,w)`と書いてやることで、全体としては条件を満たす3つ組だけが入ったリストが出来上がりますが、今回は具体的な値には興味がないため、空タプル（0要素からなるタプル）`()`を置いています。

リスト内包表記でリストが出来上がったら、それの`length`を`print`してやれば完了です。

#5問目 [ABC083B Some Sums](https://abs.contest.atcoder.jp/tasks/abc083_b)

```haskell
main = do
 [n, a, b] <- map read . words <$> getLine
 print $ sum [k | k <- [1..n], evaluate k >= a, evaluate k <= b]

evaluate k = sum [read [c] | c <- show k]
```
2行目はテンプレですね。3行目にはリスト内包表記があります。「1からnまでの整数を取ってきて、それを`evaluate`という関数（桁の総和を計算する関数。後述する）に入れたものが`a`以上であり`b`以下であるもの」が`[ ~ ]`で表されるリストなので、それの総和を`sum`という関数で取って、`print`しているだけです。

次に、`evaluate`ですが、これは前述の通り桁の総和を計算する関数です。これもまたリスト内包表記と`sum`の組み合わせですね。ちょっと分かりにくいので、具体的に`evaluate 1234`がどんな値になるか見てみましょう。

```haskell
evaluate 1234
sum [read [c] | c <- show 1234] -- 定義で置き換え
sum [read [c] | c <- "1234"] -- showは数値を文字列に変換してくれる
sum [read [c] | c <- ['1', '2', '3', '4'] ] -- 文字列は文字のリスト
sum [read ['1'], read ['2'], read ['3'], read ['4']] -- リスト内包表記を展開
sum [read "1", read "2", read "3", read "4"] -- 文字のリストは文字列
sum [1, 2, 3, 4] -- readは文字列を数値に変換してくれる
10 -- sumは総和
```

というわけで、桁数の総和が計算できることがわかりました[^digitToInt]。


#6問目 [ABC088B Card Game for Two](https://abs.contest.atcoder.jp/tasks/abc088_b)

最初に解いた時に私の提出したコードは

```haskell
import Data.List
main = do
 _ <- getLine
 a_s <- map read . words <$> getLine
 print $ analyze $ reverse $ sort a_s

analyze :: [Integer] -> Integer
analyze = f . unzip . chop
f(us,vs) = sum us - sum vs

chop (a:b:c) = (a,b) : chop c
chop [a] = [(a,0)]
chop [] = []
```

なのですが、長いのでcojna様（[Twitter](https://twitter.com/cojna), [AtCoder](http://atcoder.jp/user/cojna)）のコードを参考にした以下のコード

```haskell
import Data.List
main = do
 getLine
 a_s <- map read . words <$> getLine
 print $ sum $ zipWith (*) (cycle [1, -1]) $ reverse $ sort a_s
```

で解説します。

リストをソートする必要があるので、先頭で`import Data.List`という宣言をして`sort`関数を使えるようにします。

入力の1行目を単独`getLine`で読み飛ばし、$a_1$ ~ $a_n$の入ったリスト`a_s`を`map read . words <$> getLine`で入手しています。

5行目では、まず`reverse $ sort a_s`で、`a_s`を`sort`でソートした後`reverse`で逆順にしたリストを作っています。これにより、降順でソートされます。

あとは、これを先頭からそれぞれAliceとBobに振り分けていけばいいのですが、(Aliceのカードの総和) - (Bobのカードの総和)が求まればよいので、奇数番目の要素を1倍し、偶数番目の要素を-1倍して総和を取ればよいことになります[^me]。それを行っているのがその次の`zipWith (*) (cycle [1,-1])`と`sum`です。
まず、`cycle [1, -1]`は`1`と`-1`が交互に出てくる無限リスト`[1, -1, 1, -1, 1, -1, ...]`を生み出します[^infinite]。`zipWith`関数は、次のような挙動をする関数です。

```haskell
zipWith f [a1, a2, ...., an] [b1, b2, ...., bm]
== [f a1 b1, f a2 b2, ..., f am bm]
```
（ただし、$n \ge m$とする）

二つのリストを先頭から、ジッパーで閉じるように`f`で一つずつ対応させて新たなリストを作るのが`zipWith`関数です。リストの長さが異なるときには短い方のリストの長さになるので、無限リストと有限リストを`zipWith`してできる新しいリストの長さは有限です。

ということで、2つのリストを`(*)`で`zipWith`して`sum`を取ったものを`print`することで、答えが出ます。

#7問目 [ABC085B Kagami Mochi](https://abs.contest.atcoder.jp/tasks/abc085_b)

```haskell
import Control.Monad
import Data.List
main = do
 n <- readLn
 ds <- replicateM n readLn
 print $ length $ group $ sort (ds :: [Integer])
```

`replicateM k m`は、I/Oアクション`m`を`k`回行い、それぞれの結果をまとめたリストを結果とするI/Oアクションです。`replicateM`は`Control.Monad`に定義されているので、予め`import`しておきましょう。

これを`sort`してやるのですが、その際に`ds`が整数のリストであるという情報も提供しておきましょう。そのための記述が` :: [Integer]`で、これがないと型推論が失敗します。

次に、`group`という関数を使います。これは[公式](http://hackage.haskell.org/package/base-4.10.1.0/docs/Data-List.html#v:group)に載っている例が分かりやすいので引用すると、

```haskell
group "Mississippi" = ["M","i","ss","i","ss","i","pp","i"]
```

というように、隣り合っている同一の値をグループ化してくれます。

これの`length`を`print`すれば完了です。

#8問目 [ABC085C Otoshidama](https://abs.contest.atcoder.jp/tasks/abc085_c)
私のコード（↓）は実行速度が比較的早い(1msだった)のですが、長いので解説には用いず、

```haskell
main = do
 [n, y] <- map read . words <$> getLine
 let u = y `div` 1000 - n
 case analyze u of
  Nothing -> putStrLn "-1 -1 -1"
  Just (a,b) -> putStrLn $ 
   if n-a-b < 0 then "-1 -1 -1" else unwords $ map show [a,b,n-a-b]

analyze :: Integer -> Maybe(Integer,Integer)
analyze u
 | u < 0 = Nothing
 | u >= 36 = let (a_,b_) = head $ foo $ (u `mod` 36)+36 in Just((u `div` 36 - 1)*4+a_,b_)
 | otherwise = case foo u of
  [] -> Nothing
  k:_ -> Just k

foo u = [(a,b) | a <- [0..7], b <- [0..8], 9*a+4*b == u]
```

これまたIamnoob様のコードで解説させていただきます。

```haskell
main = do
 [n, y] <- map read . words <$> getLine
 let ans = [[a, b, c] | a <- [0 .. n], b <- [0 .. (n - a)], let c = n - a - b, 10000 * a + 5000 * b + 1000 * c == y]
 putStrLn $ unwords $ map show $ if null ans then [-1, -1, -1] else head ans
```

3行目はリスト内包表記で全探索をしていますが、$a+b+c=n$ かつ $c\ge0$ なので $n-a\ge b$ が必要になります。そのため、`a`の範囲は`[0 .. n]`ですが`b`の範囲は`[0 .. (n - a)]`にする必要があります。あとは`10000 * a + 5000 * b + 1000 * c == y`の条件を加えてやるだけです。
そうして得られた、条件を満たす`[a,b,c]`を集めたリストに`ans`という名前を付けています。

最後の行については、

 - `null`: 空リストなら`True`、それ以外は`False`を返す関数
 - `head`: リストの先頭要素を返す関数

を解説すれば十分でしょう。

#9問目 [ABC049C 白昼夢 / Daydream](https://abs.contest.atcoder.jp/tasks/arc065_a)

```haskell
main = do
 s <- getLine
 putStrLn $ if analyze (reverse s) then "YES" else "NO"

analyze "" = True
analyze ('m':'a':'e':'r':'d':k) = analyze k
analyze ('r':'e':'m':'a':'e':'r':'d':k) = analyze k
analyze ('e':'s':'a':'r':'e':k) = analyze k
analyze ('r':'e':'s':'a':'r':'e':k) = analyze k
analyze _ = False
```
先頭から処理していくと厄介なので、一旦`reverse`してから後ろから処理していっています。
`'m':'a':'e':'r':'d':k`はmaerdで始まる文字列にマッチし、残りの部分に`k`という名前がつくので、その`k`を再び`analyze`にかける、ということをやっていって、最終的に空文字列が得られたら`True`、そうでなければ`False`です。

あとは、それに応じて`"YES"`か`"NO"`を返し、`putStrLn`してやれば完了です。

#10問目 [ABC086C Traveling](https://abs.contest.atcoder.jp/tasks/arc089_a)

```haskell
import Control.Monad
main = do
 n <- readLn
 txys <- replicateM n $ map read . words <$> getLine
 putStrLn $ if analyze ([0,0,0]:txys) then "Yes" else "No"

analyze [a,b] = reachable a b
analyze (a:b:xs) = reachable a b && analyze (b:xs)

reachable [t1,x1,y1] [t2,x2,y2] = 
 (dt >= dx + dy) && ( (dt - dx - dy) `mod` 2 == 0)
 where dx = abs(x2-x1); dy = abs(y2-y1); dt = t2-t1
```

入力を読み取ったら、それの先頭に`[0,0,0]`[^tuple]を付けて、`analyze`に渡します。
`analyze`では、再帰を使って、「隣り合うt,x,yの組に`reachable`関数を適用し、全部が`True`なら`True`」という処理を書いています。「移動が毎回成功するなら、全体でも成功する」ということですね。

最後に`reachable`ですが、`where`という予約語を使って計算途中の値に名前を付けています。

#おわりに
解説を書くのが予想以上に面倒でしたが、お役に立てれば幸いです。
定数倍が厳しくない問題・実装速度が実行速度より重視される系の問題ではHaskellは普通に有用なので、おすすめです（Haskellはいいぞ）

#脚注
[^a]: 初学者の混乱を防ぐためにも、用語とかはなるべく「すごいHaskell」に合わせるようにして解説していきます。
[^u]: 「整数型も小数型も`+`できるのに、なんでコンパイルが通るの？」と気づいた人はとてもすごいです。この場合、コンパイラが気を効かせて「`Integer`でよさそう」としてくれるのでコンパイルが通ります。`-Wall`を付けてコンパイルすると、`Defaulting the following constraints to type ‘Integer’`というメッセージが(ghcなら)出て、このことを教えてくれます。
[^k]: 詳しくは「Haskell モナド」とか「Haskell 入出力」とかで調べるか、「すごいHaskell」の第8章を読みましょう。
[^w]: これがスラスラ読めるプロは温かく見守っていただけると幸いです。
[^pp]: 厳密に言うと、`read`ではなく`readIO`です。
[^qrs]: 「型制約がついていないんだから、数値とは限らんぞ」はい、そのとおりです。
[^fmap]: 型クラス`Functor`のメソッド`fmap`の別名
[^excuse]: 言い訳をするなら、`instance Functor IO` は `fmap f x = x >>= (pure . f)` と定義されていて、かつ`IO`モナドがモナド則を満たしている（ので`pure`したものを`<-`したら元の値になる）以上、そんなに誤った説明でもない気がします。（不十分な説明であることは確かだが）
[^inverse]: `unwords (words "a  b") == "a b"`なので、逆関数ではありません。
[^inv2]: これもまた`show(read "[1,  2]" :: [Int]) == "[1,2]"`なので、逆関数ではありません。
[^dollar]: `foo bar(hoge baz)`、と説明されることが多い気がしますが、その理解だと`product $ map (+1) [1,2,3]`に1を足したい時に`1 + product $ map (+1) [1,2,3]`と書いてしまって（これは`1 + product (map (+1) [1,2,3])` ではなく `(1 + product) (map (+1) [1,2,3])`なのでダメ）エラーが出るので、第一項にもカッコを付けて教えています。
[^simple]: こうやって簡潔に書けるのもHaskell競プロの利点なので、解説用にわざわざ書き直さずにあえてこのまま解説します。
[^reverse]: もちろん、本当は`do`が`>>=`に翻訳されているわけなので、「等価」という表現で逃げています。
[^partial]: この記法は「セクション」と言います。頻出するので、「すごいHaskell」とかを読んでちゃんと理解しておきましょう。
[^docs]: [公式のソースコード](http://hackage.haskell.org/package/base-4.10.1.0/docs/src/System.IO.html#print) を見てみると一発でわかりますね。
[^leftasexercise]: 腕に自信のあるプロは是非解読してみましょう。
[^python]: ちなみに、Pythonのリスト内包表記はHaskellに直接由来するそうです。
[^digitToInt]: `import Data.Char`して`digitToInt`してもいいんですが、「`show`と`read`が対称的」「`Prelude`に入っていない関数を暗記させるのもなんかなぁ（後で`replicateM`とか`sort`とか出てくるけど）、そもそも最初に組んだときは私が`digitToInt`の存在を知らなかったし」「説明する関数の数が少なければ少ないほど執筆が楽」ということもあり、今回は`read`を使いました。ちなみに最初に組んだときは`subtract (fromEnum '0') . fromEnum`とか[書いてました](https://beta.atcoder.jp/contests/abs/submissions/2216215)。
[^me]: ちなみに、私はこの発想が思いつかなかったので、上記のコードではかなり面倒なことをしています。
[^infinite]: Haskellでは無限の長さを持つリストを扱うことができます。もちろん、長さを求めようとしたりソートしようとしたりすると無限ループが発生します。ここで使ったように、`zip`系の関数などと合わせて使うのが定石です。
[^tuple]: tとxとyの組を表すにはタプルを使ったほうが健全で、私も最初の提出ではタプルを使っていましたが、コードが長くなるのでこのコードでは全部リストで処理しています。