问题标签 [recursion-schemes]

在 Ed Kmett 的recursion-scheme包中，有三个声明：

这三种数据类型有什么区别？

我正在阅读 Jeremy Gibbons 的关于折纸编程的文章，我被困在练习 3.7 上，它要求读者证明列表展开的融合定律：

如果

函数unfoldL展开列表，定义如下：

这是我目前的证明尝试：

我不确定如何证明标有 的步骤???。我可能应该在函数应用程序上使用某种归纳b？相关问题：有哪些很好的资源可以解释和激发各种归纳技术，例如结构归纳？

我希望能够使用定点数据类型和递归方案来制定hindley-milner 类型推理算法。忽略除实际递归部分之外的所有细节：

env该算法在递归遍历树直到到达叶子时构建环境数据结构。然后它在再次构建结果时使用此信息。

如果没有这env部分，这可以很容易地用cata. 这（与env）一般可以使用递归方案来完成吗？

我正在尝试使用递归方案编写 Robinson 的统一算法。统一算法采用两种类型并吐出一个结果。类型是：

如何使用递归方案优雅地做到这一点？

使用cataI 可以将 AST 折叠为结果。我可以在CofreeAST 上存储额外的注释。如何获取 AST 并在每个步骤中返回带注释的 AST？

我们有一个 AST 定义：

以及用于类型推断的 F 代数：

我们可以使用以下方法获得运行推理的结果cata：

但是现在我希望结果是带有每个表达式的类型信息注释的原始 AST，所以现在infer' :: Fix Term -> Wrapped (Labeled Term Type)。

1. 我应该使用什么数据结构来注释树（Cofree, Product,Fix带有自定义Label）？
2. 如何在不修改原始w函数的情况下使用递归方案实现这一点？

我不明白如何用时态创建一些例子。我知道 hylomorphism ( cata, ana) 也知道histoand futu。

但是我没有意识到时态的一些例子（可能是 Tardis monad 中的一些行为）。

还有相关链接https://github.com/ekmett/recursion-schemes/issues/42

这与专门用于列表的 Histomorphisms、Zygomorphisms 和 Futumorphisms 无关，因为没有一些关于时态的例子。

我一直在看recursion-schemes图书馆，我很困惑prepro应该用于什么，甚至它的作用。将其描述为“Fokkinga 的预变形”的信息量不是很大，并且签名 ( prepro :: Corecursive t => (forall b . Base t b -> Base t b) -> (Base t a -> a) -> t -> a) 看起来与 (catamorphism) 非常相似，cata但有一个额外的论点，其意图尚不清楚。有人能解释一下这个功能是做什么的吗？

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

它编译并且一个简短的测试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指定类型签名？

根据 Bartosz Milewski 的文章（一、二），我定义了一个F-Algebra：

（这并不是说我的代码是 Bartosz 思想的准确体现，这只是我对它们的有限理解，任何错误都是我一个人的问题。）

我现在几乎可以做任何我想做的事情，例如，对叶子求和：

这是我专门为这个问题编造的一个人为的例子，但我实际上尝试了一些不那么琐碎的事情（例如评估和简化具有任意数量变量的多项式），它就像一个魅力。One may indeed fold and replace any parts of a structure as one runs a catamorphism through, with a suitably chosen algebra . 所以，我很确定 F-Algebra 包含了 Foldable，它甚至似乎也包含了 Traversable。

现在，我可以根据 F 代数定义可折叠/可遍历实例吗？

在我看来，我不能。

• 我只能在初始 algebra上运行 catamorphism ，这是一个空类型构造函数。而且我给它的代数有一个类型，a b -> b而不是a -> b，也就是说，“in”和“out”类型之间存在函数依赖关系。
• 我Algebra a => Foldable a在类型签名中看不到任何地方。如果不这样做，那一定是不可能的。

在我看来，我不能Foldable用 F 代数来定义，因为一个Expr必须是 aFunctor在两个变量中：一个是载体，另一个是值，然后是Foldable第二个。因此，双函子可能更合适。我们也可以构造一个带有双函子的 F-代数：

它像这样运行：

但我仍然无法定义可折叠。它会有这样的类型：

不幸的是，没有得到关于类型的 lambda 抽象，也没有办法同时将隐含的类型变量放在两个地方。

我不知道该怎么办。