When is a composition of catamorphisms a catamorphism?

Question

From page 3 of http://research.microsoft.com/en-us/um/people/emeijer/Papers/meijer94more.pdf:

it is not true in general that catamorphisms are closed under composition

Under what conditions do catamorphisms compose to a catamorphism? More specifically (assuming I understood the statement correctly):

Suppose I have two base functors F and G and folds for each: foldF :: (F a -> a) -> (μF -> a) and foldG :: (G a -> a) -> (μG -> a).

Now suppose I have two algebras a :: F μG -> μG and b :: G X -> X.

When is the composition (foldG b) . (foldF a) :: μF -> X a catamorphism?

---

Edit: I have a guess, based on dblhelix's expanded answer: that outG . a :: F μG -> G μG must be the component at μG of some natural transformation η :: F a -> G a. I don't know whether this is right. (Edit 2: As colah points out, this is sufficient but not necessary.)

Edit 3: Wren Thornton on Haskell-Cafe adds: "If you have the right kind of distributivity property (as colah suggests) then things will work out for the particular case. But, having the right kind of distributivity property typically amounts to being a natural transformation in some appropriately related category; so that just defers the question to whether an appropriately related category always exists, and whether we can formalize what "appropriately related" means."

Answer 1

When is the composition (fold2 g) . (fold1 f) :: μF1 -> A a catamorphism?

When there exists an F1-algebra h :: F1 A -> A such that fold1 h = fold2 g . fold1 f.

To see that catamorphisms are in general not closed under composition, consider the following generic definitions of type-level fixed point, algebra, and catamorphism:

newtype Fix f = In {out :: f (Fix f)}

type Algebra f a = f a -> a

cata :: Functor f => Algebra f a -> Fix f -> a
cata phi = phi . fmap (cata phi) . out

For catamorphisms to compose we would need

algcomp ::  Algebra f (Fix g) -> Algebra g a -> Algebra f a

Now try writing this function. It takes two functions as arguments (of types f (Fix g) -> Fix g and g a -> a respectively) and a value of type f a, and it needs to produce a value of type a. How would you do that? To produce a value of type a your only hope is to apply the function of type g a -> a, but then we are stuck: we have no means to turn a value of type f a into a value of type g a, have we?

I am not sure whether this is of any use for your purposes, but an example of a condition under which one can compose to catamorphisms is if we have a morphism from the result of the second cata to the fixed point of the second functor:

algcomp' :: (Functor f, Functor g) =>
            (a -> Fix g) -> Algebra f (Fix g) -> Algebra g a -> Algebra f a
algcomp' h phi phi' = cata phi' . phi . fmap h