このブログ記事では、関数型プログラミング（Haskellを含む）において重要な概念である畳み込み関数の概念を紹介しています。
Folding
多くのHaskellのプログラマーたちは、この関数を言語全体で最も重要な関数の1つというかもしれません -
その関数とはずばりfoldingです。以下は、foldr（右畳み込み）の型です：
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr (+) 0 [1,2,...,n]
--- => 1+2+...+n+0上記のようにして、リストのすべての要素を含む操作を行うことができます。
以下は、foldrを使用して書かれたいくつかの関数です：
sum = foldr (+) 0
and = foldr (&&) True
or = foldr (||) False上記の関数はすべて、+、&&、および||などの事前定義された演算を使用しています。
ただし、foldrに任意の関数を適用することもできます：
foldr (\elem acc -> <term>) <start_acc> <list>
--- <elem>: リスト内の要素
--- acc: アキュムレータ
--- <term>: elemと/またはaccを使用した式
--- <start_acc>: アキュムレータの初期値
--- <list>: リスト
count e = foldr (\x acc -> if e == x then acc+1 else acc) 0
--- eとxが等しいとき、0から開始してアキュムレータに1を加算し、
--- リスト内のeに等しい要素の数をカウントします。このテクニックを使用して、以前にカバーした関数を構築することができます：
length = foldr (\x -> (+) 1) 0
--- 各要素に対してアキュムレータに1を加算します
length = foldr (const $ (+) 1) 0
--- <term>としてxを使用しない場合、constを使用できます
map = foldr ((:) . f) []
--- 関数fを適用し、リストに前置しますFoldr vs Foldl
foldrに加えて、foldl(左畳み込み)もあります：
foldl (\acc elem -> <term>) <start_acc> <list>違いは何でしょうか？それは想像以上に直感的です。sumの例でfoldrとfoldlを視覚化してみましょう：
--- foldr
sum [1,2,3] = foldr (+) 0 [1,2,3]
--- 1+(2+(3+0))
--- foldl
sum [1,2,3] = foldl (+) 0 [1,2,3]
--- ((1+0)+2)+3上記から分かるように、foldrはリストの右側から要素とアキュムレータで操作を開始し、
foldlは左側から開始します。もしもあなたが命令型のプログラマーであれば、
以下の例が違いを理解するのに役立つかもしれません：
def sum_foldr(nums):
acc = 0
for i in range(len(nums)-1, -1, -1):
acc += nums[i]
return acc
def sum_foldl(nums):
acc = 0
for i in range(len(nums)):
acc += nums[i]
return accsumの場合、foldrとfoldlの両方を使用できますが、多くの場合、そのうちの1つだけが機能します。
重要事項: Foldingを使用する際には、import Prelude hiding (foldr, foldl)を使用して手動で関数の型を定義し、エラーを回避してください。
クイズ
この記事では、学習した内容を確認するためのクイズを設けます。記事のメイン部分を読んだ後に、ぜひ自分で問題を解いてみることを強くお勧めします。各問題をクリックすると答えが表示されます。
リソース
- Philipp, Hagenlocher. 2020. Haskell for Imperative Programmers #9 - Folding (foldr, foldl). YouTube.
- Philipp, Hagenlocher. 2020. Haskell for Imperative Programmers #11 - Folding Exercises. YouTube.