Haskell勉強記（7）

foldlは、foldrで書けるらしい。

"universal property of fold"とよばれる特性を使うと変換できるらしい。読んだけど、良く分からなかった。

とりあえず、今日やったことを書きます。まずはfoldに慣れるところからはじめました。。

1) foldを自分で定義する。

foldl' f v []     = v
foldl' f v (x:xs) = foldl' f (f v x) xs

foldr' f v []     = v
foldr' f v (x:xs) = f x (foldr' f v xs)


main = do print $ foldl' (+) 0 [1..10]
       print $ foldl' (++) [] ["h", "o", "g", "e"]
       print $ foldr' (:) [] ['a', 'g', 'e', 'p', 'o', 'y', 'o']
       print $ foldr' (\_ n -> 1+n) 0 [1..10]

2) ラムダ式とfoldを使って標準関数を書く。

length' = foldr (\_ n -> 1+n) 0
reverse' = foldl (\xs x -> x:xs) []
map' f = foldr (\x xs -> f x : xs) []
filter' f = foldr (\x xs -> if f x then x : xs else xs) []

main = do print $ length' [1..5]
       print $ reverse' "Hello"
       print $ map' (*2) [1..10]
       print $ filter (<0) [0, -1, 2, -3, 4, -5]

3) セクションとfoldを使って標準関数を書く。

sum' = foldr (+) 0
product' = foldr (*) 1
and' = foldr (&&) True
or' = foldr (||) False

main = do print $ sum' [1..10]
       print $ product' [1..10]
       print $ and' $ map even [2,4..10]
       print $ or' $ map odd [1..10]

references:

1. Writing foldl using foldr

2. A tutorial on the universality and expressiveness of fold