# Haskell はコードをフラットにする
先日、このような投稿をした。
日頃 Haskell を書いていると、手続き型言語で書いていたような for を入れ子にした多重ループ、右斜め下に拡がっていくコードを書く機会が少ないことに気がつく。Haskell はコードをフラットにする。実際には Haskell は、というよりはモナドによるものだと思う。少しそれを見ていく。
[C - Slot Strategy 2 (Easy)](https://atcoder.jp/contests/abc320/tasks/abc320_c)
この問題を題材にする。多重ループの実装が必要になりそうな問題を選んだだけであり、詳細はさして重要ではない。さらっと概要だけ説明する。
以下のような入力が与えられる。
```
10
1937458062
8124690357
2385760149
```
長さ $10$ の $3$ 個のリールからなるスロットがある。各スロットは $1$ 秒にひとつ進む。各スロットがぐるぐる回転している中、スロットを停めて同じ数字を三つ揃えたい。最小で何秒でゾロ目を作れるか。
上記の例でいえば数字の `8` で `888` を揃えることを目標に、2 番目のスロット、3 番目のスロット、1番目のスロットと停めていくと最小の 6 秒でゾロ目を作ることができる。
以下のように解くと良い。
- どの数字 $x$ で停めるか $0 \ldots 9$ までを全探索する
- スロットをどの順で停めるかを順列全探索する
- 各リールの探索は、リールを $S_1' = S_1 + S_1 + S_1$ のように 3倍化して、目的の $x$ のインデックス位置を探索するのが簡単
数字の目の全探索、スロットを停める順の探索、$3$ 倍化された文字列 $S_i$ の探索 $\times 3$ なので手続き的に書くと 5 重ループの実装になる。
以下は ChatGPT に書かせた Python の実装である。
`for` の 5重ループにより、コードが右斜め下に伸びている。
```python
from itertools import permutations
INF = 10**15
M = int(input())
S1 = input()
S2 = input()
S3 = input()
S1 *= 3
S2 *= 3
S3 *= 3
ans = INF
for digit in '0123456789':
for s1, s2, s3 in list(permutations([S1, S2, S3])):
for i in range(M):
if s1[i] == digit:
for j in range(i + 1, 2 * M):
if s2[j] == digit:
for k in range(j + 1, 3 * M):
if s3[k] == digit:
ans = min(ans, k)
if ans == INF:
print(-1)
else:
print(ans)
```
一方、Haskell で書いた実装は以下で、見た目上 5 重ループ的なものは存在せずフラットである。
```haskell
main :: IO ()
main = do
_ <- getInt
ss <- replicateM 3 getLine
let ss' = map (\s -> s ++ s ++ s) ss
res =
[ do
t1 <- elemIndexFrom 0 x s1
t2 <- elemIndexFrom (t1 + 1) x s2
elemIndexFrom (t2 + 1) x s3
| [s1, s2, s3] <- permutations ss',
x <- ['0' .. '9']
]
print $ minimumDef (-1) (catMaybes res)
```
リストモナドによる非決定計算、Maybe モナドによる失敗可能性の文脈つき計算が発生しているが、いずれもモナドによって分岐的な計算構造は抽象化されモナドの背後に隠れる。そしてコードはフラットになる··· のだが、その説明だけだと意味が不明なので少し分解していく。
モナドを使わずに、手続き的な実装のように書くと以下のようになる。
内側の関数が外側の関数の変数を参照する必要があり、やはり右斜め下にコードが伸びていってしまう。
```haskell
main :: IO ()
main = do
_ <- getInt
ss <- replicateM 3 getLine
let ss' = map (\s -> s ++ s ++ s) ss
let res =
map
( \[s1, s2, s3] ->
map
( \x ->
case elemIndexFrom 0 x s1 of
Just t1 -> case elemIndexFrom (t1 + 1) x s2 of
Just t2 -> case elemIndexFrom (t2 + 1) x s3 of
Just t3 -> t3
Nothing -> maxBound
Nothing -> maxBound
)
['0' .. '9']
)
(permutations ss')
print res
```
この実装をフラットにしていくため少しずつモナドを導入していく。
まずは `permutations` と `[0 .. 9]` の二つのリストの全探索を、リストモナドのバインド演算子 `>>=` で結合する。
```haskell
let res =
permutations ss' >>= \[s1, s2, s3] ->
['0' .. '9'] >>= \x ->
```
このように書くことで、二つのリストの探索を一つのシーケンスに結合することができる。結果は、二つのリストの直積になる。
これを導入すると、先の実装は以下となる。
```haskell
main :: IO ()
main = do
_ <- getInt
ss <- replicateM 3 getLine
let ss' = map (\s -> s ++ s ++ s) ss
let res =
permutations ss' >>= \[s1, s2, s3] ->
['0' .. '9'] >>= \x ->
return $ case elemIndexFrom 0 x s1 of
Just t1 ->
case elemIndexFrom (t1 + 1) x s2 of
Just t2 -> elemIndexFrom (t2 + 1) x s3
Nothing -> Nothing
Nothing -> Nothing
print $ minimumDef (-1) (catMaybes res)
```
同様に $S_1, S_2, S_3$ を先頭から探索している `elemIndexFrom` が多数登場する実装も、モナドで結合することにしよう。
こちらは Maybe モナド、つまり失敗する可能性のある計算であるが、結合に使う演算子は同じ `>>=` である。モナドパワー。
Maybe モナドの結合は「計算が成功したら次に進み、途中で失敗したら計算全体は Nothing を返す」という結合である。
```haskell
elemIndexFrom 0 x s1 >>= \t1 ->
elemIndexFrom (t1 + 1) x s2 >>= \t2 ->
elemIndexFrom (t2 + 1) x s3 >>= \t3 ->
return t3
```
`>>=` で結合することによりいちいち Nothing が返却されるケースをパターンマッチする必要がなくなる。`>>=` の裏に、分岐が隠れた。
```haskell
main :: IO ()
main = do
_ <- getInt
ss <- replicateM 3 getLine
let ss' = map (\s -> s ++ s ++ s) ss
let res =
permutations ss' >>= \[s1, s2, s3] ->
['0' .. '9'] >>= \x ->
return $ elemIndexFrom 0 x s1 >>= \t1 ->
elemIndexFrom (t1 + 1) x s2 >>= \t2 ->
elemIndexFrom (t2 + 1) x s3 >>= \t3 ->
return t3
print $ minimumDef (-1) (catMaybes res)
```
モナドでリスト文脈とMaybe 文脈それぞれの計算が結合されたことにより幾分マシになった。
が、`>>=` で次の計算に値を渡していく過程が見づらいし、それこそここがコードの記述上、入れ子っぽくなってしまっている。
ここで `>>=` による計算の連結のシンタックスシュガーである `do` 記法を使うと、以下のように書ける。
```haskell
main :: IO ()
main = do
_ <- getInt
ss <- replicateM 3 getLine
let ss' = map (\s -> s ++ s ++ s) ss
let res = do
[s1, s2, s3] <- permutations ss'
x <- ['0' .. '9']
return $ do
t1 <- elemIndexFrom 0 x s1
t2 <- elemIndexFrom (t1 + 1) x s2
elemIndexFrom (t2 + 1) x s3
print $ minimumDef (-1) (catMaybes res)
```
魔法のようにみえつつ、これがただのシンタックスシュガーなのが面白い。
リストモナドの do 記法には、さらにそのシンタックスシュガーとも言えるリスト内包表記が用意されている。
これを使うと、冒頭の実装になる。
```haskell
main :: IO ()
main = do
_ <- getInt
ss <- replicateM 3 getLine
let ss' = map (\s -> s ++ s ++ s) ss
res =
[ do
t1 <- elemIndexFrom 0 x s1
t2 <- elemIndexFrom (t1 + 1) x s2
elemIndexFrom (t2 + 1) x s3
| [s1, s2, s3] <- permutations ss',
x <- ['0' .. '9']
]
print $ minimumDef (-1) (catMaybes res)
```
というわけで、リストや Maybe などの文脈つき計算がモナドによって抽象化されていて、do 記法を用いることでコードはフラットになり、またコードから消えた依存や分岐は背後のモナドに押しつけることができる、というのがそのメカニズムなわけである。
が、それはあくまでメカニズムであって、最終的に得られるコード表現を宣言的に考えると
- 複数のリストを全探索したい! → リスト内包表記と `<-` を使って、その直積を宣言する
- 失敗可能性のある計算をひとつにまとめて「成功 or 失敗」で一括りにいしたい! → do と `<-` を使ってそれらの結果をあたかも失敗しない手続きかのように計算を記述する
ということになる。そうするのが楽だから、そうする。するとコードがフラットになる。
実際、普段実装するときはモナドがどうこうとか `>>=` で連結しているのが、とかは考えていない。2つ、3つのリストがあって全探索したいと思ったらリスト内包表記で直積を宣言すればいいでしょという気持ちだし、Maybe を返す計算が連続したら do 記法で書くと楽、というような頭でコードを記述している。結果、気づけば多重ループとはほぼ無縁になった。