ZipListは、なぜ、ふつうにはモナドにならないか

想定読者層

Haskellのモナドやアプリカティブファンクタは、だいたいわかっている。モナド則について、ちゃんと考えてみたことがある。

注釈

この記事は、ZipListをモナドにしようと思ったときに、すぐに思いつくやりかたが、「なぜモナドにならないか」を説明しています。ZipListをモナドにする方法がないということを証明した記事ではありません。

はじめに

アプリカティブを学ぶときに、「モナドにならないアプリカティブ」として、ZipListが紹介されることが多い。しかし、ものごとを自分できちんと考えてみるタイプの人では、「えっ、できるじゃん」となりがちだ。

たしかに、ZipListであっても「モナドっぽいもの」は作れる。それがモナドとして正しくないのは、モナド則のうち結合則を満たさないためである。ここでは、ZipListを「正しくないやりかた」で、モナドクラスのインスタンスにしたうえで、それが結合則を満たさないことを示す。

モナドクラスのインスタンスにする

zipListMonad.hs

import Control.Applicative

instance Monad ZipList where
        ZipList xs >>= f = ZipList . zincat $ map (getZipList . f) xs

zincat :: [[a]] -> [a]
zincat ((x : xs) : xss) = x : zincat (takeJusts $ map safeTail xss)
zincat _ = []

takeJusts :: [Maybe a] -> [a]
takeJusts (Just x : mxs) = x : takeJusts mxs
takeJusts _ = []

safeTail :: [a] -> Maybe [a]
safeTail [] = Nothing
safeTail (_ : xs) = Just xs

関数zincatがポイントだ。これは、2重になったリストの1番目のリストの1番目、2番目のリストの2番目、...のように取り出して、1重のリストにする関数だ。ふつうのリストモナドにおける関数concatの代わりに、ZipListでは、このような関数zincatを使う。

さて、このような定義でZipListモナドができたように思われる。では、どうしてだめか。答えは「モナド則のうちの結合則を満たさない」からだ。

結合則を満たさない例

zipListMonad.hs

fun :: Int -> ZipList Int
fun n = ZipList $ replicate n n

check1 :: ZipList Int
check1 = ZipList [3, 2, 1] >>= \x -> (x *) <$> ZipList [2, 1, 3] >>= fun

check2 :: ZipList Int
check2 = (ZipList [3, 2, 1] >>= \x -> (x*) <$> ZipList [2, 1, 3]) >>= fun

check1とcheck2とでは、演算子(>>=)について、それぞれ、右結合、左結合となっている。もし、まともなモナドであれば、これらの結合は、おなじになるはずだ。実際には、つぎのようになる。

Prelude> :load zipListMonad.hs
*Main> check1
ZipList {getZipList = [6,2]}
*Main> check2
ZipList {getZipList = [6,2,3]}

どういうことか

つぎの図を見てみよう。はじめのモナドの結果、つぎのモナド((x *) <$> ...)の結果と、最終的な結果の候補とが樹構造で表現されている。ZipListの定義からするとこれらの、1番目の1番目の1番目、2番目の2番目の2番目、3番目の3番目の3番目を取り出すことになる。

   +- 6 -+- x11
   |     +- x12
   |     +- x13
   |     .
   |     .
   |     .
   |
   |
3 -+- 3 -+- x21
   |     +- x22
   |     +- x23
   |
   |
   +- 9 -+- x31
         +- x32
         +- x33
     .
     .
     .


   +- 4 -+- y11
   |     +- y12
   |     +- y13
   |     .
   |     .
   |     .
   |
2 -+- 2 -+- y21
   |     +- y22
   |
   +- 6 -+- y31
         +- y32
         +- y33
         .
         .
         .

   +- 2 -+- z11
   |     +- z12
   |
1 -+- 1 -+- z21
   |
   +- 3 -+- z31
         +- z32
         +- z33

左結合では、みっつの値が問題なく取り出せる。しかし、右結合のときのことを考えてみよう。1番下の樹の右からふたつをみてほしい。ここで、1番目の1番目は取り出せるが、2番目の2番目(つまりz22)は存在しない。そのため3番目の3番目(z33)を取り出す前にリストからの取り出しが終わってしまう。

このように、「あいだがぬける」ことによって、要素を取り出せないことがあり、その「取り出せなさ」が右結合と左結合とで変わってくるということだ。

モナドとして正当な定義は可能か

「ZipListモナドと呼べる」という条件を「ZipListアプリカティブと矛盾しないモナド」と定義するならば、実装可能かもしれない。ただし、このような実装は実用性も、美しさもないと思われるが。

(「このやりかたではモナドにならない」ことを言っているだけで、「モナドにすることはできない」ことを言っているのではないという指摘を受けての、追記です。)

アプリカティブとモナド

ファンクタに追加される機能を考えると、ふたつのちがいは、アプリカティブは「ふたつの文脈つきの値を組み合わせて、ひとつの文脈つきの値にできる」ということです。モナドは「二重になった文脈を、一重の文脈に変換することができる」ということです。

ファンクタの機能を使うと、「ふたつの文脈つきの値を組み合わせて、二重になった文脈にすること」ができます。なので、モナドの機能だけでアプリカティブの機能を実現することができます。このとき、実現された機能がアプリカティブとして実現された機能とおなじでなければ、「同一の文脈」とは言えません。

ZipListアプリカティブと矛盾しないために

以下のような定義をすれば、ZipListモナドを作ることはできそうだ。

instance Monad ZipList where
    ZipList xs >>= f
        | sameLength yss = ZipList $ zincat yss
        | otherwise = ZipList []
        where
        yss = map (getZipList . f) xs

sameLength :: [[a]] -> Bool
sameLength = and . (zipWith (==) <$> id <*> tail) . map length

このような定義(実用的ではないが)では、モナド則を満たし、かつ、ZipListアプリカティブとも矛盾しない定義ができるかもしれない(あとで検証する)。これは、内側のリストがすべておなじ長さでなければ、全体を空にしてしまうという、乱暴な定義だ。

追記

@lotzさんのご指摘で、この定義も、やはりモナド則を満たさないということが明らかになった。コメントを参照してください。@1to100penさんの記事を紹介してくれています。

ZipListは、なぜ、ふつうにはモナドにはならないか