読者です 読者をやめる 読者になる 読者になる

foldlとfoldrについて理解したところと、まだよくわからないところ

Haskellネタ。
通算n度目のfold関係ぐぐり事案が発生したのでついにまとめる。
Haskell初心者どころか入門中なので間違ってたら教えて下さい。

foldl, foldrの何がわからないのか

foldlとfoldrってとっつきにくいというかfoldlは、まあ分かる。

foldl (-) 0 [1,2,3,4]
-- ((((0 - 1) - 2) - 3) - 4)
-10

foldl (\xs x -> xs ++ [x*2]) [] [1,2,3,4]
-- (((([] ++ [1*2]) ++ [2*2]) ++ [3*2]) ++ [4*2])
[2,4,6,8]

うん。

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

foldr (\x xs -> 2*x : xs) [] [1,2,3,4]
-- (1*2 : (2*2 : (3*2 : (4*2 : []))))
[2,4,6,8]

おおう。でも、まだ理解できる。 fodlの二個目の例が面倒になってるのも1:[]はOKだけど[]:1はダメってことを考えれば、すぐ理解できる。

しかし無限リストになると

take 5 $ foldl (\xs x -> xs ++ [x*2]) [] [1..]
-- (((...([] ++ [1*2]) ++ [2*2]) ++ [3*2]) ++ [4*2])...
-- 無限ループ

take 5 $ foldr (\x xs -> x*2 : xs) [] [1..]
-- (1*2 : (2*2 : (3*2 : (4*2 : (5*2: (((...
[2,4,6,8,10]

となる。 おかしい。これはおかしい。何がおかしいのかはわからないけど、なんとなくfoldlの方が値返してくれそうじゃん?foldrなんて[]までたどりつけてないし・・・。

遅延評価

っというところでググって、 発展途上猿人 : なんでHaskellのfoldrは無限リストにも使えるのか、自分なりに考えて分かったこと という神記事を発見。

なるほど遅延評価。忘れてた。

foldlの展開

つまり

foldl (-) 0 [1,2,3,4]
-- ((((0 - 1) - 2) - 3) - 4)
-10

というのは

-- ((((0 - 1) - 2) - 3) - 4)
(? - 4)
(? - 3) - 4)
(? - 2) - 3) - 4)
(? - 1) - 2) - 3) - 4)
(0 - 1) - 2) - 3) - 4)
(-1 - 2) - 3) - 4)
(-3 - 3) - 4
-6 - 4
-10

と評価されるらしい。 上の展開は引き算だから正直良い例じゃないけど foldlは全体をざっくり (? - 最後の要素)とみてから?を展開していくらしい。まじめにこつこつfoldl。 この辺りは中置関数の考えをやめて

-- ((((0 - 1) - 2) - 3) - 4)
(-) ? 4
(-) ((-) ? 3) 4
(-) ((-) ((-) ? 2) 3) 4
(-) ((-) ((-) ((-) ? 1) 2) 3) 4
(-) ((-) ((-) ((-) 0 1) 2) 3) 4

とみれば分かりやすいかも。(展開し終わった式を見て、一番左から関数を適用しようとすると自然と(-) ? 4の評価が行われる。)

foldrの展開

次にfoldrで同じ例を。

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

というのは

-- 1 - (2 - (3 - (4 - 0)))
1 - ?
1 - (2 - ?)
1 - (2 - (3 - ?))
1 - (2 - (3 - (4 - 0)))
1 - (2 - (3 - 4))
1 - (2 - -1)
1 - 3
-2 

ってなる。さっきと同じように表記を変更すると

-- 1 - (2 - (3 - (4 - 0)))
(-) 1 ?
(-) 1 ((-) 2 ?)
(-) 1 ((-) 2 ((-) 3 ?))
(-) 1 ((-) 2 ((-) 3 ((-) 4 ?)))
(-) 1 ((-) 2 ((-) 3 ((-) 4 0)))

になる。面倒なのは後回しにしてしまうちょっと不良なfoldr。 重要なのはhaskellが、(右側の)この要素いらねーなと思ったらhaskellは?の部分を評価しないということ。*1まじ不良だなfoldr。

無限リストとの戦い

次に左側の引数を返すgl(getLeft)と右側を返すgr(getRight)を考える。

let gl a _ = a
let gr _ a = a

foldl gr 0 [1..]
-- 無限ループ

foldr gl 0 [1..]
1

foldlの動作を考えると

foldl gr 0 [1..]
(((...(0 `gr` 1) `gr` 2) `gr` 3) `gr` 4) ...

となるが、これは

gr ? ...

となって評価できない。演算の右側引数が分からないということですね。もちろんglでもダメ。

一方で

foldr gl 0 [1..]
1 `gl` (2 `gl` (3 `gl` (4 `gl` 0)))

は、

gl 1 ?
gl 1 (gl 2 ?)
gl 1 (gl 2 (gl 3 ?)
gl 1 (gl 2 (gl 3 (gl ...)

となっていく。 ここで、さっきの重要pointの 「右側の引数が評価する必要のないものであった場合、haskellはそれを評価しない」 が活きてきます。すなわちgl(getLeft)は右側の引数がなんであろうと左側の引数を返すので、 gl 1 ?の時点で、1を返してきます。すごいHaskell

ちなみにfoldrでも右側引数の評価が必要なgr(getRight)を渡すと、ちゃんと死にます結果が帰ってきません。

この辺で、何故foldrが"場合によっては"*2、無限リストに対しても正しく動作するのか、何故一見ちゃんと動作しそうなfoldlでは動作しないのかが分かってきた。結局は遅延評価で項が展開されるときの挙動を把握できてなかったことが原因だった。いつもどおりの算数脳で考えて括弧付いてるところから評価するもんだと思ってた・・・。

とりあえずまじめ系foldlは分かりやすいけどストレスに弱くて、不良系foldrは分かりにくいけど極限状態でも手を抜いてがんばれるという謎の理解に達した。*3

無限リストの結合

さて、一番上の例に戻って考える。

foldl (\xs x -> xs ++ [x]) [] [1,2,3,4]

だと

(? ++ [4])
((? ++ [3]) ++ [4])
(((? ++ [2]) ++ [3]) ++ [4])
(((([] ++ [1]) ++ [2]) ++ [3]) ++ [4])
((([1] ++ [2]) ++ [3]) ++ [4])
(([1,2] ++ [3]) ++ [4])
([1,2,3]) ++ [4])
[1,2,3,4]

になる。

foldr (\x xs -> x : xs) [] [1,2,3,4]
-- (1 : (2 : (3 : (4 : []))))
[1,2,3,4]

だと

(1 : ?)
(1 : (2 : ?))
(1 : (2 : (3 : ?))
(1 : (2 : (3 : (4 : [])))
(1 : (2 : (3 : [4])))
(1 : (2 : [3,4]))
(1 : [2,3,4])
[1,2,3,4]

になる。これはOK。

では、次に無限リストを考える。 もうfoldlでは無限リストとは戦えないことはわかっているのでfoldrだけ。

foldr (\x xs -> x : xs) [] [1..]
(1 : ?)
(1 : (2 : ?))
(1 : (2 : (3 : ?)))
(1 : (2 : (3 : (4 : ...)))...

となる。これは無限に長いリストを生成するので、適当にtakeしてやると

take 5 $ foldr (\x xs -> x : xs) [] [1..]
[1,2,3,4,5]

となる。 めでたしめでたしと思うのだが、これの動作を考えると

take 5 $ foldr (\x xs -> x : xs) [] [1..]
take 5 $ (1 : ?)
take 5 $ (1 : (2 : ?))
take 5 $ (1 : (2 : (3 : ?)))
take 5 $ (1 : (2 : (3 : (4 : ?))
take 5 $ (1 : (2 : (3 : (4 : (5 : ?)))
-- take 5 $ (:) 1 ((:) 2 ((:) 3 ((:) 4 ((:) 5 ?)

となる。 うーん、なんだか大丈夫なような大丈夫じゃないような気がします。 特に[]にたどり着いてないのにリストになってるのとか気になる。 型チェックが先に行われていればtake 5 $ 以降がリストになってるのは事前に分かりそう。 foldrの定義は

:info foldr
foldr :: (a -> b -> b) -> b -> [a] -> b

らしいのでfoldr (ーー) [] [ーー]の時点で返り値がリストなのは確定だけども・・・。 takeしなくても、先頭要素からリストとして認識されているみたいだし・・・。 リスト連結の際にhaskellがどう解釈するのかが、いまいち分かってない感じです。 とりあえずは、こんなかんじで今後haskell力の上昇と共に、もう少し理解していく所存ということで終わります。

*1:引き算だと必ず左の要素も右の要素も必要なので今はあんまり関係ない

*2:正しく動作するのはgrや&&等、右側引数の評価が不要なとき

*3:分かりやすい、分かりにくいとか言ってる時点でわかってない感100%