问题标签 [catamorphism]

给出了两种数据类型 Color 和 Plant。

现在我应该实现fold_plant以下类型的功能：

我理解折叠函数的方式是它需要一个列表，并且对于每次迭代，它都会从列表中删除第一个元素并对该元素执行某些操作。

显然fold_plant Stalk Blossom Leaf是植物上的身份。

现在我知道在 Haskell 中你可以创建这样的函数：

但是从这里开始，我不知道折叠功能如何在植物中起作用。

我正在阅读关于 catamorphisms 的维基百科文章，目前我能够在 F# 中重现 Haskell 示例，除了这一部分：

这可以在 F# 中完成吗？

最近我终于开始觉得我理解变态现象了。我在最近的一个答案中写了一些关于它们的内容，但简要地说，我会说一个类型的变态抽象了递归遍历该类型的值的过程，该类型的模式匹配被具体化为该类型具有的每个构造函数的一个函数. 虽然我欢迎对这一点或上面链接的我的答案中的较长版本进行任何更正，但我认为我或多或少地对此有所了解，这不是这个问题的主题，只是一些背景。

一旦我意识到传递给 catamorphism 的函数完全对应于类型的构造函数，并且这些函数的参数同样对应于那些构造函数字段的类型，这一切突然感觉很机械，我看不出哪里有替代实现的任何回旋余地。

例如，我只是编造了这种愚蠢的类型，对它的结构“意味着”什么没有真正的概念，并为它推导出了一个变态。我没有看到任何其他方式可以定义这种类型的通用折叠：

我的问题是，是否每种类型都有独特的 catamorphism（直到参数重新排序）？或者是否有反例：不能定义变质的类型，或者存在两种不同但同样合理的变质的类型？如果没有反例（即，一个类型的变态是唯一的并且可以简单地派生），是否有可能让 GHC 为我派生某种类型类来自动完成这项繁重的工作？

以下函数使用递归方案库从列表中实现了良好的旧过滤器函数。

它编译并且一个简短的测试catafilter odd [1,2,3,4]是成功的。但是，如果我取消注释类型签名，alg我会收到以下错误：

SO question type-signature-in-a-where-clause的答案 建议使用ScopedTypeVariables扩展。对Why-is-it-so-uncommon-to-use-type-signatures-in-where-clauses的最后一个答案中的评论 建议使用forall量化。

所以我补充说：

在我的模块顶部，并为alg尝试了不同的类型签名，例如： alg :: forall a. ListF a [a] -> [a]或者 在catlist类型签名中alg :: forall b. ListF b [b] -> [b]添加一个forall 。没有编译！

问题：为什么我不能为alg指定类型签名？

我有这个 F 代数（在上一个问题中介绍过），我想在它上面加上一个有效的代数。通过绝望的试验，我设法拼凑出一个有效的一元变态。我想知道它是否可以推广到应用程序，如果不能，为什么。

这就是我定义的方式Traversable：

这是一元变态：

这就是它的工作原理：

我现在的想法是我可以这样重写：

不幸的是，value这取决于subtree并且根据一篇关于 applicative do-notation 的论文，在这种情况下，我们不能对 Applicative 脱糖。似乎没有办法解决这个问题；我们需要一个单子从嵌套的深处浮起来。

这是真的吗？我可以安全地得出结论，只有扁平结构可以折叠，仅具有应用效果吗？

我在fixana这里有这个可爱的功能，它的执行速度比她姐姐快 5 倍ana。（我有一份criterion报告支持我）

我可以cata用同样的方式表达他们的表弟吗？

在我看来，我做不到，但过去我曾多次被我的 SO 伙伴羞辱过。

所以我一直在尝试将这个检查列表是否没有任何重复的 Haskell 函数转换为 Hylomorphism，但它有些奇怪。

如果有人可以提供帮助，我会很高兴！谢谢

我有一个我正在使用注释的 AST Cofree：

我type Expr = Fix ExprF用来表示未标记的 AST，并type AnnExpr a = Cofree ExprF a表示标记的 AST。我想出了一个函数，通过丢弃所有注释将标记的 AST 转换为未标记的 AST：

这看起来可能是某种变态（我使用的是 Kmett 的recursion-schemes包中的定义）。

我认为使用 catamorphism 重写的上述内容看起来像这样，但我不知道要放置什么来alg进行类型检查。

任何帮助确定这是否真的是 cata/anamorphism，以及为什么它是/不是的一些直觉将不胜感激。

我想理解函子不动点的抽象概念，但是，我仍在努力弄清楚它的确切实现及其在 Haskell 中的变态。

例如，如果我根据“程序员的类别理论”一书 - 第 359 页定义，则以下代数

根据变质的定义，可以将以下函数应用于 ListF 的不动点，即 List，以计算其长度。

我有两个困惑。首先，Haskell 编译器如何知道 List 是ListF 的不动点？我从概念上知道它是，但是编译器怎么知道，即，如果我们定义另一个与 List 相同的 List'，我敢打赌编译器不会自动推断 List' 也是 ListF 的不动点，或者确实它？（我会很惊讶）。

其次，由于 cata lenAlg 的递归性质，它总是试图 unFix 数据构造函数的外层以暴露函数的内层（顺便说一句，我的这种解释是否正确？）。但是，如果我们已经在叶子节点，我们怎么能调用这个函数呢？

例如，有人可以帮助为以下函数调用编写执行跟踪以澄清吗？

我可能遗漏了一些明显的东西，但是我希望这个问题对于其他有类似困惑的人仍然有意义。

答案摘要

@nm 回答了我的第一个问题，指出为了让 Haskell 编译器找出 Functor A 是 Functor B 的不动点，我们需要明确。在这种情况下，它是

@luqui 和@Will Ness 指出，由于 fmap 的定义，在叶子上调用 fmap (cata lenAlg)，在这种情况下是 NilF，将返回 NilF。

我会接受@nm 的回答，因为它直接解决了我的第一个（更大的）问题，但我确实喜欢所有三个答案。非常感谢您的帮助！

我目前正在学习结构递归/变态意义上的折叠。我使用自然数的折叠来实现幂和阶乘。请注意，我几乎不知道 Haskell，所以代码可能很尴尬：

接下来我想调整斐波那契数列：

我有fib一对作为第二个参数，其字段在每次递归调用时交换。我被困在这一点上，因为我不了解转换过程的机制。

[编辑]

如评论中所述，我的fact功能是错误的。这是一个基于变形的新实现（希望如此）：