suztomoの日記

To be a good software engineer

foldrとfoldl

myfoldr :: (a -> b -> b) -> b -> [a] -> b
myfoldr f b alst = case alst of
                   a : rst -> f a (foldr f b rst)
                   _       -> b

myfoldl :: (a -> b -> a) -> a -> [b] -> a
myfoldl f a blst = case blst of
                     b : rst  -> myfoldl f (f a b) rst
                     _        -> a

myreverse :: [a] -> [a]
--myreverse lst = foldr (\x l -> l ++ [x]) [] lst
myreverse = myfoldl (\l e -> e:l ) []

How to remember foldr and foldl

Until today, I cannot remember which is which: foldr and foldl. I came up with an idea to remember the two functions.

Suppose you have a and b in your hands and foldl is "a -> b -> a" and foldr is "a -> b -> b". *1 The type of the second parameter of foldr and foldl is the same as the return value of the first parameter. The third list parameter has the other type. Return value of foldl and foldr is the same as the return value of the first lambda.
Once we get type signature, the implementation naturally follows the idea.

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f b [a1, a2, a3]

f a1 (foldr f b [a2, a3])
f a1 (f a2 (foldr f b [a3]))
f a1 (f a2 (f a3 (foldr f b [])))
f a1 (f a2 (f a3 b))

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f a [b1, b2, b3]

foldl f (f a b1) [b2, b3]
foldl f (f (f a b1) b2) [b3]
foldl f (f (f (f a b1) b2) b3) []
Remove all ads