yashiganiの英傑になるまで死ねない日記

週末はマスターバイクでハイラルを走り回ります

foldrやっとわかった

わかったつもりになっていたけど,実はそんなちゃんとわかってなかった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の実装が読める

すごいHaskellたのしく学ぼう!

すごいHaskellたのしく学ぼう!

すごいHaskellたのしく学ぼう!

すごいHaskellたのしく学ぼう!