This is a definition of foldr and foldl in terms of foldr:
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f a bs =
foldr (b g x -> g (f x b)) id bs a
foldr evaluates right to left and foldl evaluates left to right
In the case of multiplying integers, foldr would do operations in the following order
(1*(2*(3*(4*5))))
Whereas foldl would do
((((1*2)*3)*4)*5)
I’m wondering if/how this could be done more abstractly for recursion schemes over all algebraic datatypes?
Specifically, if I’ve defined catamorphism, anamorphism, paramorphism and apomorphism as follows:
deriving instance (Eq (f (Fix f))) => Eq (Fix f)
deriving instance (Ord (f (Fix f))) => Ord (Fix f)
deriving instance (Show (f (Fix f))) => Show (Fix f)
out :: Fix f -> f (Fix f)
out (In f) = f
-- Catamorphism
type Algebra f a = f a -> a
cata :: (Functor f) => Algebra f a -> Fix f -> a
cata f = f . fmap (cata f) . out
-- Anamorphism
type Coalgebra f a = a -> f a
ana :: (Functor f) => Coalgebra f a -> a -> Fix f
ana f = In . fmap (ana f) . f
-- Paramorphism
type RAlgebra f a = f (Fix f, a) -> a
para :: (Functor f) => RAlgebra f a -> Fix f -> a
para rAlg = rAlg . fmap fanout . out
where fanout t = (t, para rAlg t)
-- Apomorphism
type RCoalgebra f a = a -> f (Either (Fix f) a)
apo :: Functor f => RCoalgebra f a -> a -> Fix f
apo rCoalg = In . fmap fanin . rCoalg
where fanin = either id (apo rCoalg)
How could I write catamorphismLeft, anamorphismLeft, paramorphismLeft and apomorphismLeft?