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

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?

Solution

• 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
``````
``````instance Foldable ListFix where
foldr = listF
``````