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

Catamorphisms de-construct a data structure into a result value. So, in general, when you apply a catamorphism, the result is something completely different, and you cannot apply another catamorphism to it.

For example, a function that sums all elements of [Int] is a catamorphism, but the result is Int. There is no way how to apply another catamorphism on it.

However, some special catamorphisms create a result of the same type as the input. One such example is map f (for some given function f). While it de-constructs the original structure, it also creates a new list as its result. (Actually, map f can be viewed both as a catamorphism and as an anamorphism.) So if you have such a class of special catamorphisms, you can compose them.

Answer 2

If we consider semantic equivalence, the composition of two catamorphisms is a catamorphism, when the first one is a hylomorphism:

cata1 . hylo1 = cata2

For example (Haskell):

sum . map (^2) = foldl' (\x y -> x + y^2) 0

Answer 3

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

Answer 4

(Disclaimer: This is outside my area of expertise. I believe I'm correct (with caveats provided at different points), but ... Verify it yourself.)

A catamorphism can be thought of as a function that replaces constructors of a data type with other functions.

(In this example, I will be using the following data types:

data [a] = [] | a : [a]

data BinTree a = Leaf a | Branch (BinTree a) (BinTree a)

data Nat = Zero | Succ Nat

)

For example:

length :: [a] -> Nat
length = catamorphism
     []   -> 0
     (_:) -> (1+)

(Sadly, the catamorphism {..} syntax is not available in Haskell (I saw something similar in Pola). I've been meaning to write a quasiquoter for it.)

So, what is length [1,2,3]?

length [1,2,3]
length (1 : 2 : 3 : [])
length (1:  2:  3:  [])
        1+ (1+ (1+ (0 )))
        3

That said, for reasons that will become apparent later, it is nicer to define it as the trivially equivalent:

length :: [a] -> Nat
length = catamorphism
     []   -> Zero
     (_:) -> Succ

Let's consider a few more example catamorphisms:

map :: (a -> b) -> [a] -> b
map f = catamorphism
     []   -> []
     (a:) -> (f a :)

binTreeDepth :: Tree a -> Nat
binTreeDepth = catamorphism
     Leaf _ -> 0
     Branch -> \a b -> 1 + max a b

binTreeRightDepth :: Tree a -> Nat
binTreeRightDepth = catamorphism
     Leaf _ -> 0
     Branch -> \a b -> 1 + b

binTreeLeaves :: Tree a -> Nat
binTreeLeaves = catamorphism
     Leaf _ ->  1
     Branch -> (+)

double :: Nat -> Nat
double = catamorphism
     Succ -> Succ . Succ
     Zero -> Zero

Many of these can be nicely composed to form new catamorphisms. For example:

double . length . map f = catamorphism
     []   -> Zero
     (a:) -> Succ . Succ

double . binTreeRightDepth = catamorphism
     Leaf a -> Zero
     Branch -> \a b -> Succ (Succ b)

double . binTreeDepth also works, but it is almost a miracle, in a certain sense.

double . binTreeDepth = catamorphism
     Leaf a -> Zero
     Branch -> \a b -> Succ (Succ (max a b))

This only works because double distributes over max... Which is pure coincidence. (The same is true with double . binTreeLeaves.) If we replaced max with something that didn't play as nicely with doubling... Well, let's define ourselves a new friend (that doesn't get along as well with the others). For a binary operators that double doesn't distribute over, we'll use (*).

binTreeProdSize :: Tree a -> Nat
binTreeProdSize = catamorphism
     Leaf _ -> 0
     Branch -> \a b -> 1 + a*b

Let's try to establish sufficient conditions for two catamorphisms two compose. Clearly, any catamorphism will quite happily be composed with length, double and map f because they yield their data structure without looking at the child results. For example, in the case of length, you can just replace Succ and Zero with what ever you want and you have your new catamorphism.

1. If the first catamorphism yields a data structure without looking at what happens to its children, two catamorphisms will compose into a catamorphism.

Beyond this, things become more complicated. Let's differentiate between normal constructor arguments and "recursive arguments" (which we will mark with a % sign). So Leaf a has no recursive arguments, but Branch %a %b does. Let's use the term "recursive-fixity" of a constructor to refer to the number of recursive arguments it has. (I've made up both these terms! I have no idea what proper terminology is, if there is one! Be wary of using them elsewhere!)

If the first catamorphism maps something into a zero recursive fixity constructor, everything is good!

               a               |            b            |     cata(b.a)
===============================|=========================|================
       F a %b %c .. -> Z       |      Z -> G a b ..      |      True

If we map children directly into a new constructor, we're also good.

               a               |            b            |     cata(b.a)
===============================|=========================|=================
   F a %b %c .. -> H %c %d ..  |   H %a %b -> G a b ..   |       True

If we map into a recursive fixity one constructor...

               a               |            b            |     cata(b.a)
===============================|=========================|=================
 F a %b %c .. -> A (f %b %c..) |     A %a -> B (g %a)    |    Implied by g
                               |                         | distributes over f

But it isn't iff. For example, if there exist g1 g2 such that g (f a b..) = f (g1 a) (g2 b) .., that also works.

From here, the rules will just get messier, I expect.