问题标签 [recursion-schemes]

我有一个可变参数提升函数，它允许扁平的单子链没有深度嵌套的函数组合：

它有效，但我想通过折叠从递归中抽象出来。正常的折叠似乎不起作用，至少与Task类型无关，

因为行中的代数A会为每次迭代返回 a Task，而不是部分应用的函数。

如何用折叠替换非尾递归？

这是当前递归实现的一个工作示例：

[编辑] 根据评论中的要求，我的折叠实现：

我最近读到了递归方案，其中变态被描述为类似于 generalized foldr。

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

我们能否定义一个递归方案（不失其一般性）来构造值 top-down而不是自下而上？

这将非常有帮助，因为我已经看到很多次使用递归方案在内部定义的函数首先应用于reverse其输入，清楚地表明需要类似foldl“从前到后”的执行。

我希望看到香蕉、镜头等的 Coq 版本。它们是在sumtypeofway 递归方案简介的优秀系列博客文章中建立的

然而，博客文章是在 Haskell 中的，它允许无限的非终止递归，因此完全满足于Y组合器。哪个 Coq 不是。

特别是，定义取决于类型

它构建了无限类型 f (f (f (f ...)))。 Term f 允许使用 Term 类型族对 catamorphisms、paramorphisms、anamorphisms 等进行非常漂亮和简洁的定义。

尝试将此移植到 Coq

给了我预期的

问：在 Coq 中形式化上述 Haskell Term 类型的好方法是什么？

上面f是 type Type->Type，但也许它太笼统了，可能有一些方法可以限制我们使用归纳类型，使得每个应用程序 都f在减少？

也许有人已经在 Coq 中实现了Banans、Lenses、Envelopes的递归方案？

考虑这段代码：

它定义了一个递归数据类型，以及一个通过遍历它来执行搜索和替换的函数。但是，我正在使用显式递归，并且想改用递归方案。

首先，我投入了makeBaseFunctor ''MyStructure。为了清楚起见，我在下面扩展了生成的 Template Haskell 和派生的 Functor 实例。然后我能够重写descend：

如果我在这里停下来，我已经取得了胜利：我不再需要在 中写出所有的情况descend，而且我不会意外地犯错误，例如descend (Baz x y) = Baz x (makeReplacements replacements y)（忘记替换里面x）。但是，这里仍然存在显式递归，因为我仍在使用makeReplacements它自己的定义。我如何重写它以删除它，以便我在递归方案中进行所有递归？

在递归方案中，我怎样才能用类型定义来构造一些东西，比如(Recursive t, CoRecursive t) -> t -> ? -> t

我尝试使用递归方案来更新节点。以列表为例，我可以想出两种方法：

但是，这两种实现都很好。在这两个实现中， 和 的构造函数ListF出现[]在等式的两边。而且这个定义似乎不是唯一的。有没有更好的方法来使用递归方案执行列表更新？

我最近在 Haskell 中查找了一些关于递归方案的指南，但是大多数文章并没有超出实现这些概念所需的基本基础结构。

给定递归数据类型，如二叉树

我们还将实现一个类似的结构，用类型参数替换定义的递归部分，以便能够使用诸如等的通用cata折叠ana

连同一个固定点组合器

这允许我们用我们的新表示来表达任意嵌套的树。

所以我的问题很直截了当（也许很愚蠢）：我们在程序的其余部分中实际使用了哪种数据结构表示？我们两者都需要吗？理论上我们只能使用TreeF，但是根据我在玩弄以这种方式实现的表达式语法树时发现的情况，这往往有点问题，主要是因为您现在必须将树的每个级别包装在新的数据构造函数中据我所知，您不能再从基本类型类（如Showor ）自动派生Eq。

在recursion-schemes包中定义了以下类型：

它们是同构的吗？如果是，你如何证明？

我正在尝试构建以下递归方案：

如何something使用现代递归方案库中的常用函数，例如recursion-schemes？这个计划有一个众所周知的名字吗？

给定以下数据类型：

我的第一步是执行以下操作：

但我不确定如何将 Fix 与两个类型变量一起使用。

如何表示这些类型，以便可以使用 droste 或 matryoshka/Fix 使用递归方案？