リストモナドの非決定性／可能性について

勉強中、リストモナドの挙動が興味深かったので、ざっくり調べてみた結果をとりあえずまとめてみる。

リストは次のように実装される。

Data List: Empty | cons a (List a)

そして、

Prelude> zipWith (+) [1,2,3] [4,5,6]
[5,7,9]

Prelude> concatMap (\x -> [x, x^2]) [1,2,3]
[1,1,2,4,3,9]

Prelude> [1,2,3] ++ [4,5,6]
[1,2,3,4,5,6]

まずはその中に入っているものはとにかく入っているのだという前提で学んでいく。
こうしたリストの使い勝手の良さはHaskellのよいところの１つだと思うが、さらに面白いのは、実はFanctor, Applicative, Monad各クラスのインスタンスであるという点。つまり、（入門Haskellプログラミングの表現をまず借りると）上記したような「コンテナとしてのリスト」という側面と別に、「コンテクストとしてのリスト」が存在している。

「コンテクストとしてのリスト」、つまりモナドリストは、たとえば次のような使い方をされる。

Prelude> (+) <$> [1,2,3] <*> [4,5,6]
[5,6,7,6,7,8,7,8,9]

Prelude> (++) <$> ["white ","black "] <*> ["cat","dog"]
["white cat","white dog","black cat","black dog"]

Will Kurtによると、モナドとしてのリストを理解するには「非決定論的な計算」という考え方をするのが最善だという。<*>でつながれたそれぞれのリストは「そのうちのどれであるかが決定されていない」ものであり、計算結果はありうる結果すべてを表現している…。
プログラミングの世界で非決定論的、なんていう言葉を目にするとは思っていなかっただけに、これには驚かされた。

コンテクストという言葉は、おそらく厳密に言えば圏論をしっかり理解しないと腑に落ちないワードだと思う（圏論を理解していないので断言もできない）のだが、Haskellでのモナドを頭に入れるだけであれば次のように考えるとよさそうだ。

コンテナとコンテクスト、という二種類のデータのあり方は、pure function 純粋関数とunpure function 非純粋関数にそれぞれ対応している。
関数が純粋であるとはこの場合、side effectを持たず、その関数にある引数を与えたとき、必ず同じ返り値が出てくる、という意味だ。これは、関数の役割が、ただその関数の定義と引数のみから完全に表現できる、ということでもある。
それは数学の純粋性にどこか似ている。定義、命題、そういったクリアーなモジュールとして在るのが純粋関数、そういう風に考える。
では非純粋とはなにかといえば、「それ自体」以外の役割、something elseを持つかもしれないもの、ということになる。関数と引数が持つデータ以外に何かを引き連れていたり、何かを生んだり、何かを表示したり…といった、つまりside effectを持つかもしれないものが非純粋関数だ。これを扱うためにFanctor, Applicative, Monadという考え方がある。

次に、純粋なものとしてのリストと、非純粋なものとしてのリスト、それぞれをコンテナ／コンテクストとして呼ぶ「意味」は何か、ということを考える。どちらも、ある種の比喩を含む表現だと思う。この比喩が面白いと思うのだが、まずコンテナのほうは「箱」だ。しかもフタが空いていて、何かを追加したり取り出したりするのは自由だが、とにかく中にはこれこれが入っているということが「確定している」。だから計算結果にはゆらぎがない（ように見える）。
一方、コンテクストとは、「何かを理解するために役立つ、状況や事象、情報」のことである。つまり、その何かというのは、コンテクスト(=something else)なしでは完全には意味をとれない。意味が決定されていない。

Prelude> (++) <$> ["white ","black "] <*> ["cat","dog"]
["white cat","white dog","black cat","black dog"]

上の式は、白か黒かが決定されておらず、犬か猫かも決定されていない、というように読むこともできる。結果は、すべてのあり得る可能性を拾い尽くしたものになる。

もちろんこれは、あえて文学的に表現すれば…ということで、実際にはこの式はdo構文を用いると次のようになる。
（参考: リストモナドの動作原理を考える - あどけない話）

sample: do
    x <- ["white ","black "]
    y <- ["cat","dog"]
    return (x ++ y)

*Main> sample
["white cat","white dog","black cat","black dog"]

上のsample関数を脱糖するとこうなる。

sample: ["white ","black "] >>= \x -> ["cat","dog"] >>= \y -> return (x ++ y)

リストモナドにおいて、returnと>>=はそれぞれ

return x: [x]
l >>= f: concatMap f l

このように定義されているから、sample関数はさらに

sample: concatMap (\x -> ["cat","dog"] >>= \y -> [x ++ y]) ["white ","black "]
      : concatMap (\x -> concatMap (\y -> [x ++ y]) ["cat","dog"]) ["white ","black "]

と変形できる。
これを内側、外側の順に計算すると、

sample: concatMap (\x -> [x ++ "cat", x ++ "dog"]) ["white ","black "]
      : ["white cat","white dog","black cat","black dog"]

リストモナドの計算に非決定性／すべてのありうる可能性…といったsomething elseが現れる根拠は、この式変換でいうとconcatMapの存在だろう。

:t concatMap
concatMap :: Foldable t => (a -> [b]) -> t a -> [b]

ところで、>>=の型は

:t (>>=)
(>>=) :: Monad m => m a -> (a -> m b) -> m b

こうなっている。
concatMapとは引数の順番が違うが、flipを使ってもよいと考えるとconcatMapのほうはこうなる。

:t flip concatMap
flip concatMap :: Foldable t => t a -> (a -> [b]) -> [b]

これを>>=と見比べてみると、>>=のm a/m bがconcatMapではt a/[b]になっているだけで、構造としては同じだ。「モナドな何かについて、モナドでない何かをとってモナドな何かを返す関数を適用することで、モナドな何かを返す」…これが>>=だとすれば、「Foldableな何かについて、リストでない何かをとってリストを返す関数を適用することで、リストを返す」ものがconcatMapだというわけだ。一般論としての>>=とconcatMapの関連性（正確ではないかもしれないが、抽象／具体の関係と呼んでみる）が、こう表現すると明らかになってくる。つまり、要素をリストに入れ、リストを返すという「リスト化」が、<*>でつながれたそれぞれの引数について不足なく行われる結果、可能性全体を表現するかのようなリストが生成される、というふうに考えることができる。

ここで文学的な解釈にあえて戻ってみると、結局、非決定性／可能性とは全体性なのだ、ということができるような気がする。こぼさずすべてを取り尽くすことが非決定性／可能性を生む。逆に言えば、その一部をとらないーすくわず、捨て去るたび毎に、それは凝固し、決定的になっていく。同時に、可能性がなくなり、固定されていく。こんな風に言い換えることもできるかもしれない。決まっていないことは可能性であり、決めることはゆらぎがなくなっていくことだと。当たり前といえば当たり前なのだが、あまりにも豊かすぎる表現のように感じられる。モナドという概念は、やっぱり面白い。