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?
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