Haskell の sequence 関数 - foldr をイメージして

「Haskell の mapM_ – foldr と (>>) を意識して」のつづき

1. mapM_ 関数を理解するには、sequence 関数の理解が不可欠

前回は、

mapM_ 関数

の動作について見た。しかし、どうも感覚的に全然身に付いていない。

mapM_ を使おうとすると、

「あれ？一体これ何してるんだっけ」

と考え込んでしまう。返り値に関心のある mapM にしても同じ。

多分、この関数のベースとなっている

• sequence 関数

をちゃんと理解してないために、頭の中にイメージを描けないと思う。 (+_+)

Prelude には、

sequence :: Monad m => [m a] -> m [a]

   Evaluate each action in the sequence from left to right, and collect the results.

型を見れば、わかるように、sequence 関数は、Monad が関わってくる。

ところで、モナドな計算について理解しようとすると、途端に具体的なものが、遠のき霧の中に隠されてしまう感覚を抱く。詳細なことを、一々考えないで済むのが抽象化のメリット。しかし、モナドに関しては、詳細を考えないで済ませることができない。共通の構造として存在するものを理解し、抽出する方法を学ばなけれど、いつまで経ってもブラックボックスをいじっているという感覚から抜け出せない。

 

2. モナドのイメージ

「モナドとは何か」について様々な説明がされる。

例えば、

モナドは値およびその値を使う計算の並びという観点からいえば、計算を構造化 する方法です。

(All About Monads のIntroduction より)

これをはじめて読んだとき、何が言いたいのかサッパリわからなかった。

しかし、今理解している範囲で「モナドのイメージってどんな感じ？」と言われたら、やはり Monad クラスの (>>=) の説明を元に想像している。

Sequentially compose two actions, passing any value produced by the first as an argument to the second.

(Prelude より)

「アクション」と言われるとわかりずらいので、「計算」 と置き換えて読んでいる。つまり、

二つの計算をつなげるとき、先行する計算の結果を、後続の計算の引数とする。

頭の中のイメージは、

(>>=) による計算のつなげ方にはバリエーションがある。値を含む「包み」の種類によって計算の仕方が異なる。

例えば、以下のように、Maybe, [ ], State s の型コンストラクタが「包み」で、それぞれの型コンストラクタに応じて計算の方法が定義される。

Prelude の Moand の説明では、

it is best to think of a monad as an abstract datatype of actions.

モナドを、アクションの抽象データ型の一種だと考えておけばよいと。

モナドと言われた場合、このような大雑把なイメージを頭に浮かべている。イメージが浮かぶから、ある程度わかった気になるれる。数学嫌いの文系人間なのでこの程度の想像で「まぁよし」と。

 

3. foldr の動作イメージ

モナドな計算のイメージはできているとして、mapM 関数に話を戻す。この関数をイメージできない原因となっている sequence 関数。

Source を見ると以下のように定義されている。

sequence       :: Monad m => [m a] -> m [a] 
sequence ms = foldr k (return []) ms
            where
              k m m' = do { x <- m; xs <- m'; return (x:xs) }

これを見て、すぐに理解できるほど、foldr 関数に馴染んでないので、もう一度ここから考え直し。 (+_+)

ところで、foldr をイメージをするとき一番参考になったのは下図だった。

Fold (higher-order function) - Wikipedia, the free encyclopedia via kwout

リストの要素間に、関数を適用していく様子がイメージしやすい。

これを元に、具体的な場合に当てはめて考える。

 

リストの要素がモナドでない場合の foldr 関数の動作イメージ

まずは、リストの要素がモナドではない場合の概念的なイメージから。

例として次の場合。

foldr (+) 0 [1,2,3,4]

最初に、foldr の計算のためにツリーをイメージ。その後、対象であるリストの要素を木の左の葉に割り当てる。加えて、foldr の第 2 引数である 0 を木の一番下の右の葉へ。

次に、二項演算子 (+) を一番下の二つの葉に適用して 4 という結果を生成。これを木のルートの方へ繰り返し最終的な結果を得る。

 

sequence 関数における foldr の動作イメージ

sequence 関数の定義を再掲。

sequence       :: Monad m => [m a] -> m [a] 
sequence ms = foldr k (return []) ms
            where
              k m m' = do { x <- m; xs <- m'; return (x:xs) }

foldr が使われている行を見ると、k が二項演算子で、第 2 引数に、「空リストがモナドで包まれたもの」が与えられているのがわかる。これを先ほどと同じようにイメージする。

要素がモナドであるリストを、木の左の葉に割り当てる。次に、一番下の右の葉に、「モナドで包まれた空リスト」を置く。

次に 二項演算子 k を一番下の葉に適用。

関数 k の定義で、do 式を使わないなら、

括弧を明示的に付けるなら、

こうすると、関数が内側へ内側へとネストしつつ、 (>>=) で第 1 引数の計算の結果を第 2 引数の計算へと受渡している感じがつかみやすい。

最後の return に注目すると、左の葉のモナドな計算から結果を取り出し、それを右の葉のモナドな計算の結果から取り出したリストの先頭へ (:) を使って追加し、最後に return でまたモナドに包んで返しているのがわかる。

結局、大雑把に言って、sequence 関数は与えられたモナドのリストの個々の中身を取り出し、リストに追加したら、そのリストをまたモナドで包んで返すことを繰り返す。

 

4. 具体的な型で sequecne 関数を試す

Maybe  a

一番わかりやすい例は Maybe a 型のリストに sequence 関数を適用したとき。

*Main> sequence [Just 1, Just 2, Just 3, Just 4]
Just [1,2,3,4]

各々のJust で包まれた数値がリストにまとめられ、再び Just で包まれている。

 

[a]

リストの場合は、

*Main> sequence [[1,2],[3,4,5]]
[[1,3],[1,4],[1,5],[2,3],[2,4],[2,5]]

むむむ…(@_@; 複雑な結果になった。

先ほどの foldr のイメージを思い出しながら考えると、最初の計算は以下のようになる。

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

次に、上記の結果を元にして、

*Main> [1,2] >>= \x -> [[3],[4],[5]] >>= \xs -> return (x:xs)
[[1,3],[1,4],[1,5],[2,3],[2,4],[2,5]]

 

 

State s a

State モナドの場合は、「初期値と増分を持つカウンター」を対象にして考える。

以下の next 関数はカウンターの値を増分だけ増やす関数。返される値のタプルの第 1 要素は next により値を更新する前の値であるとして定義。これを State モナドで包んでリストにし、それに対して sequence 関数を適用する。

import Control.Monad.State

data Counter = Counter { val, step :: Int } deriving Show

next :: Counter -> (Int, Counter)
next (Counter v s) = (v, Counter (v+s) s)

main = let s = sequence [State next, State next, State next]
       in print $ runState s $ Counter 0 1

結果は、

([0,1,2],Counter {val = 3, step = 1})

State モナドの場合、State s a 型なので、State s が包みで a が計算をつなげると次に渡される結果。よって、タプルの第 1 要素がリストに集められ、第 2 要素は State モナドがつなげられるごとに背後で カウンタの状態が更新されていく。

うーん、やはり sequence 関数の動作のイメージができても、個々のモナドの (>>=) による計算のつなぎ方もイメージできてないと難しいなぁ。。

 

関連記事

• Haskell の mapM_ – foldr と (>>) を意識して