第7章 高階関数 #2

リスト処理

標準ライブラリPreludeに含まれるリスト処理高階関数。

• map :: (a -> b) -> [a] -> [b]
• filter :: (a -> Bool) -> [a] -> [a]
• all :: (a -> Bool) -> [a] -> Bool
• any :: (a -> Bool) -> [a] -> Bool
• takeWhile :: (a -> Bool) -> [a] -> [a]
• dropWhile :: (a -> Bool) -> [a] -> [a]

LINQだとmapがSelectでfilterがWhereだけど、後は同名のメソッドがある。

畳込関数 foldr

来ましたfoldr。定義を写経してみる。

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v [] = v
foldr f v (x : xs) = f x (foldr f v xs)

再帰定義を見ると簡潔だし、無限リストに適用できそうなのも理解できる。ただし

• 関数fを適用する際に、第2引数が遅延評価される（正格評価されない）
• 関数fが値を返す際に、第2引数を評価しないか、または評価を遅延できる

の両方が必要になる（でないと結局foldrは終わらない）。

では、foldrを使って定義したライブラリ関数を写経しよう。

sum     = foldr (+) 0
product = foldr (*) 1
or      = foldr (||) False
and     = foldr (&&) True
length  = foldr (\_ n -> 1 + n) 0
reverse = foldr (\x xs -> xs ++ [x]) []
(++) xs ys  = foldr (:) ys xs

畳込関数 foldl

こっちはLINQにあるけれども、やはり定義を写経。

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v [] = v
foldl f v (x : xs) = foldl f (f v x) xs

ふーむ。定義だけ見ると分かったような分からんような。ただ、無限リストに適用すると、fがどんな性質を持っていようが再帰が終わらないことはわかる。

foldrとfoldlの型を並べてみる。（型変数を揃えておく）

foldr :: (a -> b -> b) -> b -> [a] -> b
foldl :: (b -> a -> b) -> b -> [a] -> b

というわけで、第1引数の関数が右結合か左結合かというのがなんとなく分かった気がする。

上と同じライブラリ関数をfoldlで定義すると。

sum     = foldl (+) 0
product = foldl (*) 1
or      = foldl (||) False
and     = foldl (&&) True
length  = foldl (\n _ -> n + 1) 0
reverse = foldl (\xs x -> x : xs) []
-- 教科書の (++) の定義は意味不明。(xs++)を++で定義している。
-- foldlだけでは定義できなくて、foldrが必要ってこと？

続きはまた明日以降。