すごいH本 part87

リストモナド

5という値は決定的である。一方、[1,2,3]のような値は複数の計算結果を含んでいるとも、複数の候補地を同時に重ね合わせたような1つの値であるとも解釈できる。

リストをアプリカティブスタイルで使う

*Main> (*) <$> [1,2,3] <*> [10,100,1000]
[10,100,1000,20,200,2000,30,300,3000]

左辺のリスト要素と右辺のリスト要素のすべての組み合わせが結果のリストに含まれており、非決定性を表現している。

この非決定性計算はモナドとして利用することができる。

リストMonadのインスタンス

instance Monad [] where
    return x = [x]
    xs >>= f = concat (map f xs)
    fail _ = []

return は引数の値が1つだけ入っているリストを作って返す。return は、普通の値をリストにくるんで非決定な値に混ぜたいときに便利。

>>=を使ってみる

*Main> [3,4,5] >>= (\x -> [x, -x])
[3,-3,4,-4,5,-5]

リスト内の要素に関数が適用されリストががっちゃんこされて返ってきている。

非決定性計算は失敗する可能性のある計算の上位互換になっている。

*Main> [] >>= \x -> ["bad","mad","rad"]
[]
*Main> [1,3,4] >>= \x -> []
[]

空リストは返すべき値がなにもないということを表現しており、MaybeのNothingと似ている。リストにおける失敗は空リストで表現すればよい。

Maybeのときと同様でリストを連結して非決定性という文脈を伝播できる。

*Main> [1,2] >>= \n -> ['a','b'] >>= \ch -> return (n, ch)
[(1,'a'),(1,'b'),(2,'a'),(2,'b')]

これは、[1,2]の各要素n、['a','b']各要素chに対して、タプルを作りなさいというプログラムになっている。

do 記法で書き直す

listOfTuples :: [(Int, Char)]
listOfTuples = do
    n <- [1,2]
    ch <- ['a','b']
    return (n, ch)

実行

*Main> listOfTuples
[(1,'a'),(1,'b'),(2,'a'),(2,'b')]

非決定性という文脈を>>=がいい感じにしてくれている。

文脈というものがイメージできるようになってきたので、モナドがやってくれていることもだんだんイメージできるようになってきた。