HN 日本語サマリー

← 一覧へ戻る
プログラミング

FoldlとFoldrの違い

Differences Between `Foldl` and `Foldr` (blog.haskell.org)

129 pointsby signa1129 コメント

要約

この記事は、Haskellにおけるfoldlとfoldrの動作原理と、厳密評価言語と遅延評価言語での違いを解説しています。foldlとfoldrはリストの走査順序は同じですが、演算の結合順序が異なり、これがパフォーマンスやメモリ使用量に影響を与えます。特に遅延評価言語では、foldlは不必要に大きな計算の遅延(ソート)を生成する可能性があるため、より厳密なfoldl'の使用が推奨されます。

全文翻訳

foldl と foldr の違い

Alexis King 2026年9月25日

編集者注: この記事は、foldrとfoldl、およびそれらの厳密版と遅延版の違いに関する、画期的な解説の再掲載です。2019年9月26日にhasura/graphql-engine!2933で初めて登場して以来、新規参入者を教えるために一貫して使用されてきたため、ブログに保存する価値があると信じています。Alexis King氏が再掲載の許可を与えてくださったことに、深く感謝いたします。


まず、foldlとfoldrは「左から」や「右から」のfoldではないことを理解する必要があります。foldlとfoldrはどちらも同じ順序で構造を走査します。リストの場合は左から右です。違いは、foldの結合性にあります。

foldl vs 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 vs. 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はそうはできないことを意味します。長さnのリストをfoldrで還元するには、還元が開始される前にn個のスタックフレームを作成する必要があります。

¹これはfoldrがリストを左から右に走査するにもかかわらず、「右からfoldする」と説明されることがある理由です。しかし、後述するように、これは遅延言語では実際には当てはまりません!

foldl、遅延評価で

しかし、Haskellのような遅延言語ではどうでしょうか?遅延言語では、評価順序は厳密な言語のように「内側から外側へ」進むのではなく、「外側から内側へ」進み、式の結果が要求されるまで評価されません。

厳密な言語では、foldl (+) 0 [1, 2, 3, 4]は実際には(((0 + 1) + 2) + 3) + 4という式に変換されるわけではありません。前述したように、これは末尾再帰ループとして実装されています。しかし、Haskellでは、還元が開始される前に基本的にその式に展開されます。各(+)の適用は遅延評価され、thunkとして保留されます。

thunkを⟨⟩ブラケットで明示的に示すと、最終的に得られるthunkは次のようになります。

⟨⟨⟨⟨0 + 1⟩ + 2⟩ + 3⟩ + 4⟩

これらのthunkは、最も外側のthunkが評価されるまで強制されません。これにより、(+)が引数⟨⟨⟨0 + 1⟩ + 2⟩ + 3⟩と4に適用されます。(+)は両方の引数に対して厳密であるため、次のthunkを強制し、それがさらに⟨⟨0 + 1⟩ + 2⟩と3に(+)を適用し、ツリー全体が還元されるまで続きます。

結果は同じになりますが、実際的な観点からはこれは非常に悪いです。なぜなら、厳密な言語でリストを定数空間で還元したのとは異なり、ここでは入力リストのサイズに線形なthunkを作成しているからです!さらに悪いことに、厳密な言語では、リスト自体がそのサイズに線形なスペースを消費するため、リストの生成/消費全体の空間消費は定数倍の増加にすぎませんが、遅延言語では、リスト自体はストリームに近く、ストリーム全体がメモリに完全に実現されない場合は定数空間しか使用しない可能性があります。遅延foldlを使用することで、定数空間アルゴリズムから線形空間アルゴリズムに悪化させた可能性があります!

私たちが望むのは、厳密な言語のfoldlの動作を回復し、リストを走査しながらアキュムレータを効率的に更新することであり、thunkを構築しないことです。したがって、foldlのより厳密なバージョンが必要であり、まさにそれがfoldl'です。foldl'は、リストの次の要素に進む前に、⟨0 + 1⟩ thunkに要求を置くため、より大きな⟨⟨0 + 1⟩ + 2⟩ thunkを構築する代わりに、単純に⟨1 + 2⟩ thunkを構築します。foldl'は、単一の(+)適用よりも大きなthunkを構築することなく、定数空間でリストの走査を続けます。

foldr、遅延評価で

しかし、foldrはどうでしょうか?厳密な言語では、foldrはすでにリストのサイズに線形な空間を消費する必要があったことを思い出してください。なぜなら、還元を開始するために基本的にリストの最後の要素が必要だったからです。実際、厳密な演算である(+)を持つ遅延foldrを考慮すると、これは依然として真実ですが、foldlとは興味深い異なる方法です。

foldlの場合、リストを走査しながら段階的にthunkを構築し、非常に大きくネストされたthunkにつながりました。しかし、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を呼び出すとすぐに結果を要求する必要があるため、リスト全体を走査しなければなりません。しかし、ここで興味深いことが起こります。遅延言語では、実際には次の結果を、保留中のthunkとともに返すことができます。

  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]⟩

推測してください?その結果はすでにweak-head normal form (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がリストとその値を強制して合計するとき、⟨foldr f [] [3, 4]⟩というthunkは決して評価されず、リストは部分的にしか走査されません。

これの含意は何でしょうか?さて、これは、還元関数が2番目の引数で遅延評価される場合、foldrは作業を節約できる可能性があることを意味します。そして、結果リストが完全に消費されない場合です。実際、foldrはこの方法で無限リストを処理できますが、foldlはできません。また、foldrはfoldlよりも多くのリスト融合の対象となる可能性があることも意味しますが、それは別の議論です。

foldl vs. foldr、遅延評価で

さて、簡単に要約すると、これまでに述べたことは次のとおりです。

  1. 遅延言語では、リストに対するfoldlは、あまりにも遅延評価されるため、大きなthunkを構築するため、悪い。foldl'を使用すると、thunkを段階的に強制し、リストを定数空間で消費できます。
  2. 遅延言語では、リストに対するfoldrは、遅延評価されるため、還元関数が2番目の引数で遅延評価される場合、作業を節約できるため、良い。

これら2つのことは少し矛盾しているように見えるかもしれません。なぜfoldlは遅延評価されるために悪く、foldrは遅延評価されるために良いのでしょうか?

違いを理解するために、foldrで行ったように、foldlを帰納的に展開してみましょう。

  foldl (+) 0 [1, 2, 3, 4]
= foldl (+) (0 + 1) [2, 3, 4]
= foldl (+) ((0 + 1) + 2) [3, 4]
= foldl (+) (((0 + 1) + 2) + 3) [4]
= foldl (+) ((((0 + 1) + 2) + 3) + 4) []
= ((((0 + 1) + 2) + 3) + 4)

違いがわかりますか?foldrでは、再帰呼び出しは結果の式ツリーの「葉」に押し込まれましたが、foldlでは、再帰呼び出しは常にルートになります。これは、ちなみに、foldlが末尾再帰的である理由です。これはまさに末尾再帰が何であるかです!しかし、リスト全体が走査されるまでWHNFになることがないため、遅延評価されることはありえません。

これにより、リストに対するfoldlとfoldrの使用に関する一般的な経験則が得られます。

  1. 累積関数が厳密な場合、リストを定数空間で消費するためにfoldl'を使用してください。なぜなら、リスト全体がどちらにしても走査される必要があるからです。
  2. 累積関数が2番目の引数で遅延評価される場合、ストリーミングと作業の節約を改善するために、段階的に作業を行うためにfoldrを使用してください。
  3. foldlまたはfoldr'は絶対に使用しないでください。リストでは常に劣っています。

あなたのケースでは、適用している累積関数はMap.deleteであり、これは厳密なので、foldl'を使用すべきです。

とはいえ、これはしばしばマイクロ最適化なので、リストが大きくない場合は、通常はあまり重要ではありません。ただ良い習慣であり、実践における遅延評価の素晴らしい例なので、理解する価値があります。

追加: 他のデータ構造でのfoldlとfoldr

最後に、疑問に思うかもしれません。もしfoldlとfoldr'がそれほど役に立たないなら、なぜ存在するのでしょうか?なぜfoldl'とfoldrだけではいけないのでしょうか?

答えは、私が今言ったことはすべてリストにしか適用されないということです。この動作は、基本的に(:)が右結合演算であるため、「リストの残りの部分」が右側にあるため起こります。しかし、スノックリスト(snoc lists)があった場合、次のようになります。

data SnocList a = Nil | Snoc (SnocList a) a

…リストは左結合になり、通常のリストでfoldl'を使用する状況でfoldr'を使用し、通常のリストでfoldrを使用する状況でfoldlを使用することになります。少し混乱しますね?

通常のコンスリストとスノックリストは、基本的にfoldl対foldrの2つの極端ですが、実際には、他のデータ構造ははるかに曖昧です。たとえば、ツリーがある場合、次のようになります。

data Tree a = Leaf | Branch (Tree a) a (Tree a)

…一部の要素は左側にあり、他の要素は右側にあり、foldlもfoldrも明確に優れているわけではありません。その場合、パフォーマンスが本当に本当に重要なら、foldMapとfoldMap'が通常最良の選択肢です。なぜなら、それらは(<>)への呼び出しの特定の結合性を指定しないからです。ただし、base-4.13.0.0までfoldMap'は利用できず、GHC 8.8.1に切り替えるまで利用できません。(しかし、真実は、おそらくどちらにしても問題ないということです。)