问题标签 [catamorphism]

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

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

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

我只是在琢磨托尼莫里斯关于变质的出色练习，当时我正在思考在以下情况下发生了什么......

现在让我按如下方式调用此方法：

我想知道类型推断器是否确定了的类型_ => true是A => Boolean或Any => Boolean。由于其输入参数Function1是逆变的，因此以下两个编译都很好：

所以问题是，类型推断器提出#1 还是#2？

有时我发现自己在编程模式“如果 Bool 不为假”或“如果列表不为空，则使用它，否则使用其他东西”。

我正在寻找 Bool 和 List 的函数，它们是 Maybe 的“可能”函数。有吗？

更新：我的意思是使用 Bool-case 作为 List-case 的概括。例如，当使用 Data.Text 作为 T 时：

我希望减少这样的样板代码。

我很不耐烦，期待了解与这个 SO 问题相关的catamorphism :)

我只练习了 Real World Haskell 教程的开始。所以，也许我现在要求太多了，如果是这样，请告诉我应该学习的概念。

下面，我引用了catamorphism 的维基百科代码示例。

我想知道您对下面 foldTree 的看法，这是一种遍历 Tree 的方式，与其他 SO 问题和答案相比，还涉及遍历 Tree n-ary tree traversal。（与是否为二元无关，我认为可以编写下面的变态以管理 n 叉树）

我发表了我所理解的评论，如果你能纠正我并澄清一些事情，我会很高兴。

在这一点上我遇到了很多困难，我似乎猜测态射叶将应用于任何叶但是为了真正使用这段代码，需要为 foldTree 提供一个定义的 TreeAlgebra，一个具有定义的态射叶的 TreeAlgebra从而做点什么？
但在这种情况下，在 foldTree 代码中，我希望 {f = leaf} 而不是相反

非常欢迎您的任何澄清。

目前，梦想仍在继续，在我了解到的每个 haskell 概念中，我都更加着迷。然而，我还没有完全完成这个宝贵的@luqui 对我之前关于 catamorphism的问题的回答，我会回到它，直到它没问题。这是关于 Wikipedia 上的示例代码，处理BINARY trees 上的 catamorphism。

尽管如此，我已经尝试为非二叉树实现变态，但我遇到了一些麻烦：

-- 最新的一行在“map g [y]”上并不讨好 ghc

-- 而这个最新的 sumTree 对于 ghc 也是错误的

我看到 > 和 +，就像 C++ 运算符 > 和 +。所以我不明白 ghc 在没有我给予它实现操作符 >/+ 的情况下对我生气。

其次，我必须承认我对 => （不同于 -> ???）和 @ 的感觉完全模糊，这似乎是模式匹配的指南。

您将如何更正此代码？

还有一个最新的问题，我也在尝试这样做，因为复合模式恰好是 C++ 中对我来说最重要的。很明显，我看到它几乎可以用 Haskell 中的一两行来描述（这对我来说真是太神奇了）。

但是你会如何表达这样一个事实：Leaf 和 Composite 的 Composition 构造函数可能具有某种相同的接口？（我知道这不是个好词，因为数据是不可变的，但我希望你能猜到——理解我的关注/目标）

这是总的编译错误；

编辑 所以这是非二元变态的最终版本

根据下面的有效答案：我所要求的等效于 C++ 接口合同的 haskell 似乎是类型类约束。

因此，设计模式 Composite 将通过在构造 Composition a 时应用类型类约束来实现。也许应该定义一个新的专业数据。但在这样做之前我应该​​学习类型类:-)

Scalaz 提供了一个为各种 ADT 命名的方法，fold例如Boolean、Option[_]、等。该方法基本上采用与给定 ADT 的所有可能情况相对应的函数。换句话说，如下所示的模式匹配：Validation[_, _]Either[_, _]

相当于：

一些例子：

同时，还有一个Traversable[_]类型同名的操作，遍历集合，对其元素进行一定的操作，并累加结果值。例如，

为什么这两个操作使用相同的名称 - fold/catamorphism？我看不出两者之间有任何相似之处/关系。我错过了什么？

典型的学术例子是总结一个列表。是否有使用 fold 的真实世界示例来说明其效用？

从http://research.microsoft.com/en-us/um/people/emeijer/Papers/meijer94more.pdf第 3 页：

一般来说，变质在合成下是封闭的，这是不正确的

变质在什么条件下构成变质？更具体地说（假设我正确理解了该陈述）：

假设我有两个基本函子F，G并且每个都有折叠：foldF :: (F a -> a) -> (μF -> a)和foldG :: (G a -> a) -> (μG -> a)。

现在假设我有两个代数a :: F μG -> μG和b :: G X -> X.

什么时候构图(foldG b) . (foldF a) :: μF -> X是变态？

编辑：我有一个猜测，基于 dblhelix 的扩展答案：那outG . a :: F μG -> G μG一定是μG一些自然转换的组件η :: F a -> G a。我不知道这是否正确。（编辑 2：正如 colah 指出的那样，这已经足够但不是必需的。）

编辑 3： Haskell-Cafe 上的 Wren Thornton 补充道：“如果你有正确的分配属性（正如 colah 建议的那样），那么事情就会针对特定情况解决。但是，拥有正确的分配属性通常相当于在某个适当相关的类别中进行自然转换；所以这只是将问题推迟到适当相关的类别是否总是存在，以及我们是否可以形式化“适当相关”的含义。”

我真的很喜欢以通用方式处理变态/变形的想法，但在我看来它有一个显着的性能缺陷：

假设我们想以分类方式使用树结构 - 使用通用变态函数来描述不同的折叠：

现在我们可以编写如下函数：

不幸的是，这种方法有一个明显的缺点：在计算过程TreeT Int中，每个级别都会创建 的新实例，fmap只是为了立即被g. 与经典定义相比

我们depth1总是会变慢，对 GC 造成不必要的压力。一种解决方案是使用hylomorphisms并将创建树和折叠树结合在一起。但通常我们不想这样做，我们可能希望在一个地方创建一棵树，然后传递到其他地方以便稍后折叠。或者，以不同的变质被文件夹数次。

有没有办法让 GHC 优化depth1？像内联catam g然后在里面融合/砍伐森林之 g . fmap ...类的东西？

不用说，Haskell 中的标准构造

很棒而且非常有用。

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

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

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