foldを使ってfoldを作る

foldr/foldl を使って、foldl/foldrを作ってみる。

myFoldL :: (a -> b -> a) -> a -> [b] -> a
myFoldL f y xs = foldr (\x g a -> g $ f a x) id xs y

myFoldR :: (a -> b -> b) -> b -> [a] -> b
myFoldR f y xs = foldl (\g x a -> g $ f x a) id xs y

-- 間違い : 適用が右から
myFoldLb :: (a -> b -> a) -> a -> [b] -> a
myFoldLb f y xs = foldr (\x g a -> f (g a) x) id xs y
-- 間違い : 適用が左から
myFoldRb :: (a -> b -> b) -> b -> [a] -> b
myFoldRb f y xs = foldl (\g x a -> f x $ g a) id xs y

> foldl (flip (:)) [0] [1..3]
[3,2,1,0]
> myFoldL (flip (:)) [0] [1..3]
[3,2,1,0]
> myFoldLb (flip (:)) [0] [1..3]
[1,2,3,0]
> foldr (:) [0] [1..3]
[1,2,3,0]
> myFoldR (:) [0] [1..3]
[1,2,3,0]
> myFoldRb (:) [0] [1..3]
[3,2,1,0]

第2要素の時の展開 (x = 2, g = (3:)/(1:), a = [0]) まで辿ってようやく分かった・・・