Haskellの畳み込みを完全に理解する

前回の記事

前回の記事はこちら。

今回はすごいH本の畳み込みを。

foldlとfoldr

畳み込みは2引数関数とアキュムレータの初期値、対象のリストを受け取る。

foldl

左畳み込みでは**リストの左（先頭）**から順に適用されていく。

Prelude> foldl (+) 0 [1,2,3]
6

これは内部的には、以下のような推移をしているものと思われる。

foldl (+) 0 [1,2,3]
foldl (+) (0+1) [2,3]
foldl (+) ((0+1)+2) [3]
foldl (+) (((0+1)+2)+3) []
(((0+1)+2)+3)
((1+2)+3)
(3+3)
6

遅延評価なので積算値も都度評価されずスタックに積まれていく感じのはず（間違ってたら申し訳ない）。

曖昧なのもなんなので調べてみると、こんな記事を見つけた。

そのため、アキュムレータに1が送られた後でも、0と1の加算は行われず、0+1としてアキュムレータに蓄えられる。これは、最後の数が入るまで続く。最後に7が送られてきたとき初めて加算が行われる。

ということで、アキュムレーターには遅延評価でスタックが積まれていく挙動のようだ。

foldr

右畳み込みでは**リストの右（後方）**から順に適用されていったのと同じ結果を返す。

ここで、書籍にならい型の違いを見る。

Prelude> :t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
Prelude> :t foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

どうもすごいH本にはFoldableという型クラスではなく[a]のようにリストの関数で書かれているので、実装が変わっているっぽい。

-- 本だとこう書いてある
ghci> :t foldl
foldl :: (a -> b -> a) -> a -> [b] -> a
ghci> :t foldr
foldr :: (a -> b -> b) -> b -> [a] -> b

と思ったらこんな記事を見つけた。Foldableは2010年に導入されたらしい。うーん、まだ登場していないモナドとかの概念を理解してないとキツそう。ということで、現時点では深く考えないこととする。

とにもかくにも2引数関数の引数順が(b -> a -> b)と(a -> b -> b)で異なることがわかる。

これは先ほどの左畳み込みが(((0+1)+2)+3)のようにアキュムレーターに対して各要素を右側から作用させていく様子からもわかる。

つまり右畳み込みの場合は、このような推移を取ると想像される。

foldr (+) 0 [1,2,3]
foldr (+) (3+0) [1,2]
foldr (+) (2+(3+0)) [1]
foldr (+) (1+(2+(3+0))) []
(1+(2+(3+0)))
(1+(2+3))
(1+5)
6

が、一方で、すごいH本によれば、あくまで右畳み込みは最終結果が上の形に準じるだけで、リストからの値の取得は先頭から行っているらしい。このあたりはよくわからないが、とりあえず頭の中では上記の式展開ができていればいい気がする。

で、計算量的な話をすると、foldrだとアキュムレータがリストの場合に\x acc -> f x : accという形で先頭に追加となるので$O(1)$になって具合がよい。つまりリストへの積算は右畳み込みを使用するべき。

正格と無限リスト

理解が不安だったので探してみるとこんな記事を見つけた。

どうも正格な関数では遅延評価せずにアキュムレータを随時計算するようだ。

そしてfoldrは、無限リストに対しても使用できるとある。右から取ってくるのに無限に適用できるという意味が最初まったくわからなかったのだが、これも遅延評価を考えると理解ができた。

たとえば以下を考える。

Prelude> foldr (:) [] [1,2,3]
[1,2,3]

畳み込みは以下と同等となるように値を返す。

foldr (:) [] [1,2,3]
foldr (:) 3:[] [1,2]
foldr (:) 2:3:[] [1]
foldr (:) 1:2:3:[] []
1:2:3:[]
1:2:[3]
1:[2,3]
[1,2,3]

しかし、実際にはこれは再帰的に処理されているようだ。つまり、遅延評価でリストの先頭から値を順に取っている。

とりあえず、この推測が正しいことを確認するために自作の右畳み込み関数myfuncを実装してみた。

myfunc :: (a -> b -> b) -> b -> [a] -> b
myfunc f acc [] = acc
myfunc f acc (x:xs) = f x (myfunc f acc xs)

そして、無限リストに対して作用させる。

Prelude> take 5 $ myfunc (:) [] [1..]
[1,2,3,4,5]

これは、本物のfoldrと同じ結果を返す。

foldr (:) [] [1..]
1:(foldr (:) [] [2..])
1:2:(foldr (:) [] [3..])

あくまで右から畳み込んだように見えるだけで、内部的には再帰的な処理となっているということだろう。

そして、対象が無限リストであっても、この形であれば先頭は逐次取得が可能である。ようやくちゃんと理解できた気がする。

左畳み込みでは無限リストへの作用ができない

これも確認しておきたい。foldrとfoldlの引数順を明示するためにラムダ式に展開して比較したのが以下だ。

Prelude> foldr (\x acc -> x : acc) [] [1..5]
[1,2,3,4,5]

Prelude> foldl (\acc x -> acc ++ [x]) [] [1..5]
[1,2,3,4,5]

ここで、自作のfoldlを作ろう。

myfunc :: (a -> b -> a) -> a -> [b] -> a
myfunc f acc [] = acc
myfunc f acc (x:xs) = myfunc f (f acc x) xs

こうなると再帰の深さが限定されていても、常に無限リストの末尾を含む評価が残ってしまう。

つまり、以下のような展開になる。

foldl (\acc x -> acc ++ [x]) [] [1..]
foldl (\acc x -> acc ++ [x]) ([] ++ [1]) [2..]
foldl (\acc x -> acc ++ [x]) (([] ++ [1]) ++ [2]) [3..]

こうなると内側に再帰が下っていくため、takeなどを使っても先頭から逐次解決することができない。つまり、左畳み込みは無限リストには適用できない。

ようやくすごいH本の言っている意味が腹落ちした。

つづく

俺たちの冒険はまだまだ終わらない！タナイ先生の次回作にご期待ください。