Haskell勉強記（7）

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

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

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

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

view plainprint?

1. foldl' f v []     = v  
2. foldl' f v (x:xs) = foldl' f (f v x) xs  
3.   
4. foldr' f v []     = v  
5. foldr' f v (x:xs) = f x (foldr' f v xs)  
6.   
7.   
8. main = do print $ foldl' (+) 0 [1..10]  
9.        print $ foldl' (++) [] ["h", "o", "g", "e"]  
10.        print $ foldr' (:) [] ['a', 'g', 'e', 'p', 'o', 'y', 'o']  
11.        print $ foldr' (\_ n -> 1+n) 0 [1..10]  

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を使って標準関数を書く。

view plainprint?

1. length' = foldr (\_ n -> 1+n) 0  
2. reverse' = foldl (\xs x -> x:xs) []  
3. map' f = foldr (\x xs -> f x : xs) []  
4. filter' f = foldr (\x xs -> if f x then x : xs else xs) []  
5.   
6. main = do print $ length' [1..5]  
7.        print $ reverse' "Hello"  
8.        print $ map' (*2) [1..10]  
9.        print $ filter (<0) [0, -1, 2, -3, 4, -5]  

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を使って標準関数を書く。

view plainprint?

1. sum' = foldr (+) 0  
2. product' = foldr (*) 1  
3. and' = foldr (&&) True  
4. or' = foldr (||) False  
5.   
6. main = do print $ sum' [1..10]  
7.        print $ product' [1..10]  
8.        print $ and' $ map even [2,4..10]  
9.        print $ or' $ map odd [1..10]  

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