我可以用“递归方案” cata来写“ foldr”（或“ foldMap”）吗？

Question

我最近阅读了关于递归方案的描述，其中将同构同构描述为广义foldr。

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

Answer 1

通常可以，但并非普遍如此。所需要的只是一个反例。存在几种，但请考虑（我）想到的最简单的一种。

\n\n

虽然完全没有必要，但您可以使用 F 代数定义布尔值：

\n\n

data\xc2\xa0BoolF\xc2\xa0a\xc2\xa0=\xc2\xa0TrueF\xc2\xa0|\xc2\xa0FalseF\xc2\xa0deriving\xc2\xa0(Show,\xc2\xa0Eq,\xc2\xa0Read) \n\ninstance\xc2\xa0Functor\xc2\xa0BoolF\xc2\xa0where     \xc2\xa0\n  fmap\xc2\xa0_\xc2\xa0\xc2\xa0TrueF\xc2\xa0=\xc2\xa0\xc2\xa0TrueF\n\xc2\xa0\xc2\xa0fmap\xc2\xa0_\xc2\xa0FalseF\xc2\xa0=\xc2\xa0FalseF\n

\n\n

由此（正如链接的文章所解释的那样）您可以得出变形论：

\n\n

boolF\xc2\xa0::\xc2\xa0a\xc2\xa0->\xc2\xa0a\xc2\xa0->\xc2\xa0Fix\xc2\xa0BoolF\xc2\xa0->\xc2\xa0a\nboolF\xc2\xa0x\xc2\xa0y\xc2\xa0=\xc2\xa0cata\xc2\xa0alg\n\xc2\xa0\xc2\xa0where\xc2\xa0alg TrueF\xc2\xa0=\xc2\xa0x\n       \xc2\xa0alg\xc2\xa0FalseF\xc2\xa0=\xc2\xa0y\n

\n\n

该类型Fix BoolF与 是同构的Bool，它不是参数多态的（即它没有类型参数），但存在变形现象。

\n\n

Foldable另一方面，类型类是为参数多态容器定义的，t例如

\n\n

foldr\xc2\xa0:: (a -> b -> b) -> b -> t a -> b\n

\n\n

由于Bool不是参数多态，所以它不可能是Foldable，但变形现象仍然存在。皮亚诺数也是如此。

\n\n\n\n

另一方面，对于参数多态类型，您通常（也许总是？）可以。这是用其变形性定义的Foldable树的实例：

\n\n

instance\xc2\xa0Foldable\xc2\xa0TreeFix\xc2\xa0where\n\xc2\xa0\xc2\xa0foldMap\xc2\xa0f\xc2\xa0=\xc2\xa0treeF\xc2\xa0(\\x\xc2\xa0xs\xc2\xa0->\xc2\xa0f\xc2\xa0x\xc2\xa0<>\xc2\xa0fold\xc2\xa0xs)\n

\n\n

这是一个Maybe：

\n\n

instance\xc2\xa0Foldable\xc2\xa0MaybeFix\xc2\xa0where\n  foldMap\xc2\xa0=\xc2\xa0maybeF\xc2\xa0mempty\n

\n\n

以及一个用于链接列表的：

\n\n

instance\xc2\xa0Foldable\xc2\xa0ListFix\xc2\xa0where\n  foldr\xc2\xa0=\xc2\xa0listF\n

\n