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?

Hoopen

Can you make the question more precise? In particular, does any of the answers below fit your intended question? – Queer

I added 'in all cases' to clarify; Mark's answer was what I was looking for. Happy to edit again if you have some language which is more precise? – Hoopen

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

Shrivel

I think the question was about whether a parametric type admitting cata also admits foldMap. This does not really make a counterexample, IMO. (The question could have specified the goal better, though.) – Queer

Answer 2

foldMap, being the fundamental operation of Foldable, is a better candidate for implementation than foldr. The answer is a qualified yes. cata only handles recursion; it doesn't tell you where to "find" all the values in a structure. (In the same way, implementing foldMap @[] with foldr still requires knowing the inner details of [].) Doing so requires a little help:

class Bifoldable f where
  bifoldMap :: Monoid m => (a -> m) -> (b -> m) -> f a b -> m

You can then define

foldMapDefault ::
  (Recursive (f a), Base (f a) ~ b a, Bifoldable b) =>
  Monoid m => (a -> m) -> f a -> m
foldMapDefault f = cata (bifoldMap f id)

This allows you to do things like

data Tree a = Leaf | Branch (Tree a) a (Tree a)
makeBaseFunctor ''Tree
deriveBifoldable ''TreeF
instance Foldable Tree where foldMap = foldMapDefault

(Though you may as well have just said deriving Foldable on Tree.) For maximum genericity, you may want something more like this (I say "want"...)

newtype Fixed f a = Fixed { getFixed :: f a }
newtype Bibase f a b = Bibase { getBibase :: Base (f a) b }
instance (forall a. Recursive (f a), Bifoldable (Bibase f)) =>
         Foldable (Fixed f) where
  foldMap :: forall a m. Monoid m => (a -> m) -> Fixed f a -> m
  foldMap f = cata (bifoldMap f id . Bibase @f @a @m) . getFixed

You can now say things like

data Tree a = Leaf | Branch (Tree a) a (Tree a)
makeBaseFunctor ''Tree
deriveBifoldable ''TreeF
deriving via TreeF instance Bifoldable (Bibase Tree)
deriving via (Fixed Tree) instance Foldable Tree

But now your Base functors can be more irregular:

data List a = Nil | Cons a (List a)
type instance Base (List a) = Compose Maybe ((,) a)
instance Recursive (List a) where
  project Nil = Compose Nothing
  project (Cons x xs) = Compose (Just (x, xs))
instance Bifoldable (Bibase List) where
  bifoldMap f g (Bibase (Compose Nothing)) = mempty
  bifoldMap f g (Bibase (Compose (Just (x, xs)))) = f x <> g xs
deriving via (Fixed List) instance Foldable List

Vamp

I thought the question was about whether we can do something like this to every type which supports cata. Here, AFAICS, deriveBifoldable can fail in the general case. – Queer

'I say "want"...' - hahaha, yeah this is mindbending. Very, very cool too! – Hoopen

What makes foldMap the fundamental operation of Foldable, rather than foldr? – Tertian