わかったつもりになっていたけど,実はそんなちゃんとわかってなかったfoldrがこないだの「すごいH本読書会 in 大阪#4」でより理解できたのでメモ.
右たたみ込みは右から動作するわけではない
foldrは右たたみ込みというだけあって,末尾の要素から動作するのだとイメージしていた.だから,途中で値決まるのに最後まで走査するとか無駄じゃね?とか思っていた.しかし,それの思い込みはおおきな間違いだった.
アキュムレータは初期値ではない
foldrでリストのsumを求める式を例に考えてみよう.
foldr f 0 [1..5] where f n acc = n + acc
単純な足し算だけど理解しやすいように関数にした.これは以下のように展開される.
f(1, <- accが決まらないから次へ f(2, <- accが決まらないから次へ f(3, <- accが決まらないから次へ f(4, <- accが決まらないから次へ f(5, acc))))) <- 末尾だからaccは0だ!
アキュムレータは初期値ではなく,リストを展開しきったときに使う値だといえる.つまり,以下の例の場合はアキュムレータに与えたFalseという値は使われない.
foldr (\n acc = if 3 < n then True else acc) False [1..5]
どのように展開されるかは考えてみて欲しい.
foldrの実装を見ればよりよくわかる
なんでこれを理解できたかというと,読書会の最中にHoogleでHaskellのライブラリ関数の実装が読めることを教えてもらって,foldrの実装を読めばいいよと教えてもらったことがきっかけだ.foldrの実装は以下の通り.
まさに再起!再起で書くパターンはfoldrで書き換えられるってのはこういうことだったのかー!これを見れば最後まで走査しないことは一発で理解できる.今気づいたけど,最後まで走査したら無限リストに適用できないじゃないか!どう考えても根本から間違っている!!!
まとめ
- foldrは末尾要素から動作するわけではない
- アキュムレータは初期値という思い込みを棄てれば理解しやすい
- HoogleでHaskellの実装が読める
- 作者: Miran Lipovača,田中英行,村主崇行
- 出版社/メーカー: オーム社
- 発売日: 2012/05/23
- メディア: 単行本(ソフトカバー)
- 購入: 25人 クリック: 580回
- この商品を含むブログ (44件) を見る
- 作者: Miran Lipovaca
- 出版社/メーカー: オーム社
- 発売日: 2012/09/21
- メディア: Kindle版
- 購入: 4人 クリック: 9回
- この商品を含むブログを見る