foldr
foldr の定義は以下の樣になつてゐる.
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
働きを理解するために書き下してみる.
foldr f z [a,b,c] = f a (foldr z [b,c])
= f a (f b (foldr z [c]))
= f a (f b (f c (foldr z [])))
= f a (f b (f c z))
f が && または || の場合遅延評價のために最初の && a (または || a)の評價で計算が終はる.
foldrでsumを定義する
sumr xs = foldr (+) 0 xs
sumr [1,2,3] = foldr (+) 0 [1,2,3]
= (+ 1 (foldr (+) 0 [2,3]))
= (+ 1 (+ 2 (foldk (+) 0 [3])))
= (+ 1 (+ 2 (+ 3 (foldr (+) 0 []))))
= (+ 1 (+ 2 (+ 3 0)))
= (+ 1 (+ 2 3))
= (+ 1 5)
= 6
foldrでmapを定義する
遅延評價が効く.
map f xs = foldr (\x a -> f x : a) [] [xs]
map f [1,2,3] = foldr (\x a -> f x : a) [] [1,2,3]
= f 1 : (foldr (\x a -> f x : a) [] [2,3])
= f 1 : (f 2 : (foldr (\x a -> f x : a) [] [3]))
= f 1 : (f 2 : (f 3 : (foldr (\x a -> f x : a) [] [])))
= f 1 : (f 2 : (f 3 : []))
= f 1 : f 2 : f 3 : []
foldl
foldl の定義は以下の樣になつてゐる.
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl _ z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
こちらも働きを理解するために書き下してみる.
foldl f z [a,b,c] = foldl f (f z a) [b,c]
= foldl f (f (f a z) b) [c]
= foldl f (f (f (f a z) b) c) []
= (f (f (f z a) b) c)
foldlでsumを定義する
suml xs = foldl (+) 0 xs
suml [1,2,3] = foldl (+) 0 [1,2,3]
= foldl (+) (+ 0 1) [2,3]
= foldl (+) (+ (+ 0 1) 2) [3]
= foldl (+) (+ (+ (+ 0 1) 2) 3) []
= (+ (+ (+ 0 1) 2) 3)
= (+ (+ 1 2) 3)
= (+ 3 3)
= 6
foldlでmapを定義する
リストの連結があるので遅い.
map f xs = folfl (\a x -> a ++ [f x]) [] xs
map f [1,2,3] = foldl (\a x -> a ++ [f x]) [] [1,2,3]
= foldl (\a x -> a ++ [f x]) (++ [] [f 1]) [2,3]
= foldl (\a x -> a ++ [f x]) (++ (++ [] [f 1]) [f 2]) [3]
= foldl (\a x -> a ++ [f x]) (++ (++ (++ [] [f 1]) [f 2]) [f 3]) []
= (++ (++ (++ [] [f 1]) [f 2]) [f 3])
= (++ (++ [f 1] [f 2]) [f 3])
= (++ [f 1, f 2] [f 3])
= [f 1, f 2, f 3]
晩御飯
- 鮟鱇鍋