モナド
Monad
Applicative
ZipList
アプリカティブ

ZipListアプリカティブファンクタはモナドに拡張できるか (1)

More than 1 year has passed since last update.

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

(結論だけに興味がある人は ZipListアプリカティブファンクタはモナドに拡張できるか (2) 結論
にどうぞ)

リストのアプリカティブファンクタ

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

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

ZipListモナドの性質 その1

ZipListモナドが ZipListアプリカティブの拡張であるためには前の記事 アプリカティブファンクタの拡張にあたるモナドを探る で書いたとおり

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

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)]

ZipListモナドの性質 その2

(後で記事を見直したらここで説明する性質は後の話では使っていなかったのでこの節は読み飛ばしても構いません)

次は join のモナド則を使って探ってみましょう。

asbs を同じ型を持つ二つのリストとします。さらに

xs = [as, bs]

{- さらにその xs を 2つ並べた3重リスト -}
xss = [xs, xs]

とします。この xssjoin を観察します。
join と (>>=) と、時々、fmap に書いたモナド則

join (join xss) = join (fmap join xss)

の左辺と右辺をそれぞれ計算します。
ys = join xs とします。

左辺 = join (join [[as, bs], [as, bs]))
       {- 行列の形をしているので性質1 により対角線を集める -}
     = join [as, bs]
     = join xs
     = ys
右辺 = join [join xs, join xs]
     = join [ys, ys]

つまり

ys = join [ys, ys]

さてここに出てきている [ys, ys] ですが2行(length ys)列の行列的な2重リストですので性質1を使うと、join した結果のリストの長さは 2以下になることがわかります。

length (join xs) = length ys = length (join [ys, ys]) <= 2

同様に、xs = [as, bs, cs] を3つ並べた3重リスト xss = [xs, xs, xs]join を観察すると

length (join xs) <= 3

がわかります。
次は xs = [as, bs, cs, ds] を4つ並べた3重リストを... というように考えていくと

ZipListモナドの性質2

任意の2重リスト xs に対して

length (join xs) <= length xs

が成り立つことがわかります。

続く

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

次の記事 ZipListアプリカティブファンクタはモナドに拡張できるか (2) でZipListモナドの全貌が明らかに!


May the Monad be with you