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) []