すごいH本 part20

畳み込み

リストに対する関数を扱う際、

基底部は空リストとし、パターンを使ってリストを先頭要 素と残りのリストに分解する

というパターンが頻繁に出てくるので、Haskell には 畳み込み(fold) と呼ばれる便利な関数があるらしい。

畳み込みを使うと、データ構造を単一の値にまとめることができる。

畳み込み関数は、

• 2引数関数(2つの引数を取る関数。+ や divなど)
• 畳み込みに用いる値(アキュムレータ)
• 畳み込むリスト

を受け取る。

foldl で畳み込み

リストの左から畳み込む関数

sum を再帰使わずに実装

sum' :: (Num a) => [a] -> a
sum' xs = foldl (\acc x -> acc + x) 0 xs

実行結果

*Main> sum' [3,2,4,1]
10

こうも書ける

sum' :: (Num a) => [a] -> a
sum' = foldl (+) 0

実行結果

*Main> sum' [3,2,4,1]
10

fold (+) 0 はリストを取る関数を返す。

カリー化のおかげで、foo a = bar b a を foo = bar b に書き換えることができる。

foldr で畳み込み

右畳み込み関数。リストを右から畳み込む。

map を実装する

map' :: (a -> b) -> [a] -> [b]
map' f xs = foldr (\x acc -> f x : acc) [] xs

実行結果

*Main> map' (+3) [1,2,3,4]
[4,5,6,7]

左畳み込みを使っても同じことができるが、リストから新しいリストを構築する際には普通は右畳み込みを使う。なぜならリストに対する:は++よりはるかに速いから。

右畳み込みと左畳み込みのもう一つの大きな違いは、右は無限リストに対しても動作するが左はダメ。

所感

リストを扱う方法が増えてきたので、ここらで復習しないとつらくなってきた。

すごいHaskellたのしく学ぼう！