foldr と foldl の違い
foldr とは cons リスト上の fold であり, foldl とは snoc リスト上の fold を cons リスト上でシミュレートしたものである. よって foldr の方が美しい. 終わり.
ではなくてもう少しきちんと説明する.
よく使われる単方向リストは, 2 引数をとる cons と 0 引数をとる [] の 2 個のコンストラクタを持つデータ構造である. cons は値とより後ろの部分リストを持つタプルであり, [] は空リスト, 言い換えるとリストの終端である. これを cons リストといい, 通常左から右に伸びるように図示される. また, 逆方向に伸びるリストも考えられて, それは snoc リストと呼ばれる.
cons リストのコンストラクタを 2 項演算子と定数で置換する機能を持つ高階関数が, foldr であり, データ構造から見て自然な定義である. 一方, 実際のデータ構造は cons リストであるが, snoc リストだと思って置換するのが foldl である.
計算上の違いを言うと
foldrは 2 項演算子を右に結合させるが,foldlは左に結合させる,foldrは定数 (初期値) を右端に与えるが,foldlは左端に与える,
といったものがある. すなわち, 結合性 と (少なくとも定数についての) 可換性 が 2 項演算子にあれば, どちらを使っても結果には影響しないということになり, 使い分けの必要性が生じる. この辺のことをリストの(第一)双対定理と言ったりする.
使い分けの基準としては, 大体 foldl で,
だけ foldr を使うことになる.
foldl が基本なのは, foldl が先頭からリストを展開していくと同時に少しずつ計算してイメージになるのに対して, foldr はリスト全体を展開してようやく計算を始められるイメージなので, 結局全体を見ないといけないならコツコツ計算した方が良くなるからである.
一方, 非正格な場合には, 後ろの計算を省略できるかは前から逐次計算している場合には最後まで計算しないとわからないし, 順序によって計算量が変わってしまう場合には, 一般論を言うのは非常に難しい.
foldl と foldl' の違い
Haskell のような遅延評価が基本の言語では, 前から順番に...というのは機能しない. 必要になってからというスタイルだと, 結局先頭部を評価する段階でリスト全体を展開してしまうことになる. すなわち, スタックを浪費する問題が生じる.
そのため Haskell には foldl' がある. これは, 正格評価版なのできちんと前から評価する. 当たり前であるが, 正格でない関数のときには foldl なら止まったのに, foldl' だと止まらないということが起こりうる. 要するに 正格性 が必要な条件である.
ノーコストでは手に入らないということに気をつけよう.
