Can I write `foldr` (or `foldMap`) in terms of 'recursion schemes' `cata`?

Question

I recently read about recursion schemes where catamorphisms are described as analogous to generalized foldr.

Is is possible to write an instance of Foldable (via either foldr or foldMap) in terms of cata in all cases?

Answer 1

You often can, but not universally. All it takes is a single counter-example. Several exist, but consider the simplest one that comes to (my) mind.

While completely unnecessary, you can define Boolean values with an F-algebra:

data BoolF a = TrueF | FalseF deriving (Show, Eq, Read) 

instance Functor BoolF where      
  fmap _  TrueF =  TrueF
  fmap _ FalseF = FalseF

From this (as the linked article explains) you can derive the catamorphism:

boolF :: a -> a -> Fix BoolF -> a
boolF x y = cata alg
  where alg TrueF = x
        alg FalseF = y

The type Fix BoolF is isomorphic to Bool, which isn't parametrically polymorphic (i.e. it doesn't have a type parameter), yet a catamorphism exists.

The Foldable type class, on the other hand, is defined for a parametrically polymorphic container t, e.g.

foldr :: (a -> b -> b) -> b -> t a -> b

Since Bool isn't parametrically polymorphic, it can't be Foldable, yet a catamorphism exists. The same is true for Peano numbers.

---

For parametrically polymorphic types, on the other hand, you often (perhaps always?) can. Here's a Foldable instance for a tree defined with its catamorphism:

instance Foldable TreeFix where
  foldMap f = treeF (\x xs -> f x <> fold xs)

Here's one for Maybe:

instance Foldable MaybeFix where
  foldMap = maybeF mempty

and one for linked lists:

instance Foldable ListFix where
  foldr = listF