[Haskell-cafe] When is a composition of catamorphisms a catamorphism?

[wren ng thornton]

On 8/24/12 3:44 AM, Sebastien Zany wrote:
> More specifically (assuming I understood the statement correctly):
>
> Suppose I have two base functors F1 and F2 and folds for each: fold1 :: (F1
> a -> a) -> (μF1 -> a) and fold2 :: (F2 a -> a) -> (μF2 -> a).
>
> Now suppose I have two algebras f :: F1 μF2 -> μF2 and g :: F2 A -> A.
>
> When is the composition (fold2 g) . (fold1 f) :: μF1 -> A a catamorphism?

 From <http://comonad.com/haskell/catamorphisms.html> we have the law:

     Given
         F, a functor
         G, a functor
         e, a natural transformation from F to G
             (i.e., e :: forall a. F a -> G a)
         g, a G-algebra
             (i.e., f :: G X -> X, for some fixed X)

     it follows that

         cata g . cata (In . e) = cata (g . e)

The proof of which is easy. So it's sufficient to be a catamorphism if 
your f = In . e for some e. I don't recall off-hand whether that's 
necessary, though it seems likely

-- 
Live well,
~wren