1. リストを畳み込む foldl と foldr
Haskell のサンプルコードを見ていると、よく見かける foldl と foldr 。名前からして両者は対照的な関数のようだ。
Prelude の List Operation の分類において、
として、わざわざ分類されているところを見ると、重要な関数なのだろう。 (@_@)
そういえば、Reduce と言えば、Python の関数 reduce を思い出した。
これと似たものなのかな？
2. どのように計算が行われるのか
「foldr と foldl の違い - 言語ゲーム」によると、foldr, foldl は、以下のように計算が行われる。
foldr (+) 4 [1, 2, 3] -- 1 + (2 + (3 + 4)) == 10 foldl (+) 1 [2, 3, 4] -- ((1 + 2) + 3) + 4 == 10
なるほど、これは Python の reduce() と同じ役割の関数のようだ。
Python の「2.1 組み込み関数」によると、
reduce(labmda x, y: x+y, [1, 2, 3, 4, 5])は((((1+2)+3)+4)+5)を計算します。
Ruby では inject に相当する。
3. foldl と foldr の定義を見ながら理解する
動作を理解するために、foldl とfoldr の定義を見ながら、具体的な計算を、定義で置き換えてみる。
foldl の計算を、定義で置き換える
まずは、foldl から。定義は、Haskell Code by HsColour より、
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f z xs = lgo z xs
where
lgo z [] = z
lgo z (x:xs) = lgo (f z x) xs
これを見ながら、
foldl (-) 100 [1,2,3]
の計算の過程を追ってみる。
lgo 100 [1,2,3] lgo ((-) 100 1) [2,3] lgo ((-) ((-) 100 1) 2) [3] lgo ((-) ((-) ((-) 100 1) 2) 3) [] -- ここで lgo z [] = z にマッチ ((-) ((-) ((-) 100 1) 2) 3) ((-) ((-) 99 2) 3) ((-) 97 3) 94
foldr の計算を、定義で置き換える
次に foldr。定義は、Haskell Code by HsColour より、
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr k z xs = go xs
where
go [] = z
go (y:ys) = y `k` go ys
同じように
foldr (-) 100 [1,2,3]
の計算を定義で置き換える。
go [1,2,3] 1 - go [2,3] 1 - (2 - go [3]) 1 - (2 - (3 - go [])) 1 - (2 - (3 - 100)) 1 - (2 - (-97)) 1 - 99 -98
よし！これで動作を覚えた。
4. 他の言語との比較
最後に、他の言語で、Haskell の map, filter, foldl に相当する関数、メソッドを整理しておく。
- Haskell : map, filter, foldl
- Python : map, filter, reduce
- Ruby : map, select, inject
試してみる
Ruby では、inject。
irb(main):001:0> [1,2,3].inject(100){|x,y| x - y}
=> 94
Python では、reduce。
>>> reduce(lambda x,y: x - y, [1,2,3], 100) 94
