あどけない話

インターネットに関する技術的な話など

リストモナドの動作原理を考える

Haskell のリスト内包表記はとっても便利です。あまり意味がないのですが、よく出される例は、こんな感じです。

[(x,y)|x<-[1,2],y<-[3,4,5]]
→ [(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)]

このように、このリスト内包表記は、あたかも二重のループであるかのように動きます。

リスト内包表記は、実は糖衣構文であり、do に直すと以下のようになります。

do x<-[1,2]
   y<-[3,4,5]
   return (x,y)
→ [(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)]

僕は、この意味をずっと理解できませんでした。

"<-" は、モナドという箱の中から、中身を取り出します。たとえば、Just "str" から中身を取り出すと "str" となるように、Maybe モナドを理解するのは簡単です。

でも、リストから中身を取り出すとはどういうことなのか、さっぱり分かっていませんでした。昨日、新幹線の中で考えていて、ようやく理解できたので、書いておきます。

do から >>= への変形

do と >>= には以下のような関係があります。

do x <- m
   y <- n
   return (f x y)
== 
m >>= \x ->
n >>= \y ->
f x y

この規則に従って、上記の例を変形するとこうなります。

[1,2]   >>= \x ->
[3,4,5] >>= \y ->
return (x,y)
→ [(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)]

return の変形

ここでリストの return の定義を思い出しましょう。

return = [x]

よって、こう変形できます。

[1,2]   >>= \x ->
[3,4,5] >>= \y ->
[(x,y)]

>>= の変形

上記の式を以下のように考えます。

[1,2] >>= (\x -> [3,4,5] >>= \y -> [(x,y)])

次にリストの >>= の定義を思い出しましょう。

M >>= k = concatMap k m

この定義に従って、>>= を concatMap に変換すると、こうなります。

concatMap (\x -> [3,4,5] >>= \y -> [(x,y)]) [1,2]

さらに、内側の >>= を変形すると次のようになります。

concatMap (\x -> concatMap (\y -> [(x,y)]) [3,4,5]) [1,2]

concatMap を適用する

内側の concatMap を適用してみましょう。

concatMap (\x -> [(x,3),(x,4),(x,5)]) [1,2]

もう分かりますね! というわけで最後にこうなります。

[(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)]