问题标签 [recursion-schemes]

我正在尝试了解 catamorphisms，我已经阅读了 Wikipedia 文章以及Inside F#博客上的F # 主题系列中的前几篇文章。

我知道这是折叠的概括（即，将许多值的结构映射到一个值，包括将值列表映射到另一个列表）。我认为 fold-list 和 fold-tree 是一个典型的例子。

可以使用 LINQ 的Aggregate运算符或其他一些高阶方法在 C# 中完成吗？

我正在寻找一些非常简单、易于理解的递归方案和核心递归方案（catamorphisms、anamorphisms、hylomorphisms 等）的解释，这些解释不需要遵循大量链接或打开类别理论教科书。我确信我已经无意识地重新发明了许多这些方案，并在编码过程中将它们“应用”在我的脑海中（我相信我们中的许多人都有），但我不知道我的（共同）递归方案是什么使用被称为。（好吧，我撒了谎。我刚刚读到其中一些，这引发了这个问题。但在今天之前，我不知道。）

我认为这些概念在编程社区中的传播受到了人们往往会遇到的令人生畏的解释和示例的阻碍——例如在维基百科上，但也在其他地方。

它也可能被他们的名字所阻碍。我认为有一些替代的，更少的数学名称（关于香蕉和铁丝网的东西？）但我也不知道我使用的递归方案的更简洁的名称是什么。

我认为使用具有表示简单现实世界问题的数据类型的示例而不是抽象数据类型（例如二叉树）会有所帮助。

不用说，Haskell 中的标准构造

很棒而且非常有用。

尝试在 Agda 中定义类似的东西（为了完整起见，我将其放入）

失败，因为f不一定是严格积极的。这是有道理的——通过适当的选择，我可以很容易地从这个结构中得到一个矛盾。

我的问题是：有没有希望在 Agda 中编码递归方案？已经完成了吗？需要什么？

我在函数式编程和 PLT 圈子中多次听到“代数”这个词，尤其是在讨论对象、共单子、透镜等时。谷歌搜索这个术语会给出对这些结构进行数学描述的页面，这对我来说非常难以理解。任何人都可以解释一下余代数在编程环境中的含义，它们的意义是什么，以及它们与对象和共子的关系？

我“发明”了一种递归方案，它是变态的推广。当您折叠具有多态性的数据结构时，您无法访问子项，只能访问折叠的子结果：

折叠函数phi只能访问 的结果self x，而不能访问 original x。所以我添加了一个加入功能：

现在可以以有意义的方式组合x和self x，例如使用(,)：

processTerm varArgs为每个标识符返回它在不同控制路径上接收到的实际参数列表。例如，bar (foo 2) (foo 5)它返回fromList [("foo", [2, 5])]

请注意，在此示例中，结果与其他结果统一组合，因此我希望存在使用Data.Foldable. 但总的来说，情况并非如此，因为phi可以应用其对内部结构的知识ExampleFunctor来以 Foldable 无法实现的方式组合“子项”和“子结果”。

我的问题是：我可以processTerm使用现代递归方案库中的库存函数进行构建recursion-schemes/Data.Functor.Foldable吗？

我filter使用来自recursion-schemesHackage 库的变形实现了一个损坏的函数：

该函数不是 : 的忠实实现filter，xfilter odd [1..5]但xfilter odd [0,0]没有。我试图通过使用显式递归来实现“重试”，phi然后用超态重新实现它，所以我以ana . para：

这是令人满意的，但我随后尝试在内部明确表达重试phi并在外部执行它们：

Right意思是“产生一个新元素”，Left意思是“用新种子重试”。

的签名phi开始看起来与专门用于列表的同态的第一个参数非常相似：

（[a] -> Either [a] [a]对[a] -> Prim [a] [a] (Either [a] [a]）

所以我想知道是否有可能使用同构或其他广义展开来实现过滤，或者ana . para是我所希望的最好的？

我知道我可以使用折叠，但问题是专门关于展开的。

这个问题使用来自http://hackage.haskell.org/package/recursion-schemes-4.0/docs/Data-Functor-Foldable.html的概念/导入

我正在尝试将其扩展为通过变质使给定的单子线程化。这是我要编译的代码：

但是由于某种原因，对distMin的调用cataM无法弄清楚使用相同的t.

我得到的错误是：

我在这里使代码变得不那么性感，并且更容易调试：

的定义g是导致问题的原因。

编辑：据我了解的问题是，当它调用distM它时，它只Base t需要推断类型，所以它无法解决t。这令人沮丧，因为我知道t我想使用什么。事实上，我认为如果我可以distM手动提供类型参数，它将解决问题，但我认为这是不可能的。

这是一个解决方案，但我对此不满意：

编辑 2：很酷的了解Proxy（感谢 Antal）。我已经使用 Haskell 多年了，刚刚学到了另一个新东西。我喜欢这种语言。我正在使用的解决方案是：

写完这篇文章后，我决定把钱放在嘴边，并开始转换我以前的项目来使用recursion-schemes.

有问题的数据结构是惰性 kdtree。请查看具有显式和隐式递归的实现。

这主要是一个简单的转换，大致如下：

至

现在，在对整个 shebang 进行基准测试后，我发现该版本比普通版本慢了KDTreeF大约两倍（在此处找到整个运行）。

只是额外的Fix包装让我在这里放慢了速度吗？有什么我可以做的吗？

注意事项：

• 目前这是专门用于（V3 Double）的。
• 这是 cata-after 变形应用。Hylomorphism 不适用于 kdtree。
• 我用cata (fmap foo algebra)了好几次。这是好习惯吗？
• 我使用 Edwardsrecursion-schemes包。

编辑1：

这有关系吗？https://ghc.haskell.org/trac/ghc/wiki/NewtypeWrappers 不是newtype Fix f = Fix (f (Fix f))“免费”的吗？

编辑2：

刚刚做了另一组基准测试。这次我测试了树的构造和解构。这里的基准测试：https ://dl.dropboxusercontent.com/u/2359191/2014-05-15-kdtree-bench-03.html

虽然核心输出表明中间数据结构没有被完全删除，并且现在线性搜索占主导地位并不奇怪，但现在KDTreeFs 比KDTrees 略快。不过也没关系。

假设我有如下定义（cata变质在哪里）：

我想知道是否有某种方法可以修改的定义，cata以便我可以链接一些对象，例如int通过它，这样我就可以为 alg 函数中的事物生成唯一的句柄，即“a0”、“a1”、“ a2"，...等。

编辑：为了更清楚地说明这一点，我希望能够拥有一些功能cata'，以便当我有类似于以下定义的东西时

然后run评估为“a0 && a1”或类似的东西，即这两个常量不会被标记为相同的东西。

这个问题的答案表明，Scala 中 Option 上的 fold 方法是一种变态。来自维基百科的catamophism是“从初始代数到其他代数的独特同态。这个概念已被应用于函数式编程作为折叠”。所以这看起来很公平，但让我把初始代数作为F-algebras类别中的初始对象。

因此，如果 Option 上的折叠真的是一个变态，则需要一些函子 F，以创建 F 代数的类别，其中 Option 将是初始对象。我不知道这个函子会是什么。

对于 Lists 类型A的函子F是F[X] = 1 + A * X. 这是有道理的，因为 List 是一种递归数据类型，所以如果X是，List[A]那么上面的内容读取类型列表A要么是空列表 ( 1)，要么是 ( ) an和 a+的对 ( ) 。但 Option 不是递归的。将只是（无或）。所以我看不到函子在哪里。*AList[A]Option[A]1 + AA

为了清楚起见，我意识到 Option 已经是一个仿函数，因为它需要Ato Option[A]，但是对列表所做的事情是不同的，它A是固定的，并且仿函数用于描述如何递归地构造数据类型。

在相关的说明中，如果它不是变质，它可能不应该被称为折叠，因为这会导致一些混乱。