モナド，リスト，非決定性

## 概要

Haskell におけるモナドを導入し、リストが非決定性計算を与えることを見る。プログラミングにはある程度親しんでいるものの関数型言語の概念を知らない人を出発点に想定し、なるだけ跳躍のない導入を試みる。同様のトピックを解説した記事は数多存在しており、アプローチが重複していないかの確認はしていない。

## 導入
Python を例として次のようなコードを考えてみる。関数を順次適用していくことで処理を進めるありきたりのコードである。

```Python
a = m
b = f(a)
g(b)
```

ここで簡単のため `f` も `g` も整数を引数／戻り値とする関数であるとしよう。例えば次のように置こう。

```Python
def f(a):
    return 2*a
def g(b):
    return b+1
```

`toolz.pipe` を用いると上述のコードは次のように書ける。

```Python
toolz.pipe(
    m,
    lambda a: f(a),
    lambda b: g(b)
)
```

ここで `toolz.pipe` は `toolz.pipe(x,f,g,h,...) = ...h(g(f(x)))` のように振る舞う関数である。また`lambda a:f(a)` は`a`を引数、`f(a)`を戻り値とする関数を表す。つまり `f` のことである。

ここから「変数 `a` に値 `m` を代入する」という処理は、「引数に記号 `a` を割り当てた関数を値 `m` に適用する」こと、に置き換えられることがわかる。これを「代入と関数適用のイメージ」と呼ぶことにする。

上のコードはもちろん次と同じである。

```Python
toolz.pipe(m,f,g)
```
ここで `>>=` なる記号を導入して上コードを

```Haskell
( m >>= f ) >>= g
```

と書くことにしてみる。`m >>= f` は「`m`を`f`に渡すこと」すなわち`f(m)`を意味している。コード全体は「`m`を`f`に渡し、その結果を`g`に渡す」という意味になる。単純な書き換えであるが、「値を関数に渡す」ことが記号化され明示されている。`toolz.pipe`を用いたコードは値と関数を列挙しただけでこの点は明示的でない。

このコードはさらに

```Haskell
m >>= (\a -> (f a >>= g))
```

と書き換えてもよい。ここで`\a -> f a` はPython の `lambda a:f(a)` と同じ。この書き方は `m` がたどる運命を1つの関数にまとめている。すなわち「引数を`f`に渡し、その結果を`g`に渡す」関数`\a -> (f a >>= g)`に `m` を渡している。もう少しねちっこくかけば

```Haskell
m >>= (\a -> (f a >>= (\b -> g b)))
```

である。`g` を `\b -> g b`としただけである。

ここで「代入と関数適用のイメージ」を逆にたどろう。引数を記号`a`で表した関数に値`m`を渡すことは、値`m`を記号`a`で表すことと同様なのであった。そのことを `a <- m`と表すことにすると、これは

```Haskell
do
  a <- m
  b <- f a
  g b
```

と書いても差し支えない。この記法はdo記法と呼ばれるので`do`を付している。書き換え後、より下段に書かれた式は、書き換え前、より内側の括弧に位置していたこと、また初めのPythonコードと類似しつつそこにあった変数という概念が消失していることに注意されたい。なおこれはほんの少し疑似コードであり Haskell として実行はできない。

以上の流れを振り返ろう。ここでは

1. 関数の戻り値を変数に代入しながら、関数を順次適用していくことでコードを書く
1. `toolz.pipe`を用い、変数を使わず関数だけでコードを書く
1. 「値`a`を関数`f`に渡す」ことを意味する `a >>= f`なる記号を導入する
1. `f` を `\a -> f a` として引数記号を明示する
1. 「代入と関数適用のイメージ」に従って式を書き直す。すなわち値を記号に割り当てながら、関数を順次適用していくコードにする

ことを行った。ここで本質的に新しい概念は生まれていない。

## 非決定性計算

さきほどPythonで記した関数定義をHaskell で書き直しておこう。

```Haskell
f:: Int -> Int
f a = 2*a
g:: Int -> Int
g b = b+1
```

前節で扱った計算は**決定性計算**すなわち
![d.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1409134/f9c3f261-9f57-5f4e-19d0-f34589608fc5.png)
のような計算である。ここで**非決定性計算**すなわち
![画像_2021-10-26_214119.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1409134/08f2251f-e4f5-b883-dd68-535c7076748a.png)
のような計算を考えたい。たとえば次のような関数を考えよう。

```Haskell
f:: Int -> [Int]
f a = [1*a, 2*a, 3*a]
g:: Int -> [Int]
g b = [b+0, b+1]
```

図で示した計算の結果を得るだけなら、elephantに繰り返し処理を行えばよい。しかしelegentに記述する方法はないだろうか。関数を順次適用していくという、その有様を？

記号`m >>= f`を思い出そう。そしてこいつを

```Haskell
m >>= f   ===   concat (map f m)
```

で定義し直してやろう。いま式の等価性を言うのに`===`で表すことにした。

ここで `map f m` は `m=[m1,m2,m3,..]`のとき`[f m1, f m2, f m3, ...]` を、`cancat` は `[[a1,b1,...],[a2,b2,...],...]` のような入れ子を`[a1,b1,...,a2,b2,...]`と「なめす」（フラット化する）関数である。対話的環境での実行例は次の通り。

```Haskell
Prelude> f a = [1*a,2*a,3*a]
Prelude> f 2
[2,4,6]
Prelude> map f [1,2,3]
[[1,2,3],[2,4,6],[3,6,9]]
Prelude> concat (map f [1,2,3])
[1,2,3,2,4,6,3,6,9]
```

すると上の図で示した非決定性計算は前節と同じ次のコードで書けてしまう。

```Haskell
( m >>= f ) >>= g
```

もちろん関数`f`,`g`および記号`>>=`の定義が変わっている。do記法を用いれば、やはり同じコード

```Haskell
do
  a <- m
  b <- f a
  g b
```

である。この芸当は一番始めに示したPythonのやり方では実現できない。「値を関数に渡す」ことが記号化／明示されていないからである。

例で示したように、`m` は `m=[m1,m2,m3,..]` のような `[Int]`型の変数であることが想定されている。つまり`m >>= f`を `concat (map f m)` で定義したので、`f(1)` を表すのに `1 >>= f`のようには、すなわち

```Haskell
do
  a <- 1 -- これはNG
  b <- f a
  g b
```

のようには書けない。そこで

```Haskell
return:: Int -> [Int]
return x = [x]
```

という関数を定義しておけば、

```Haskell
do
  a <- return 1 -- これはOK。[1]と同じ。
  b <- f a
  g b
```

とできる。この`return`は

```Haskell
(return m0) >>= f   ===   f m0
m >>= return   ===   m
```

という性質を持っている。

## モナド

### リストモナド
これまでに出て来た登場人物を整理すると、`[Int]`の構造を鑑みて `concat (map f m)` で定義された`>>=`と、便宜的に導入された`return`が挙げられる。そしてこれらは次の性質を満たしていた。

```Haskell
(m >>= f) >>= g   ===   m >>= (\a -> (f a >>= g))
(return m0) >>= f   ===   f m0
m >>= return   ===   m
```

この三つ組 ```([], >>=, return)```を**リストモナド**と呼ぶ。リストモナドはdo記法の下で非決定性計算をエレガントに表現するモナドであった。

リストモナドを用いた非決定性計算の、もう少し実用的な例を紹介しよう。
$$
H(\mathbf q) =  c_0 + c_1 q_2 + c_2 q_3 + c_3 q_4 + c_4 q_2 q_3 + c_5 q_2 q_4 + c_6 q_3 q_4
$$

で示された関数 $H$ が常に $H\geq 0$ かつ、 $q_2q_3=q_4$ かつそのときに限り$H=0$ であるような条件を満たす係数$c_0,c_1,...,c_6$ を求める問題である。ただし$q_i\in\\{0, 1\\}$ であり $c_i$ は整数であるとする。下のコードは係数の絶対値が小さいものから列挙して5番目までを表示するコードになっている。

```Haskell
import Control.Monad

condition c0 c1 c2 c3 c4 c5 c6 = and $ do
  let z2 = [0,1]
  q2 <- z2
  q3 <- z2
  q4 <- z2
  let h =  c0 + c1*q2 + c2*q3 + c3*q4 + c4*q2*q3 + c5*q2*q4 + c6*q3*q4
  return $ and [h>=0, (q2*q3 == q4)==(h==0)]

coefficients = do
  let z k = 0 : [ y | x<-[1..k], y <- [x,-x]]
  -- z k = {0,1,-1,2,-2,3,..,k,-k}
  let n = [1..]
  k <- n
  c0 <- z k
  c1 <- z k
  c2 <- z k
  c3 <- z k
  c4 <- z k
  c5 <- z k
  c6 <- z k
  guard $ or [c == k | c <- [c0,c1,c2,c3,c4,c5,c6]]
  guard $ condition c0 c1 c2 c3 c4 c5 c6
  return (c0,c1,c2,c3,c4,c5,c6)

main = print $ show $ take 5 coefficients
```

説明していない記号が含まれているがおおむね意味はお判りになると思う。**解法**ではなく**問題**をそのまま記述すれば済むのが非決定性計算のメリットであり、リストモナドがこれを実現している。なおこれは『[量子アニーリングの基礎](https://www.kyoritsu-pub.co.jp/bookdetail/9784320035386)』に掲載されていた問題である。

### 恒等モナド

始めの節で導いたコードは疑似コードであるといった。これを正確に書くと次のようになる。

```Haskell
import Control.Monad.Identity

f:: Int -> Identity Int
f a = Identity (2*a)
g:: Int -> Identity Int
g b = Identity (b+1)

do
  a <- Identity m
  b <- f a
  g b
```

`Identity`はその名の通り恒等、つまり何もしない。ここでは先ほどの `[Int]` の代わりに `Identity Int` が検討されている。そこでこれを**恒等モナド**と呼ぶ。恒等モナドは始めの節で行ったような代入計算の類似を与える。

### 一般のモナド

`[]`や`identity`を一般化して`M`と表すことにしよう。このようにして一般の**モナド**を考えることができる。モナドは

```Haskell
>>=:: M x -> (x -> M y) -> M y
return:: x -> M x
```

つまりは`f::x->M y` のような`f`と`m::M x` に対して  `m >>= f` を考えられる記号 `>>=`
であって

```Haskell
(m >>= f) >>= g   ===   m >>= (\a -> (f a >>= g))
(return m0) >>= f   ===   f m0
m >>= return   ===   m
```

を満たす三つ組 `(M,>>=,return)` のことである。

### Maybe モナド

最後にありきたりの例であるが、いちおうこの流れでMaybe モナドを紹介する。
まずMaybe は `Just a` と `Nothing`の2通りの値を持つ。

```Haskell
data Maybe a = Just a | Nothing
```

たとえばゼロ除算を考慮する逆数関数は次のように書ける。

```Haskell
inv:: Double -> Maybe Double
inv a
  | a == 0 = Nothing
  | otherwise = Just (1/a)
```

つまり0 の逆数を計算しようとすると値は `Nothing` になり、それ以外では `Just 1/a` とする関数である。
計算が順次適用されるにあたり、ひとたび`Nothing`が出たら結果は`Nothing`であり、そうでなければ `Just 1/a`から `1/a`を取り出して計算を続行する。こうした処理を実装したい。

次のコードは、いま述べた内容そのままである。

```Haskell
Nothing  >>= _  =  Nothing
(Just x) >>= f  =  f x  
```

3つの数を引数にとりその逆数和を計算する関数は次のように書ける。

```Haskell
invsum3 a b c = do
  ai <- inv a
  bi <- inv b
  ci <- inv c
  return $ ai + bi + ci
```

モナドの性質によって、elephantに引数の0判定をすることなく、elegantに実装できている。結果なしを表すMaybe型に関するこのモナドをMaybeモナド呼ぶ。Maybeモナドは結果なし`Nothing`の伝播や判定をうまく表すことで記述を簡潔にしている。

なおelephant なコードとは次のようなものである。

```Python
def inv(a):
  if a == 0:
    return None
  else:
    return 1/a

def invsum3(a,b,c):
  ai = inv(a)
  bi = inv(b)
  ci = inv(c)
  if all([xi is not None for xi in [ai,bi,ci]]):
    return ai + bi + ci
  else:
    return None
```

こうした関数すべてについていちいち条件分岐を書かねばならないとすると頭の痛くなることである。

## まとめ

関数型プログラミングでは関数を順次適用していくことでプログラムを構築する。その順次適用の過程（値を次の関数に渡す）を`>>=`で明示化してみると、`>>=`をカスタマイズすることで非決定性計算やゼロ除算による計算失敗の伝播をうまく表すことができる。`Int`といった基礎的な型に対し、複数の値を取りうることや、値を持たない可能性があることはそれぞれ`[Int]`，`Maybe Int`といった型で表される。`[]`や`Maybe`は関数の順次適用に特別な処理を要する事情（文脈）を付与しており、こうした事情（文脈）をより一般に`M`と表すことにすると、`M`に応じて定義された`>>=`に`return`を加えていくつかの基礎的な性質を課したものをモナドと呼ぶ。リストモナドは非決定性計算を表すモナドであり、Maybe モナドは値を持たない可能性を表すモナドであった。