FoldlとFoldrの違い

FoldlとFoldrの違い Alexis King 2026年9月25日 [Deep Dives] 編集者注: この記事は、foldrとfoldlの厳密版と遅延版の違いに関する、画期的な説明の再現です。2019年9月26日にhasura/graphql-engine!2933で初登場して以来、新規参入者への教育に一貫して使用されてきたため、ブログに保存する価値があると考えています。Alexis King氏がその許可を与えてくれたことに、深く感謝いたします。 まず、foldlとfoldrが「左から」や「右から」のfoldではないことを理解する必要があります。foldlとfoldrはどちらも同じ順序で構造を走査します。リストの場合は左から右です。違いはfoldの結合性です。 foldl対foldrの図解 これを考える最良の方法は図解です。foldl (⨂) v [e0, e1, e2, ..., en−1, en]と書くと、以下の計算を実行しています。 ( ... (((v ⨂ e0) ⨂ e1) ⨂ e2) ⨂ ... ⨂ en−1) ⨂ en 対照的に、foldr (⨂) v [e0, e1, e2, ..., en−1, en]と書くと、この計算を実行しています。 e0 ⨂ (e1 ⨂ (e2 ⨂ ... ⨂ (en−1 ⨂ (en ⨂ v)) ... )) 違いがわかりますか？どちらの式でも、リストの要素は同じ順序、つまり左から右へと式に現れますが、グループ化が変わります。foldlでは、(⨂)の適用は左結合ですが、foldrでは右結合です。 foldl対foldr、厳密に 問題は、この違いが実際にプログラムの動作にどのように影響するかということです。さて、まず厳密な言語でどのような違いがあるかを考えてみましょう。厳密な言語では、評価順序は常に「内側から外側へ」進み、最も深くネストされた式から始まります。まずfoldlの文脈で考えてみましょう。この式を書いたとします。 foldl (+) 0 [1, 2, 3, 4] 上記の図解から、この式が次の式と同等であることがわかります。 (((0 + 1) + 2) + 3) + 4 内側から外側へ還元すると、次の還元シーケンスが得られます。 foldl (+) 0 [1, 2, 3, 4] = (((0 + 1) + 2) + 3) + 4 = (( 1 + 2) + 3) + 4 = ( 3 + 3) + 4 = 6 + 4 = 10 対照的に、foldrを使用した場合は、同じ結果が得られます（(+)は結合的で可換な演算であるため）が、わずかに異なる還元シーケンスになります。 foldr (+) 0 [1, 2, 3, 4] = 1 + (2 + (3 + (4 + 0))) = 1 + (2 + (3 + 4 )) = 1 + (2 + 7 ) = 1 + 9 = 10 これら2つのことの実際的な違いは何でしょうか？さて、次の詳細に注意してください。foldlでは、還元を開始するためにリストの最初の要素しか必要としませんが、foldrではリストの末尾から開始し、「逆方向に」還元する必要があります。¹実際には、これはfoldlがテイル再帰可能であり、リストを一定のスペースで走査しながら還元できるのに対し、foldrはそうできないことを意味します。foldrで長さnのリストを還元するには、還元が開始される前にn個のスタックフレームを作成する必要があります。 ¹foldrがリストを左から右へ走査するにもかかわらず、「右からfoldする」と説明されることがあるのはこのためです。しかし、遅延言語では実際にはそうならないことがわかります。 foldl、遅延評価で しかし、Haskellのような遅延言語ではどうでしょうか？遅延言語では、評価順序は厳密な言語のように「内側から外側へ」進むのではなく、「外側から内側へ」進み、式の結果が要求されるまで評価されません。 厳密な言語では、foldl (+) 0 [1, 2, 3, 4]は実際には式(((0 + 1) + 2) + 3) + 4に変換されません。前述したように、これはテイル再帰ループとして実装されています。しかしHaskellでは、還元が開始される前に基本的にその式に展開されます。各(+)の適用は遅延的にソート（thunk）として保留されます。ソートを⟨⟩括弧で明示的に示すと、最終的に得られるソートは次のようになります。 ⟨⟨⟨⟨0 + 1⟩ + 2⟩ + 3⟩ + 4⟩ これらのソートは、最も外側のソートが評価されるまで強制されません。これにより、(+)が引数⟨⟨⟨0 + 1⟩ + 2⟩ + 3⟩と4に適用されます。(+)は両方の引数に対して厳密であるため、次のソートを強制し、それがさらに⟨⟨0 + 1⟩ + 2⟩と3に(+)を適用し、ソートツリー全体が還元されるまで続きます。結果は同じになりますが、実際的な観点からは、これは非常に悪いことです。なぜなら、厳密な言語でリストを一定のスペースで還元する代わりに、入力リストのサイズに線形なソートを生成しているからです！ しかし、それよりもさらに悪いことがあります。厳密な言語では、入力リスト自体がそのサイズに線形なスペースを占有するため、リストの生成/消費の全体的なスペース消費は定数倍の増加にすぎませんが、遅延言語では、リスト自体はストリームに近く、ストリーム全体がメモリに完全に実現されない場合は一定のスペースしか使用しない可能性があります。遅延foldlを使用することで、定数スペースのアルゴリズムから線形スペースのアルゴリズムに変わってしまった可能性があり、これは悪いことです！ 私たちが望むのは、厳密な言語のfoldlの動作を回復し、リストを走査しながらアキュムレータを効率的に更新し、ソートを構築しないことです。したがって、より厳密なfoldlのバージョンが必要であり、まさにfoldl'がそれです。foldl'は、リストの次の要素に進む前に⟨0 + 1⟩ソートに要求を置くため、より大きな⟨⟨0 + 1⟩ + 2⟩ソートを構築する代わりに、単に⟨1 + 2⟩ソートを構築します。foldl'は、単一の(+)の適用よりも大きなソートを構築することなく、一定のスペースでリストの走査を続けます。 foldr、遅延評価で しかし、foldrはどうでしょうか？厳密な言語では、foldrはすでにリストのサイズに線形なスペースを消費する必要があったことを思い出してください。なぜなら、還元を開始する前に基本的にリストの最後の要素が必要だったからです。実際、厳密な演算である(+)を持つ遅延foldrを考えると、これは依然として真ですが、foldlとは興味深い方法で異なります。foldlでは、リストを走査しながらソートを段階的に構築し、非常に大きくネストされたソートにつながりました。しかしfoldrでは、実際にはそれは起こりません。 なぜでしょうか？さて、しばらくの間、展開をもう一度考えてみましょう。 foldr (+) 0 [1, 2, 3, 4] = 1 + (2 + (3 + (4 + 0))) この展開がどのように得られるかを考えるために、明示的に帰納的な方法で展開を書き出してみましょう。 foldr (+) 0 [1, 2, 3, 4] = 1 + foldr (+) 0 [2, 3, 4] = 1 + (2 + foldr (+) 0 [3, 4]) = 1 + (2 + (3 + foldr (+) 0 [4])) = 1 + (2 + (3 + (4 + foldr (+) 0 []))) = 1 + (2 + (3 + (4 + 0))) これにより、foldrへの再帰呼び出しがより明確になります。厳密な言語では、foldrを呼び出すとすぐに結果を要求する必要があるため、リスト全体を走査する必要があります。しかし、ここで興味深いのは、遅延言語では、保留中のソートを持つ次の結果を実際に返すことができることです。 foldr (+) 0 [1, 2, 3, 4] = 1 + ⟨foldr (+) 0 [2, 3, 4]⟩ この結果が強制されると、⟨foldr (+) 0 [2, 3, 4]⟩は(+)によって強制され、以前と同じ還元シーケンスが得られるため、これは完全に無関係に見えるかもしれません。しかし、これは(+)が厳密な演算であるためにのみ真であることに注意してください。 代わりに、(:)のような遅延演算を使用した場合はどうでしょうか？その場合、次の展開が得られます。 foldr (:) [] [1, 2, 3, 4] = 1 : ⟨foldr (:) [] [2, 3, 4]⟩ 推測してみてください。その結果はすでに弱ヘッド正規形（WHNF）です！したがって、残りの結果が他のものによって明示的に要求されるまで、評価はそこで停止します。この場合、これは愚かな演算です。なぜなら、foldr (:) []はリストに対する複雑な恒等関数にすぎないからです。しかし、各要素を2倍するような、わずかに複雑な関数を想像することができます。 let f x xs = (x * 2) : xs in foldr f [] [1, 2, 3, 4] これは次の展開になります。 foldr f [] [1, 2, 3, 4] = ⟨1 * 2⟩ : ⟨foldr f [] [2, 3, 4]⟩ …そして再び、すでにWHNFであるため、そこで停止します。 これはどのように役立つのでしょうか？さて、例えば、次のように、結果のリスト全体を実際に消費しなかった場合はどうでしょうか。 sum (take 2 (foldr f [] [1, 2, 3, 4])) take 2はリストの最初の2つの要素しか返さないため、sumがリストとその値を強制して合計するとき、それは決して評価されません