问题标签 [catamorphism]

文件夹身份是

更一般地说，使用折叠，您可以破坏结构并最终得到一个汇总值，或者以这样一种方式注入结构，最终得到相同的输出结构。

[Int] -> [Int] 或 [Int] -> Int 或 [Int] -> ?

我想知道展开器/l 是否有类似的身份。

我知道如何获得

Int -> [Int]

与展开/安娜。

我正在寻找某种方式

Int -> Int

使用递归方案。

是否有一个递归方案的名称，它类似于 catamorphism，但它允许在它仍在运行时查看最终结果？这是一个稍微做作的例子：

这个例子total在折叠的每一步都使用，即使它的值直到最后才知道。（显然，这依赖于懒惰的工作。）

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

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

我正在尝试将以下代码从 SML 转换为 haskell，但遇到了一些麻烦。

这是我尝试过的：

我收到错误消息Error: type constructor List_alg given 0 arguments, wants 2 ，但我不确定出了什么问题/如何解决。任何帮助，将不胜感激！

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

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

使用以下自然数的变态，我可以实现各种算术算法，而无需处理递归：

cataNat在我看来类似于原始递归。至少它的每个应用程序似乎都可以终止，无论提供zero和succ的哪种组合。在每次迭代中，整个问题都被最小/最简单的问题实例分解。因此，即使它在技术上不是原始递归，它似乎也具有同样的表现力。如果这是真的，则意味着变态不足以表达一般递归。我们可能需要一个hylomorphism。我的推理是否正确，也就是说，是否对任何类型的变质都成立，而不仅仅是自然数？

我试图确保我使用自然数的基本情况来理解初始代数和变态概念，但我肯定遗漏了一些东西（我的 Haskell 语法也可能一团糟）。

稍后编辑

我认为我的问题主要与定义和之间同构的函数Fx/相关。我的理解是N （自然数的集合），即.unFixNatF (Fix NatF)Fix NatFFix NatFNat = Zero | Succ Nat

具体是如何Fx定义的？这个对吗？

如果是这样，为什么这与对[0, succ]评估的初始代数1 + N -> N不同？

原帖

我知道对于自然数，我们有函子F(U) = 1 + U和初始代数F(U) -> U其中unit变为0并且n变为succ(n) = n + 1。对于另一个由函数h求值的代数，catamorphism cata将是cata(n) = h ⁿ (unit)。

所以可以把函子写成data NatF a = ZeroF | SuccF a，它的不动点为data Nat = Zero | Succ Nat

我想那我们可以定义Fx :: NatF (Fix NatF) -> Fix NatF或说Fix NatF = Fx (NatF (Fix NatF))

如果我们用String这样的载体类型定义另一个代数

那么我认为我们可以使用cata h = h . fmap (cata h) . unFix像 1 这样的自然数，如下所示

但这似乎不是公式cata(n) = h ⁿ (unit)。我在这一切中的错误在哪里？

我正在尝试在 Haskell 中实现表达式树，如下所示：

我希望能够使用变态对其进行操作。

目前，这是我得到的功能：

但是，每当我尝试将它与类型表达式一起使用时，都会ExprTr String Integer出现编译器错误。例如，运行cataTr id id id id (Var "X")返回以下编译器错误，而不是(Var "X").

我不确定如何进行。此外，我将不胜感激有关如何键入诸如 cataTr 之类的函数以使其以后更易于调试的一些建议。

由于我对 Haskell 还很陌生，我想了解如何从“第一原则”处理这种情况，而不是使用库为自己生成 catamorphism。

当转换器函数中需要给定项目的位置（索引或路径）时，使用哪一个是合适的态射（递归方案）？

一个简单的示例是将列表["foo", "bar", "qux"]转换为字符串"foo, bar, and qux"。需要当前元素的位置来知道何时插入and.

catamorphism 可以解构一个值

或维护结构并像底层类型的身份一样行事：

对于列表（或 JS 中的数组），变态和折叠（可折叠容器的）重合。

但是，对于树木，它们不会：

作为身份的角色按预期工作。然而，解构涉及更多。事实上，我需要一个列表折叠来执行它。我实际上可以看到有一层解构，因为否则列表折叠对于非线性树来说是不够的。但是仍然不得不使用另一个折叠似乎很奇怪。

我只能猜测这种行为与使用的变质的简洁定义有关。它只考虑产品的单个案例Tree a = Node a [Tree a]。如果我完全接受类型和区分Node/Array构造函数和空数组情况的代数结构，也许会更有希望。

但这是否意味着treeCata不是适当的变态？它缺少什么？