foldl と foldr の本質的な違い：厳密・非厳密評価の観点から

Alexis King による深層考察。Haskell の

foldl

foldr

1. 概念的な違い：結合性の理解

foldl

foldr

計算式の比較

-- foldl の計算式：左結合 (Left Associative)
foldl (⨂) v [e0, e1, e2, ..., en]
-- ↓展開後
( ... (((v ⨂ e0) ⨂ e1) ⨂ e2) ... ) ⨂ en

-- foldr の計算式：右結合 (Right Associative)
foldr (⨂) v [e0, e1, e2, ..., en]
-- ↓展開後
e0 ⨂ (e1 ⨂ (e2 ⨂ ... (en ⨂ v)))

厳密な言語における挙動

厳密な言語では「内側から外へ」評価されます。

foldl

foldl (+) 0 [1, 2, 3, 4]
= (((0 + 1) + 2) + 3) + 4
-- 計算順序
(( (0+1)+2 ) + 3) + 4 
→ (( 3    +2 ) + 3) + 4 
→ (   5          + 3) + 4 
→      8                + 4 
→         10

• 特性: 定数空間（Constant Space）で処理可能。尾再帰的（Tail Recursive）。
• 要件: リストの先頭の要素のみがあれば計算開始可能。

foldr

foldr (+) 0 [1, 2, 3, 4]
= 1 + (2 + (3 + (4 + 0)))
-- 計算順序（右から内側へ）
1 + (2 + (3 +      4 )) 
→ 1 + (2 +           7)  
→ 1 +                9    
→                  10     

• 特性: スタック深度 $N$ に比例した記憶領域を消費する（再帰的な性質のため）。

注意:

foldl

が「左から探索」と言われるのは誤解ではなく、結果が得られる準備としてリスト全体を読み込む必要があるためです。一方、

foldr

は「右から結合」するため、末尾要素を深くネストした形で保持する必要があります。

2. 非厳密な言語（Haskell など）における

foldl

の問題点

非厳密な言語では、評価順序が「外側から内側へ」になります。式は展開されず、計算結果が求められた瞬間までThunk（遅延評価された表現） として保持されます。

foldl

が生成する Thunk ツリー

-- foldl の展開
foldl (+) 0 [1, 2, 3, 4]
-- ↓厳密な言語なら
(((0 + 1) + 2) + 3) + 4

-- 非厳密な言語では（Thunk は ⟨ ⟩ で表記）
⟨⟨⟨⟨0 + 1⟩ + 2⟩ + 3⟩ + 4⟩

メリット・デメリット

• メリット: 結果が要求されるまで計算を保留できる。
• デメリット:
  • 入力リストのサイズに比例した巨大な Thunk ツリーが構築される。
  • リストをストリームとして処理する際、メモリ使用量が定数ではなく線形になる（空間効率の低下）。
  • 定数空間アルゴリズムが実質的に線形空間アルゴリズムに堕してしまうリスクがある。

解決策：

foldl'

の使用

巨大な Thunk を構築せず、各ステップで評価を強制的に行うための

foldl'

動作原理:

-- foldl' は直前の結果を計算してから次の処理へ進む
⟨0 + 1⟩ -- (ここで評価が強制される) → 1
→ 1 + 2  -- (次に評価) → 3
→ ...

• 効果: 定数空間内で効率的にリストを消費し、不要な巨大な Thunk を回避できます。

3. 非厳密な言語における

foldr

の強み

非厳密な言語において、

foldr

結合子による挙動の違い

厳密な演算の場合（例：

+

）

foldr (+) 0 [1, 2, 3, 4]
= 1 + ⟨foldr (+) 0 [2, 3, 4]⟩ -- 未評価の Thunk が残る

結果が要求されるまで

+

非厳密な演算の場合（例：リスト構築

(:)

）

foldr (:) [] [1, 2, 3, 4]
= 1 : ⟨foldr (:) [] [2, 3, 4]⟩
-- ↓この時点で Weak Head Normal Form (WHNF) になり、評価停止
[1, 2, 3, 4] -- (リストとしての構造は即時に構築される)

• (:)

  は左演算子（Cons）であり、先頭要素と尾部の Thunk を保持するだけで済むため、即座に結果として認識されます。

無限リストへの適用

この特性により、

foldr

foldl

foldl'

部分リストの利用例

-- foldr を使うことで、必要な要素のみを処理できます
sum (take 2 (foldr f [] [1, 2, 3, 4])) 
where 
    f x xs = (x * 2) : xs -- 非厳密な累積関数

• 上記では

  take 2

  で先頭 2 つ要素だけを取得するため、残りの

  foldr

  の呼び出し（

  [3, 4]

  など）は決して評価されません。計算リソースが節約されます。

4. まとめ：データ構造と累積関数による選択ガイド

foldl

foldr

基本的な経験則

1. 累積関数が厳密な場合（例：合計、最小値など）

   • 推奨:

     foldl'

     を使用。
   • 理由: リスト全体を探索するため、定数空間で処理する必要がある。非厳密な

     foldl

     はメモリ効率が悪すぎる。

2. 累積関数が第二引数（尾部）に対して非厳密な場合（例：リスト構築、無限リスト処理）

   • 推奨:

     foldr

     を使用。
   • 理由: 結果を即時に要求できず、ストリーミング処理や部分計算が可能なため。

3. 常に避けるべき組み合わせ

   • ❌

     foldl

     （非厳密な関数でリスト全体を探索する場合）：巨大な Thunk を生成する。
   • ❌

     foldr'

     （存在しないが、冗長な概念）：通常不要。

具体的なコード例

厳密な処理が必要な場合（Map.Delete など）

-- Map.delete は厳密な関数（結果を確定させる必要があるため）
-- よって foldl' を使用すべき
let result = foldl' (\m k -> m `delete` k) map [x1, x2, x3]

※ リストサイズが小さければ微調整レベルですが、習慣として

foldl'

部分処理が必要な場合

-- 必要なリストの先頭のみを取得する場合
take 5 (foldr (\x acc -> x : acc) [] [1..]) -- 無限リストも扱える

補足：他のデータ構造について

• Snoc リスト:

  foldl

  と

  foldr

  の役割が逆転します（右結合性が左側にあり）。
• ツリーなどの木構造: 明確な左右の区別がないため、通常は

  FoldMap

  や

  FoldMap'

  を使用するのがベストプラクティスです。

結論: 適切なデータ構造と累積関数を選ぶことで、パフォーマンスと可読性を両立させられます。