问题标签 [catamorphism]

我最近了解了一点 F 代数： https ://www.fpcomplete.com/user/bartosz/understanding-algebras 。我想将此功能提升到更高级的类型（索引和更高级别）。此外，我检查了“给 Haskell 一个提升”（http://research.microsoft.com/en-us/people/dimitris/fc-kind-poly.pdf），这很有帮助，因为它给了我自己模糊的名字“发明”。

但是，我似乎无法创建适用于所有形状的统一方法。

代数需要一些“载体类型”，但我们正在遍历的结构需要某种形状（本身，递归应用），所以我想出了一个可以携带任何类型的“虚拟”容器，但形状符合预期。然后我使用一个类型族来耦合这些。

这种方法似乎有效，为我的“cata”函数带来了一个相当通用的签名。

然而，我使用的其他东西（Mu，Algebra）仍然需要为每个形状单独的版本，只是为了传递一堆类型变量。我希望像 PolyKinds 这样的东西可以提供帮助（我成功地使用它来塑造虚拟类型），但它似乎只是为了反过来工作。

由于 IFunctor1 和 IFunctor2 没有额外的变量，我试图通过附加（通过类型族）索引保留函数类型来统一它们，但由于存在量化，这似乎是不允许的，所以我在那里留下了多个版本也。

有没有办法统一这两种情况？我是否忽略了一些技巧，或者这只是目前的限制？还有其他可以简化的事情吗？

以及 2 个可使用的示例结构：

ExprF1 似乎是一个正常有用的东西，将嵌入式类型附加到对象语言。

ExprF2 是人为设计的（恰好也被提升的额外参数（DataKinds）），只是为了找出“通用” cata2 是否能够处理这些形状。

输出：

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

折叠函数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吗？

我想对 n-ary Tree 数据结构进行折叠。（折叠在 Linq 中又称为聚合）
我设法提出了一个可行的解决方案：

getChildren是一个定义如何获取给定节点的子节点的函数。它必须为叶节点返回一个空的 IEnumerable。
定义了如何使用当前节点及其子节点的aggregator结果来处理节点。

该解决方案似乎有效，但存在一些问题：

• 该算法是递归的，它会炸毁深树的堆栈。
  如何重写函数以防止堆栈溢出？

• 该算法是惰性的，但只是一种。
  例如，如果aggregatoronly 使用Enumerable.First子节点的结果，则只遍历树的最左边的分支。然而，Enumerable.Last整个树被遍历，即使计算只需要最右边的分支。
  我怎样才能让算法真正变得懒惰？

欢迎使用 F# 解决方案，但首选 C#。

写完这篇文章后，我决定把钱放在嘴边，并开始转换我以前的项目来使用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 略快。不过也没关系。

这个问题的答案表明，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是固定的，并且仿函数用于描述如何递归地构造数据类型。

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

我有一个具有 Functor 实例的递归数据类型：

现在，我有兴趣修改此数据类型以支持通用递归方案，如本教程和本 Hackage 包中所述。我设法让变态起作用：

但现在我不知道如何给出Expr2与原来相同的仿函数实例Expr。尝试定义仿函数实例时似乎存在一种不匹配：

如何为 编写 Functor 实例Expr2？

我曾考虑将 Expr2 包装在一个 newtype 中，newtype Expr2 a = Expr2 (Fix (ExprF a))但是这个 newtype 需要被解包才能传递给cata，我不太喜欢。我也不知道是否可以Expr2像我一样自动派生仿函数实例Expr1。

许多 catamorphisms 似乎很简单，主要用自定义函数替换每个数据构造函数，例如

但是，我不清楚的是，如果使用相同类型的构造函数但使用不同的类型参数会发生什么。例如，而不是传递 a List ato Cons，怎么样

或者，也许是一个更疯狂的案例：

我对这???部分的两个看似合理的想法是

• (a -> b -> b)，即List递归替换构造函数的所有应用程序）
• (a -> List b -> b)，即仅替换所有List a应用程序。

两者中哪一个是正确的——为什么？还是会完全不同？

我正试图围绕变形的概念。

在函数式编程中，变形是对列表展开概念的概括。形式上，变形是通用函数，可以核心递归地构造某种类型的结果，并由确定下一个构造步骤的函数参数化。

它的双重性，catamorphism，在这篇文章中有很好的描述：什么是 catamorphism，它可以在 C# 3.0 中实现吗？.

C# 中多变行为的一个很好的例子是 LINQ 的Aggregate方法。

什么是变形等价物？将伪随机数生成器Random视为变形构造是否正确，或者展开过程是否应该始终包含如下所示的累加器函数（取自Intro to Rx的代码片段）？

我希望能够cata从recursion-schemes包中使用 Church 编码中的列表。

为方便起见，我使用了第二等级类型，但我不在乎。如果您认为有必要，请随意添加newtype、使用 GADT 等。

Church 编码的想法广为人知且简单：

基本上是“抽象的未指定”cons并且nil被用来代替“普通”的构造函数。我相信一切都可以用这种方式编码（Maybe、树等）。

很容易证明它List1确实与普通列表同构：

所以它的基础仿函数与列表相同，应该可以实现project它并使用recursion-schemes.

但我不能，所以我的问题是“我该怎么做？”。对于普通列表，我可以进行模式匹配：

由于我无法对函数进行模式匹配，因此我必须使用折叠来解构列表。project我可以为普通列表编写一个基于折叠的：

但是，我未能将其改编为 Church 编码列表：

cata具有以下签名：

要将它与我的列表一起使用，我需要：

1. 使用声明列表的基本函子类型type family instance Base (ListC a) = ListF a
2. 实施instance Recursive (List a) where project = ...

我在两个步骤中都失败了。

在阅读（并实现） http://blog.sumtypeofway.com/recursion-schemes-part-2/的一部分之后， 我仍然想知道cata函数中的类型是如何工作的。cata函数定义为：

我有类似的东西Term Expr。打开包装后我得到Expr (Term Expr). 代数 ( f) 被定义为f :: Expr Int -> Int。我知道我可以轻松调用以下命令：

我也可以想象：

但我认为以下内容行不通：

但是，我仍然不明白它在cata函数中的工作原理 - 我如何从Expr (Term Expr)to获取Expr a. 我知道这些值确实有效，但我只是没有得到类型 - 树的叶子会发生什么？这确实是一个mystery...

编辑：我会尝试更清楚地说明我不明白的内容。

在精神上，cata似乎是这样工作的：

• 适用fmap f于叶子。
• 现在我有了Expr Int，我可以调用fmap f我拥有的节点并继续前进。

在我申请时，它显然不是这样工作的fmap (cata f)。但是，最终该函数f被Expr Int作为参数调用（在叶子中）。这种类型是如何从Expr (Term Expr)以前的类型中产生的？