2010/05/27

リストモナドと非決定性

• リストは非決定性のモナド

わかりやすいんだけれど、「リストモナドは非決定性の文脈を表す」 と聞いたときに引っかかるのは、 リストには順序という概念も入っていること。 余分な制約がついてたら

  リストモナドの表す文脈 ⊂ 非決定性の文脈

ってことにならないのだろうか。(もちろんそうだとしても 「リストモナドは非決定性の文脈を表す」という命題は否定されないけれど)。

例えばリンク先のpathFindの例では、試行の順番が究極には networkのソースに与えられてる順番によって決定されちゃってる。 この例だけで言えば、Mapをそのまま使ってるからそうなってるだけであって、 例えばlookup時に値のリストをシャッフルして返すような構造を使えば ソースのリストの順番と試行は無関係になるけれど、 やっぱりlookupから一度リストを返しちゃったら、その順番というのは その後の計算に引きずられる。

いやもちろん、ランダムな試行が欲しければそういうのを書けばいいだけなんだけど。 どっちかというと「順序という制約を暗黙にも含まない形で 非決定性を文脈を表すモナドを実装するとしたらどうなるのかなあ」 という疑問かなあ。

いや実装がある必要はないか。 単に抽象的な、例えばAmbモナドというのがあって、 リストモナドがその一形態、となっているんだったらわかるんだけど。

それともHaskellerはそもそも順序という発想をしないのかも。 答えはすべて記述されている。順序というのは使う人が値を取り出す時に のみ問題になる、そいういうことかなあ。それならまあ、シャッフルが 欲しければ最終的な値を取り出す時にかき混ぜてやればいいってことになる?

Tags: Programming, Haskell, Monad