我可以用“递归方案”中的“cata”函数来编写 `foldr` （或 `foldMap`）吗？

Question

我可以用“递归方案”中的“cata”函数来编写 `foldr` （或 `foldMap`）吗？

haskellfoldrecursion-schemesfoldablecatamorphism

7

我最近阅读了有关递归方案的内容，其中将折叠函数描述为类似于广义的foldr。

在所有情况下，是否可以通过cata编写Foldable实例（通过foldr或foldMap）？

- Michael Thomas

你能让问题更加精确吗？特别是，下面的任何答案是否符合您预期的问题？ - chi

我添加了“在所有情况下”以澄清；Mark的答案正是我所寻找的。如果您有更精确的措辞，我很乐意再次进行编辑。 - Michael Thomas

2个回答

3

你通常可以，但不是普遍的。只需要一个反例即可。有几个反例，但考虑最简单的一个。

虽然完全没有必要，你可以用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，但是却存在一个范畴论折叠。对于 Peano 数字也是如此。

对于参数多态类型，另一方面，您通常（也许总是？）可以这样做。这是一个Foldable实例，适用于使用其消解构造函数所定义的树：defined with its catamorphism。

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

- Mark Seemann

1

我认为问题是关于一个允许 cata 的 参数化 类型是否也允许 foldMap。在我看来，这并不构成反例。（尽管问题可能应该更明确地说明目标。） - chi

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- HTNW · Accepted Answer

foldMap, 作为 Foldable 的基本操作，比 foldr 更适合实现。答案是有条件的肯定。而 cata 只处理递归；它并不告诉你在结构中“找到”所有值的位置。（同样，使用 foldr 实现 foldMap @[] 仍需要知道 [] 的内部细节。）要做到这一点，需要一些帮助：

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

虽然你也可以只在Tree上使用deriving Foldable来实现相同的效果。但为了最大化通用性，你可能需要像这样做（我说“可能”是因为...）

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