Haskell の畳み込み関数 - foldl, foldr

1. リストを畳み込む foldl と foldr

Haskell のサンプルコードを見ていると、よく見かける foldl と foldr 。名前からして両者は対照的な関数のようだ。

Prelude の List Operation の分類において、

• Reducing lists (folds)

として、わざわざ分類されているところを見ると、重要な関数なのだろう。 (@_@)

そういえば、Reduce と言えば、Python の関数 reduce を思い出した。

• Python のリスト内包表記

これと似たものなのかな？

 

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