Могу ли я написать «foldr» (или «foldMap») в терминах «схем рекурсии» «cata»?

Вы часто можете, но не всегда. Достаточно одного контрпримера. Существует несколько, но рассмотрим самый простой, который приходит (мне) на ум.

Хотя это совершенно необязательно, вы можете определить логические значения с помощью F-алгебры :

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

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

Из этого (как объясняется в связанной статье) вы можете получить катаморфизм:

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

Тип Fix BoolF изоморфен типу Bool, который не является параметрически полиморфным (т. е. не имеет параметра типа), однако существует катаморфизм.

Класс типа Foldable, с другой стороны, определен для параметрически полиморфного контейнера t, например.

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

Поскольку Bool не является параметрически полиморфным, оно не может быть Foldable, но катаморфизм существует. То же верно и для чисел Пеано.

С другой стороны, для параметрически полиморфных типов вы часто (возможно, всегда?) можете. Вот Foldable экземпляр дерева, определенного с его катаморфизмом:

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

Вот один для Maybe:

instance Foldable MaybeFix where
  foldMap = maybeF mempty

и для связанных списков:

instance Foldable ListFix where
  foldr = listF

foldMap, будучи основной операцией Foldable, является лучшим кандидатом для реализации, чем foldr. Ответ квалифицированный да. cata обрабатывает только рекурсию; он не говорит вам, где «найти» все значения в структуре. (Точно так же реализация foldMap @[] с foldr требует знания внутренних деталей [].) Для этого требуется небольшая помощь:

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

Затем вы можете определить

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

Это позволяет вам делать такие вещи, как

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

(Хотя вы могли бы просто сказать deriving Foldable на Tree.) Для максимальной универсальности вы можете захотеть что-то более похожее на это (я говорю «хочу»...)

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

Теперь вы можете говорить такие вещи, как

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

Но теперь ваши функторы Base могут быть более нерегулярными:

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