ZipListアプリカティブファンクタはモナドに拡張できるか (1)  (Is there any monad instance for ZipList applicative functor? (Part 1))

ZipListアプリカティブファンクタはモナドに拡張できるかの話です。

（結論だけに興味がある人は [ZipListアプリカティブファンクタはモナドに拡張できるか (2) 結論](https://qiita.com/1to100pen/items/a29bf3162d2dd5107e92#結論-conclusion)
にどうぞ）

# リストのアプリカティブファンクタ (Applicative Functors on Lists)

Haskell のリストには標準でアプリカティブファンクタが定義されています。
ghci で試してみましょう。（プロンプトの一部は省略しています。）

```
$ stack ghci
> :m Control.Applicative
> liftA2 (,) [1,2,3] ['a','b']
[(1,'a'),(1,'b'),(2,'a'),(2,'b'),(3,'a'),(3,'b')]

> -- ついでにリストの標準のモナドの liftM2 も試します

> :m Control.Monad
> liftM2 (,) [1,2,3] ['a','b']
[(1,'a'),(1,'b'),(2,'a'),(2,'b'),(3,'a'),(3,'b')]

> -- liftA2 の結果と同じですね
```

おなじみのリストモナド系のアプリカティブファンクタです。

リストにはもう一つ有名なアプリカティブファンクタがあります。ZipList です。

```
$ stack ghci
> :m Control.Applicative
> liftA2 (,) (ZipList [1,2,3]) (ZipList ['a','b'])
ZipList {getZipList = [(1,'a'),(2,'b')]}

> -- ついでに zipWith も試します

> zipWith (,) [1,2,3] ['a','b']
[(1,'a'),(2,'b')]

> -- 実質的に liftA2 の結果と同じですね
```

名前のとおり zip系のアプリカティブファンクタです。

ZipListアプリカティブファンクタの定義は

```
instance Applicative ZipList where
  pure x = ZipList (repeat x)
  liftA2 f (ZipList xs) (ZipList ys) = ZipList (zipWith f xs ys)
```

となっています。
リストにはこの二つの他にもアプリカティブファンクタがある（と思っている）のですがその話はまたいつか。

# ZipListモナド (ZipList Monad)

リストの標準のアプリカティブファンクタはリストモナドに拡張できます。
ZipListアプリカティブファンクタについてはどうでしょう？
モナドに拡張できるかどうかまだわかっていませんが、あるとしたらそのモナドはどういう性質を持つのか探っていきましょう。
便宜のため、そのあるかもしれないモナドを ZipListモナドと呼ぶことにします。

以下、この記事ではリストに関しては ZipListアプリカティブと ZipListモナドの話しかしないので構築子 ZipList を書くのは省略します。

# ZipListモナドの性質 その1 (The property of ZipList monad (Part 1))

ZipListモナドが ZipListアプリカティブの拡張であるためには前の記事 [アプリカティブファンクタの拡張にあたるモナドを探る](http://qiita.com/1to100pen/items/ee283c9805342cade4a6) で書いたとおり

```
return x = pure x
           {- ZipList アプリカティブの pure の実質的定義 -}
         = repeat x

join (fmap (\x -> fmap (f x) ys) xs) 
         = liftA2 f xs ys
           {- ZipList アプリカティブの liftA2 の実質的定義 -}
         = zipWith f xs ys
```

を満たす必要があります。
今回は対象データがリストなので `fmap (\x -> fmap (f x) ys) xs` の部分は `[[f x y | y <- ys] | x <- xs]` とも書けます。
具体例として `f = (,)`、`xs = [1,2,3]`、`ys = ['a','b']` を上の `join` の等式に当てはめてみると

```
join [[(1,'a'),(1,'b')], [(2,'a'),(2,'b')], [(3,'a'),(3,'b')]]
  = [(1,'a'),(2,'b')]
```

`[[(1,'a'),(1,'b')], [(2,'a'),(2,'b')], [(3,'a'),(3,'b')]]` を行列的に表示すると

```
[ [(1,'a'),(1,'b')],
  [(2,'a'),(2,'b')],
  [(3,'a'),(3,'b')] ]
```

ですから上の `join` の等式は行列の対角線上の要素（`(1,'a')`, `(2,'b')`）だけを join が集めていること示しています。（注：この例のように正方形状ではないときは図形でいうところの「対角線上」にはなっていないですが他に適当な言葉を思いつかないのでこの表現で通します）
この例を一般化して考えると行列の形をしている2重リストを `join` した結果は行列の対角線上の要素を集めたリストになるということがわかります。
（ここは厳密な説明を書いても長いだけで面白みもないと思うのでこの程度の説明で）

**ZipListモナドの性質1  (The property of ZipList monad (Part 1))**

m行n列の行列的な2重リスト

```
xss = [ [x_11, x_12, x_13, ... , x_1n],
        [x_21, x_22, x_23, ... , x_2n],
        [x_31, x_32, x_33, ... , x_3n],
        ...
        [x_m1, x_m2, x_m3, ... , x_mn] ]
```

を `join` した結果は行列の対角線上の要素だけを集めたリストになる。
つまり、m と n の小さい方の値を l とすると

```
join xss = [x_11, x_22, x_33, ... , x_ll]
```

別の書き方だと

```
join xss = [xss!!0!!0, xss!!1!!1, xss!!2!!2, ... , xss!!(l-1)!!(l-1)]
```

# 次回完結 (To be concluded)

ZipListモナドへたどり着くにはもう二ひねりあるので今回はこの辺で。

次の記事 [ZipListアプリカティブファンクタはモナドに拡張できるか (2)](http://qiita.com/1to100pen/items/a29bf3162d2dd5107e92) でZipListモナドの全貌が明らかに！

---

May Monad be with you