[Haskell] foldlとfoldrに非正格な関数を渡した際の動作の違い

背景

Haskellを学んでいると、「foldrは無限リストを扱える」といったことを聞きます。しかし、なぜfoldrは計算を途中で打ち切れるのか、いまいち理解ができていませんでした。

そこで本記事では、foldlとfoldrに非正格な関数(例: (||), (&&))を渡した場合、なぜfoldrは計算を打ち切れるのに、foldlは打ち切れないのかを調べてみました。

正格な関数と非正格な関数

まず正格な関数と非正格な関数について説明します。

• 正格な関数: 結果を計算するために、必ず引数を評価する関数
  • 例: (+), (*)
  • 1 + undefined → エラー(両方の引数を評価する必要がある)
• 非正格な関数: ある引数について評価しなくても結果を返せる場合がある関数
  • 例: const, (&&), (||)
  • const 1 undefined → 1 (第二引数を評価しない)
  • False && undefined → False (第二引数を評価しない)
  • True || undefined → True (第二引数を評価しない)

ここで重要なのは、非正格な関数はその引数を評価しなくても結果が出る場合があるという点です。
この性質がfoldrで計算を打ち切れる仕組みに関係しています。

foldrとfoldlの違い

foldrで計算を打ち切れる仕組み

foldrは以下のような定義になっています。

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

foldrの実装では1ステップ展開すると式の外側が f x (...) の形になります。
このときfが第2引数を要求しない（短絡できる）なら、第2引数である foldr f z xs を評価する必要がないため、残りのリストの処理がスキップされます。

foldlで打ち切れない理由

foldlの定義を見ると:

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f z []     = z
foldl f z (x:xs) = foldl f (f z x) xs

foldlの実装では、リストが [] になるまで式の外側がずっと foldl ... の形のままです。
つまり、foldl f z [] = z の分岐に到達しない限り結果を返せないため、結果を得るにはリストの末尾（[]）まで到達する必要があり、途中で打ち切れません。

重要なのは、f 自体が短絡的であっても、外側の foldl の再帰は止まらないという点です。foldl は結果を返すにはリストが [] になるところまで到達する必要があります。

実例で確認

foldrの実例: (||)を使った場合

実例として、 (||) を使った非正格な計算を foldr で実行した際の例を紹介します。
以下のようなリストを対象に foldr を行います。

foldr (||) False [False, True, False]

展開していくと以下のような流れで計算されます。

1. False || (...)では、第二引数を評価する必要がある
2. True || (...)では、(||)の定義により第二引数を評価しないため、計算を打ち切る

foldr (||) False [False, True, False]
= False || (foldr (||) False [True, False])      -- 展開
= False || (True || (foldr (||) False [False]))  -- さらに展開
= False || True                                      -- True || ... は True になるので第二引数を評価しない
= True

無限リストでも動作する

この仕組みにより計算が打ち切られるため、 (||) のように短絡できるfのときは、無限リストでも有限時間で結果が得られます。

foldr (||) False (False : True : repeat False)
= False || (True || (...))
= False || True
= True

foldlの実例: (||)を使った場合

foldrと同じ計算を、今度はfoldlで実行してみます。
以下のように有限リスト [False, True, False] を対象に foldl を行います。

foldl (||) False [False, True, False]

foldrとは異なり、foldlでは展開していってもfoldlが繰り返し左に出てきます。
そのため、以下のような流れで計算が行われます。

1. foldlを展開しても式の外側はずっと foldl ... の形のままなので、リストが空になるまで再帰が進む
2. その後展開された式を順次評価していく

foldl (||) False [False, True, False]
= foldl (||) (False || False) [True, False]            -- 1回目: アキュムレータに蓄積
= foldl (||) ((False || False) || True) [False]        -- 2回目: さらに蓄積
= foldl (||) (((False || False) || True) || False) []  -- 3回目: さらに蓄積
= ((False || False) || True) || False                  -- リストが空になり、ここで初めて評価開始
= (False || True) || False
= True || False
= True

無限リストでは終了しない

この特性は、無限リストでは致命的になります。
リストが空にならないため、アキュムレータの評価が永遠に始まらず、計算が終了しません。

foldl (||) False (False : True : repeat False)
= foldl (||) (False || False) (True : repeat False)
= foldl (||) ((False || False) || True) (repeat False)
= foldl (||) (((False || False) || True) || False) (repeat False)
= ... -- 無限に続く(リストが空にならない)

補足: foldl'について

HaskellのData.Listには、正格版のfoldl'が用意されています:

foldl' :: (b -> a -> b) -> b -> [a] -> b

foldl'は、各ステップでアキュムレータを強制的に評価するため、thunkが蓄積しません。
ただしfoldl'でも無限リストが終わるわけではありません。

foldl' (+) 0 [1,2,3]
= foldl' (+) 1 [2,3]      -- 0+1 が評価されて 1
= foldl' (+) 3 [3]        -- 1+2 が評価されて 3
= foldl' (+) 6 []         -- 3+3 が評価されて 6
= 6

まとめ

本記事では、foldrとfoldlに非正格な関数を渡した場合の動作の違いを見てきました。

• foldr: 1ステップ展開すると式の外側が f x (...) の形になるため、fが第2引数を要求しなければ、残りのリストの処理をスキップできる
• foldl: 式の外側がずっと foldl ... の形のままなので、リストが空になるまで再帰が進み、途中で打ち切ることができない

この違いにより、foldrは (||) のような短絡可能な関数と組み合わせることで無限リストでも計算を終了できますが、foldlでは無限リストが終わりません。

適切にfoldr/foldlを使い分けることで、より効率的なHaskellプログラムを書くことができます。