问题标签 [catamorphism]

我有点不确定我正在尝试的实际名称是什么，创建折叠或变质似乎是它的名称。

我有以下折叠的数据结构：

此折叠适用于例如此“实现”：

使用此命令

1 2 3 4它会像您期望的那样打印出来。

到目前为止一切顺利，但是..

当我想在遍历数据结构时“下推”一些信息（在这种情况下为文件路径），如下所示：

我无法编译它。它返回此错误：

似乎您不能像这样返回部分单子函数，但这是为什么呢？我怎样才能让它工作？

我有这个简单的ExprAST，我可以轻松地将其转换为String.

现在我想向它添加一个额外的数据。所以我正在尝试使用Cofree

我可以转换Expr为Expr2

但我不知道如何转换Expr2为String

另外，Cofree 是解决这个注释问题的最好方法吗？

我有这个 AST

我想比较

但是所有递归方案函数似乎只适用于单一结构

显然我可以使用递归

但我希望可以使用某种 zipfold 功能。

我有这种语言 AST

我想把它转换成字符串

但是当使用 lambda 时，Apply我需要括号

但我无法将内部结构与 cata 匹配

还有比这更好的解决方案para吗？

它看起来更丑陋。即使只在一个地方需要它，我也需要在任何地方删除 fst 元组参数，我想它会更慢。

首先，这建立在https://www.schoolofhaskell.com/user/bartosz/understanding-algebras 因此如果不熟悉代数和递归方案，请阅读上下文。

假设我有一个简单的表达式解析器：

它可能会成功，也可能不会成功。例子：

我的问题是，如果有人

1) 更新parse函数以使用解析位置注释节点

2) 用解析位置前缀错误消息

我如何将下面的这些新功能与上面的功能集成在一起？

示例用法：

这会是一个zygomorphism吗？也许是组织同态？两者都需要某种类型的扭曲。

加分点：我应该使用 elgot 代数在失败时短路，看到评估可以返回Left String吗？

假设以下相互递归结构：

目标：为此结构生成常见的变态：foldl，foldr，foldk。

我产生了如下的天真变态：

如何“机械地”生成尾递归 foldl（使用累加器）和尾递归 foldr（使用延续）？

我已经阅读了Scott 的递归类型和折叠系列，并且我了解如何“机械地”为递归结构生成折叠。但是我在谷歌上找不到任何东西来为递归数据结构做“机械”的事情。

PS：可以通过内联来摆脱上面的相互递归，但让我们保留它，因为它代表了tpetricek 的 Markdown 解析器中相互递归的简化版本。

对于表示自然数的数据类型：

在 Scala 中，这是实现相应catamorphism的基本方法：

但是，由于对 cata 的递归调用不在尾部位置，因此很容易触发堆栈溢出。

有哪些替代实施选项可以避免这种情况？除非代码最终呈现的界面看起来和上面一样简单，否则我宁愿不走F 代数的路线。

编辑：看起来这可能是直接相关的：是否可以使用延续来使 foldRight 尾递归？

很久以前我正在阅读 Bart de Smet 写的文章：http: //community.bartdesmet.net/blogs/bart/archive/2009/11/08/jumping-the-trampoline-in-c-stack-friendly -recursion.aspx

在 LINQ 中根据聚合运算符定义所有其他变态运算符作为练习留给读者：
-简单：(Long)Count、Sum、Average、Min、Max
-有点困难：All、Any、Contains
-更多思考：First（OrDefault），Last（OrDefault），Single（OrDefault）

除了 Single() 扩展方法之外，我设法对几乎所有东西都使用了 Aggregate catamorphism。此外，在某些情况下，例如 Contains() 或 First()，没有正确重写，因为我真的不知道如何停止聚合变态（只要找到符合某些条件的项目）而不是遍历整个给定序列的其余部分。

总结一下：
- 如何使用 Aggregate 重写 Single() 扩展方法？
- 如何停止 LINQ 聚合变态以便在找到项目时返回项目而不继续迭代给定序列的其余部分（例如，AggregateContains() 应该为匹配值的第一个项目返回 true 并停止迭代）。

Haskell 的基础库包含几个函数，它们是它们各自数据类型的小写版本，比如bool,maybe和either. 在 Data.Bool.Extra 的源代码中，bool函数清楚地表示为数据类型的变态：

现在，使用Recursion Schemes by Example中定义的变态，似乎上述基本库函数都是其数据类型的变态，例如对于 Maybe：

然而，Data.List.Extra 的list函数只是在评论中被提及为“对列表进行非递归转换，比如‘也许’”，但由于它与其数据类型相比是非递归的，因此显然不是列表的递归方案，或者是吗？这就是为什么它没有在基础库中定义的原因吗？该函数是否还有其他很好的理论性质？

在下面的代码中，如何让 cataM 自上而下（而不是像目前的情况那样自下而上）遍历树？

我想我应该foldMap以不同的方式实现，但是如何在branch子节点之前处理节点本身，因为branch没有t不是子节点的实例？