haskell - 我可以用 `foldr` `foldMap` 来写 'recursion schemes' (或 `cata` )吗？

Question

我最近read about recursion schemes其中变质被描述为类似于广义foldr .

是否可以编写 Foldable 的实例(通过 foldr 或 foldMap )根据 cata在所有情况下？

Answer 1

foldMap ，是 Foldable 的基本操作, 比 foldr 更适合实现.答案是肯定的。 cata只处理递归；它不会告诉您在哪里“找到”结构中的所有值。 (同样，使用 foldMap @[] 实现 foldr 仍然需要了解 [] 的内部细节。)这样做需要 a little help :

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