リストデータ型にのるモナド構造の単位射は a -> [a] だけ (1)

この記事ではモナドの単位射（圏論では通常 `η`（イータ）が使われるやつ）の呼び名として return を使います。
return は Haskell での名前で他の言語では point などが使われたりします。

前回の記事 [リストのモナドは1つだけか？](https://qiita.com/1to100pen/items/1558a4d6600c47f7f859) でリストデータ型にのるモナド構造を3つ紹介しましたが、単位射はすべて `return a = [a]` でした。
別のモナド構造で、単位射が例えば `return a = [a,a]` や `return a = repeat a` になるようなものもあるのでしょうか。
実は単位射は `return a = [a]` しかありえないのです。

説明は長くなりますが、難しい理論を使うわけでもなく、ひたすらモナド則を使っていくだけなので辛抱強くお付き合いください。

以下、コードで説明する際は Haskell風のコードを使います。あくまでも「風」です。そのまま Haskell では動きません。
この記事に出てくる return, join, map, モナド則になじみがない方はまずは [join と (>>=) と、時々、fmap](https://qiita.com/1to100pen/items/3ac5864b648b1d7b81ae) をご覧ください。


# 記事内で使う用語

まずこの記事内で使う用語から説明します。一般的に使われる用語ではありません。

ある2重リスト（つまりリストのリスト）の各要素（リスト）の長さが m1, m2, ... m_n のとき、その2重リストは `(m1, m2, ... m_n)の n個形`であると呼ぶことにします。
例えば `[[1,2,3], [5], [6,7]]` は `(3,1,2)の3個形`です。
この例のように個数があきらかな場合は何個の部分は省略して単に `(3,1,2)形`とだけ表現することもあります。
m が l個並ぶ `(m,m,... m)形のl個形`は `m * l形`と呼びます。
例えば `[[1,2], [3,4], [5,6]]` は `2 * 3`形です。
無限リストも考えるので、`[[1,2], [3..]]` は `(2,∞)形`、すべての要素が無限リストである無限リストは `∞ * ∞個形`ということになります。

この記事では `return a = [a,a,... a]` （n個並んでいるとする。0個のケースも無限大個のケースもあり）であるモナドについて考察します。
n が 1 でないときもこのモナド（実は存在しなのですが）に名前がないと説明しづらいので、そのようなモナドを「複製ユニットモナド」、特に `n` という個数をはっきりさせたいときは「n複製ユニットモナド」と呼ぶことにします。
以降、`n` という変数はこの複製数を表すためだけに使います。

# 前提とする法則

**同じ形の2重リスト（無限リストも考える）に対する join は同じように作用する**
何が言いたいかというと、例えば
`join [[1,2,3],[4,5]] = [3,4,1,5,1,3]` だったとしたら
`join [[11,12,13],[14,15]] = [13,14,11,15,11,13]` だし、
`join [['a','b','c'],['d','e']] = ['c','d','a','e','a','c']` のように
要素の値や型が違っても同じ形に対する join の結果は同じ長さとなり対応する要素の位置も同じになります。
join は多相関数（圏論での自然変換にあたる）なので当然ですね。


**モナド則**

```
join (return xs) = xs
join (map return xs) = xs
join (map join xss) = join (join xss)
```

モナドですからモナド則を満たさないとね。
この記事では最初の法則を「return のモナド則」、2番目の法則を「map return のモナド則」、最後の法則を「join のモナド則」と呼ぶことにします。（一般的に使われる呼び方ではありません。）

**空リストの join 結果は空リスト**

上記の map return のモナド則で xs = [] の場合を考えると

```
join (map return []) = []
```
空リストに何を map しても空リストですから

```
join [] = []
```

さあ、準備が整いました。これからモナド則をばんばん使っていきましょう!

# 複製ユニットモナドの性質(1) n > 0

n が 0 となることがあるか考えます。つまり `return x = []` というケースです。
`return x = []` と仮定して、return のモナド則と `join [] = []` を使うと

```
[1] = join (return [1]) = join [] = []
```
となって矛盾します。

**性質1**

n複製ユニットモナドは `n > 0` でなければならない。

以降、n > 0 として話を進めます。

# 複製ユニットモナドの性質(2) n * n形の join

3複製ユニットモナドで `xs = [1,2,3]` での例で説明します。
 `xs` に `return` と、`map return` するとそれぞれ

```
return xs = [
  [1,2,3],
  [1,2,3],
  [1,2,3]] -- xs が n(=3)複製

map return xs = [
  [1,1,1],
  [2,2,2],
  [3,3,3]] -- xs の各要素が n(=3)複製
```
となります。

return のモナド則と map return のモナド則から

```
join [
  [1,2,3],
  [1,2,3],
  [1,2,3]] = [1,2,3]

join [
  [1,1,1],
  [2,2,2],
  [3,3,3]] = [1,2,3]
```

`return xs` も `map return xs` もどちらも n * n形と同じ形をしているので同じ join の作用を受けることになります。
両方の2重リストで上記の等式が成り立つためには join は対角線上の要素を取ってくるしかありません。
つまり

```
join [
  [x11, x12, x13],
  [x21, x22, x23],
  [x31, x32, x33]] = [x11, x22, x33]
```

今の例は `n` が 3 のケースでしたが、一般の `n` に対する `xs = [1,2,...n]` でも同様に考えられるので

**性質2**

n複製ユニットモナドの join に n * n形リストを適用した結果は対角線要素を集めたものになる。

つまり n * n形の xss に対して

```
join [
  [x11, x12, ... x1n],
  [x21, x22, ... x2n],
  ...
  [xn1, xn2, ... xnn]] = [x11, x22, ... xnn]

{- 別の書き方だと -}
join xss = [xss!i!i | i <- [0..n-1]]
```

n が有限としての書き方をしていますが、n = ∞ であったときでも成り立ちます。

# 複製ユニットモナドの性質(3) r * n形の join

次はちょっとややっこしくなります。
また 3複製ユニットモナドの具体的な例で考察します。

```
{- (3,0,0)形の3つのリスト -}
xs1 = [[1,2,3], [], []]
xs2 = [[4,5,6], [], []]
xs3 = [[7,8,9], [], []]

ys1 = join xs1
ys2 = join xs2
ys3 = join xs3

zs = [xs1, xs2, xs3]
{- = [
  [[1,2,3], [], []],
  [[4,5,6], [], []],
  [[7,8,9], [], []]]
-}
```

として zs での join のモナド則

```
join (join zs) = join (map join zs)
```
を観察しましょう。

```
左辺 = join (join zs)
  {- zs は 3 * 3形なので性質2より対角線要素を集めて -}
 = join [[1,2,3], [], []]
 = join xs1
 = ys1

右辺 = join (map join zs)
  = join [join xs1, join xs2, join xs3]
  = join [ys1, ys2, ys3]
```
つまり

```
join [ys1, ys2, ys3] = ys1
```

`xs1`,`xs2`,`xs3` はすべて同じ (3,0,0)形をしているので join した結果の `ys1`,`ys2`,`ys3` はすべて同じ長さになります。
その長さを `r` とします。（r は 0 や ∞ である可能性もあります）

上記の等式からわかることは

**3複製ユニットモナドの join に r * 3形のリストを適用すると結果には最初の要素のリストしか影響しない**

ということです。

ここで注意してもらいたいのは `ys1`,`ys2`,`ys3` はそれぞれ `xs1`,`xs2`,`xs3` を join した特別な値のリストでの話だったのに急に r * 3形のリストという一般的な話にもっていっていることです。

理由を説明しますがその前に  `ys1`,`ys2`,`ys3` に現れる要素について調べておきます。
`ys1 = join [[1,2,3], [], []]` でしたから `ys1` には 1 か 2 か 3 しか現れません。
同様に `ys2` には 4 か 5 か 6 しか、 `ys3` には 7 か 8 か 9 しか現れません。

では改めて r * 3形のリストの話にもっていける説明を始めます。
もし一般的な r * 3形のリスト `ws` を join した結果に `ws` の2番目のリストの要素か3番目のリストの要素が一つでも現れるとしたら、同じ r * 3形をしている `[ys1, ys2, ys3]` の join にも `ys2` か `ys3` の要素である 4 か 5 か 6 か 7 か 8 か 9 のどれかが必ず現れてくることになります。
一方 `join [ys1, ys2, ys3] = ys1` の右辺の `ys1` には 1 か 2 か 3 しか現れませんからこれは矛盾です。

もう一考察すると r * 3形のリストの join のさらに詳しい様子わかります。
そのことを見るにも具体的な例で見ていった方がわりやすいので `r = 2` だったとしたときの状況で説明します。
return のモナド則から `join (return [1,2]) = [1,2]` が成り立ちますが return は今は 3複製ユニットで説明していますので

```
join [[1,2], [1,2], [1,2]] = [1,2]
```
ということになります。
左辺は r(=2) * 3形のリストを join したものですが、上でわかった r * 3形のリストの join の作用の仕方から2番目のリストの `[1,2]` と3番目のリストの `[1,2]` は結果にまったく影響を与えることなく最初のリストの `[1,2]` がそのまま右辺に現れたことがわかります。
つまり r(=2) * 3形のリストの join は

```
join [[x11,x12], [x21,x22], [x31,x32]] = [x11,x12]
```
と最初の要素のリストがそのまま出てくるということです。

今は `n = 3` で考えましたが一般の n に対して (n,0,...0)形のn個リストの join結果のリストの長さを r とすると
上に書いたのと同じ考え方で

**n複製ユニットモナドの join に r * n形のリストを適用すると結果には最初の要素のリストしか影響しない**

ということがわかり、
return のモナド則 `join (return [1..r]) = [1..r]` が成り立つことと組み合わせて上に書いたのと同じ考え方で

**n複製ユニットモナドの join に r * n形のリストを適用すると最初の要素のリストがそのまま出てくる**

ということがわかります。

以降も r という変数は (n,0,...0)のn個形リストの join結果のリストの長さを表すためだけに使います。

`n = 1` のときに関する注意：

`n = 1` のときの (n,0,...0)のn個形リストとは (1)形のリスト（つまり `[[x]]` という形のリスト）のことで空リストが絡んでこないことに注意してください。

```
{-
  1複製ユニットモナドなので return xs = [xs] と
  return のモナド則 join (return xs) = xs を使うと
-}
r = length (join [[x]]) = length (join (return [x])) = length [x] = 1
```
で `n = 1` のときは `r = 1` であるということもわかります。

**性質3**

r * n形の xss に対して

```
join [
  [x11, x12, ... x1r],
  [x21, x22, ... x2r],
  ...
  [xn1, xn2, ... xnr]] = [x11, x12, ... x1r]

{- 別の書き方だと -}
join xss = xss!0
```

n も r も有限としての書き方をしていますが、n = ∞ や r = ∞ であったときでも成り立ちます。

次の記事 [リストデータ型にのるモナド構造の単位射は a -> [a] だけ (2)](https://qiita.com/1to100pen/items/14b3ee5171214308ca80) に続きます。

---

May Monad be with you