Haskellの畳込関数に関して
Haskellを学んでいるとよく出てくる畳込関数についてまとめたいと思います。
畳込関数に関して参考の「プログラミングHaskell 第2版」には下記の記述があります。
引数にリストを取る関数の多くは、リストに対する再帰を使って、以下のような簡単な様式で定義できます。
f [] = v
f (x:xs) = x # f xs
これは下記のことを表しています。
- 引数のリストが空のときは値vを返す
- 引数のリストが空ではない場合は[先頭の要素]と[残りの要素に対して再帰的に呼び出した結果]に対して演算子#を適用させる
例えばsum関数、product関数を下記のように表現することができます。
sum [] = 0
sum (x:xs) = x + sum xs
product [] = []
product (x:xs) = x * product xs
この再帰的な模式を一般化したものが畳込関数となります。
どのような畳込関数が用意されているかみていきます。
foldr関数
foldr関数（rはrightの略称）は二項関数、初期値（アキュムレータと呼ばれる値）、リストの３つの引数を取ります。
Prelude> :t foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
foldr関数でsum関数、product関数を定義してみると下記のようになります。
sum' = foldr (+) 0
product' = foldr (*) 1
使用例は下記のようになります。
Prelude> sum' [1,2,3,4,5]
15
Prelude> product' [1,2,3,4,5]
120
foldr関数を再帰を用いて定義すると下記のようになります。
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v []= v
foldr f v (x:xs) = f x (foldr f v xs)
sum'関数では下記のような順番で計算が行われます。
foldr (+) 0 [1,2,3,4,5]
1 + (foldr (+) 0 [2,3,4,5])
1 + (2 + (foldr (+) 0 [3,4,5]))
1 + (2 + (3 + (foldr (+) 0 [4,5])))
1 + (2 + (3 + (4 + (foldr (+) 0 [5]))))
1 + (2 + (3 + (4 + (5 + (foldr (+) 0 [])))))
1 + (2 + (3 + (4 + (5 + (0)))))
1 + (2 + (3 + (4 + (5))))
1 + (2 + (3 + (9)))
1 + (2 + (12))
1 + (14)
15
foldl関数
foldl関数（lはleftの略称）はfoldr関数と同様に二項関数、初期値（アキュムレータと呼ばれる値）、リストの３つの引数を取ります。
Prelude> :t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
foldl関数でsum関数、product関数を定義してみると下記のようになります。
sum' = foldl (+) 0
product' = foldl (*) 1
使用例は下記のようになります。
Prelude> sum' [1,2,3,4,5]
15
Prelude> product' [1,2,3,4,5]
120
foldl関数を再帰を用いて定義すると下記のようになります。
foldl:: (a -> b -> a) -> a -> [b] -> a
foldl f v []= v
foldl f v (x:xs) = foldl f (f v x) xs
sum'関数では下記のような順番で計算が行われます。
foldl (+) 0 [1,2,3,4,5]
foldl (+) (0 + 1) [2,3,4,5]
foldl (+) ((0 + 1) + 2) [3,4,5]
foldl (+) (((0 + 1) + 2) + 3) [4,5]
foldl (+) ((((0 + 1) + 2) + 3) + 4) [5]
foldl (+) (((((0 + 1) + 2) + 3) + 4) + 5) []
(((((0 + 1) + 2) + 3) + 4) + 5) -- ※これを*累積変数1*とする
((((1 + 2) + 3) + 4) + 5)
(((3 + 3) + 4) + 5)
((6 + 4) + 5)
(10 + 5)
15
foldl関数とfoldr関数の使い分け
では、foldl関数とfoldr関数をどう使い分けていくべきなのでしょうか。
計算順序によって結果が異なる場合
減法のような計算順序によって結果が異なるものは注意する必要があります。
Prelude> foldr (-) 0 [1,2,3,4,5]
3
Prelude> foldl (-) 0 [1,2,3,4,5]
-15
効率を重視する場合
foldl関数を再帰を用いて定義したものを再掲します。
foldl:: (a -> b -> a) -> a -> [b] -> a
foldl f v []= v
foldl f v (x:xs) = foldl f (f v x) xs
foldl関数は末尾再帰なので呼び出し元の情報をスタックに保存する必要がなくスタックオーバーフローも発生しなくなります。
末尾再帰とは参考より下記のようなパターンを指します。
末尾再帰（まつびさいき）とは、再帰的な関数やプロシージャにおいて、自身の再帰呼び出しが、その計算における最後のステップになっているような再帰のパターンのことである。
foldl f (f v x) xsの(f v x)をv'とするとfoldl f v' xsとなり、確かに最後の箇所が自分自身の再帰呼び出しとなっていることがわかります。
末尾再帰に関してはこちらの記事がわかりやすかったです。
上記のことを考えるとfoldl関数を積極的に使用したほうが良さそうに見えますが、遅延評価により効率が悪くなります。
遅延評価では必要になったタイミングで評価を行うため、※累積変数1(((((0 + 1) + 2) + 3) + 4) + 5)では+ 5の計算が必要になったタイミングで(((((0 + 1) + 2) + 3) + 4) + 5)の計算が開始されます。この累積変数が大きくなると使用するメモリも増え、効率が悪くなります。
Data.Listモジュールでは正格評価版のfoldl'関数も用意されているのでfoldl'関数かfoldr関数を使用したほうがいいです。
Prelude> :set +s -- 実行時間、メモリ使用量表示オプション
Prelude> foldl (+) 0 [1..1000000]
500000500000
(0.43 secs, 161,293,464 bytes)
Prelude> foldr (+) 0 [1..1000000]
500000500000
(0.21 secs, 161,585,560 bytes)
Prelude> import Data.List -- foldl'が提供されているモジュール読み込み
Prelude Data.List> foldl' (+) 0 [1..1000000]
500000500000
(0.09 secs, 88,067,480 bytes)
無限リストを使用する場合
foldl関数では遅延評価によりリストの右端の値が取り出され評価されるまで計算が行われません。もし、[1..]のような無限リストを渡してしまった場合、右端の値を取り出すことが永遠にできないため計算は開始されません。
しかし、foldr関数では左端の値が取り出されたタイミングで評価され計算が開始されるため実行することが可能です。（もちろん、foldr (+) 0 [1..]の計算が終わることは永遠にないですが…）
Prelude> foldr (&&) True (cycle [False, True])
False
Prelude> foldl (&&) True (cycle [False, True])
何も返ってこない
実行環境
OS:Debian GNU/Linux 10 (buster)
GHC:The Glorious Glasgow Haskell Compilation System, version 8.4.4
Discussion