What are the rules to compose f-algebras in a catamorphism

Question

Here are some simple F-algebras for lists. They work with the cata function from the recursion-schemes library.

import Data.Functor.Foldable

algFilterSmall :: ListF Int [Int] -> [Int]
algFilterSmall Nil = [] 
algFilterSmall (Cons x xs) = if x >= 10 then (x:xs) else xs

algFilterBig :: ListF Int [Int] -> [Int]
algFilterBig Nil = [] 
algFilterBig (Cons x xs) = if x < 100 then (x:xs) else xs

algDouble :: ListF Int [Int] -> [Int]
algDouble Nil = [] 
algDouble (Cons x xs) = 2*x : xs

algTripple :: ListF Int [Int] -> [Int]
algTripple Nil = [] 
algTripple (Cons x xs) = 3*x : xs

Now I compose them:

doubleAndTripple :: [Int] -> [Int]
doubleAndTripple = cata $ algTripple . project . algDouble
-- >>> doubleAndTripple [200,300,20,30,2,3]
-- [1200,1800,120,180,12,18]

doubleAndTriple works as expected. Both algebras are structure preserving, they don't change the length of the list, so cata can apply both algebras to every item of the list.

Next one is filter and double:

filterAndDouble :: [Int] -> [Int] 
filterAndDouble = cata $ algDouble . project . algFilterBig
-- >>> filterAndDouble [200,300,20,30,2,3]
-- [160,60,4,6]

It doesn't work properly. I assume it's because algFilterBig is not structure preserving.

Now the last example:

filterBoth :: [Int] -> [Int] 
filterBoth = cata $ algFilterSmall . project . algFilterBig 
-- >>> filterBoth [200,300,20,30,2,3]
-- [20,30]

Here both algebras are not structure preserving, but this example is working.

What are the exact rules for composing f-algebras?

Answer 1

"Structure preserving algebras" can be formalized as natural transformations (that can be between different functors).

inList :: ListF a [a] -> [a]
inList Nil = []
inList (Cons a as) = a : as

ntDouble, ntTriple :: forall a. ListF Int a -> ListF Int a
algDouble = inList . ntDouble
algTriple = inList . ntTriple

Then, for any algebra f and natural transformation n,

cata (f . inList . n) = cata f . cata n

The doubleAndTriple example is an instance of that for f = algTriple and n = ntDouble.

This doesn't easily generalize to larger classes of algebras.

I think the case of filter is easier to see without categories, as a consequence of the fact that filter is a semigroup homomorphism: filter p . filter q = filter (liftA2 (&&) p q).

---

I searched for a general but sufficient condition for a "distributive law" on filter-like algebras. Abbreviate a bit afs = algFilterSmall, afb = algFilterBig. We reason backwards, to find a sufficient condition for:

cata (afs . project . afb) = cata afs . cata afb  -- Equation (0)

By definition of a catamorphism, z = cata (afs . project . afb) is the unique solution to this equation (a disguised commutative diagram):

z . inList = afs . project . afb . fmap z

Substitute z with the RHS of the previous equation:

cata afs . cata afb . inList = afs . project . afb . fmap (cata afs . cata afb)
-- (1), equivalent to (0)

• On the LHS, we apply the definition of cata as a Haskell function, cata afb = afb . fmap (cata afb) . project, and simplify with project . inList = id;

• on the RHS, we apply a functor law fmap (f . g) = fmap f . fmap g.

This yields:

cata afs . afb . fmap (cata afb) = afs . project . afb . fmap (cata afs) . fmap (cata afb)
-- (2), equivalent to (1)

We "cosimplify" away the last factor fmap (cata afb) (remember that we are reasoning backwards):

cata afs . afb = afs . project . afb . fmap (cata afs)  -- (3), implies (2)

This is the simplest one I could come up with.