问题标签 [recursion-schemes]

使用递归方案histo中的组织同态（

如何使用 获得相同的东西mhisto？

我想理解函子不动点的抽象概念，但是，我仍在努力弄清楚它的确切实现及其在 Haskell 中的变态。

例如，如果我根据“程序员的类别理论”一书 - 第 359 页定义，则以下代数

根据变质的定义，可以将以下函数应用于 ListF 的不动点，即 List，以计算其长度。

我有两个困惑。首先，Haskell 编译器如何知道 List 是ListF 的不动点？我从概念上知道它是，但是编译器怎么知道，即，如果我们定义另一个与 List 相同的 List'，我敢打赌编译器不会自动推断 List' 也是 ListF 的不动点，或者确实它？（我会很惊讶）。

其次，由于 cata lenAlg 的递归性质，它总是试图 unFix 数据构造函数的外层以暴露函数的内层（顺便说一句，我的这种解释是否正确？）。但是，如果我们已经在叶子节点，我们怎么能调用这个函数呢？

例如，有人可以帮助为以下函数调用编写执行跟踪以澄清吗？

我可能遗漏了一些明显的东西，但是我希望这个问题对于其他有类似困惑的人仍然有意义。

答案摘要

@nm 回答了我的第一个问题，指出为了让 Haskell 编译器找出 Functor A 是 Functor B 的不动点，我们需要明确。在这种情况下，它是

@luqui 和@Will Ness 指出，由于 fmap 的定义，在叶子上调用 fmap (cata lenAlg)，在这种情况下是 NilF，将返回 NilF。

我会接受@nm 的回答，因为它直接解决了我的第一个（更大的）问题，但我确实喜欢所有三个答案。非常感谢您的帮助！

我被告知以下功能在功率上是等效的

但是，对于我的生活，我无法弄清楚如何证明这一点。在 hyloM 中将 Monad 设置为 Identity 几乎是正确的，但 gTraversable不是Functor，我尝试了多种方法从 hylo 到 hyloM，但均未成功。

这些是同构的，还是至少在力量上相似？如果是这样，我如何证明这一点？

环顾四周，我注意到递归方案是一个相当笼统的概念，我想通过亲身体验来学习。所以我开始为井字游戏实现一个极小极大算法。这是一个设置舞台的小片段。随意跳过它，因为它只是完整性的基本实现或在在线 IDE中阅读

现在，对于有趣的部分。我想出了以下类型来定义我的游戏树：

而且，很容易，我们可以使用变形来表示通过所有合法移动来扩展游戏

极小极大算法被表示为一个变态，我们可以这样写

对于我的问题：我现在想构建一个GameTree在每个节点上标记了 minimax 结果的。所以我正在寻找的，我相信是这个功能：

我只是不知道如何用递归方案编写这个函数。有人可以帮我吗？

我想生成一个字典序列的数字，以便每个数字的数字总和是一个给定的常数。它有点类似于“子集和问题”。例如，如果我希望生成 sum = 3 的 4 位数字，那么我有一个类似的系列：

[3 0 0 0]

[2 1 0 0]

[2 0 1 0]

[2 0 0 1]

[1 2 0 0] ... 等等。

我能够使用以下代码在 Python 中成功地做到这一点：

我认为这不是一种非常有效的方法（因为我是 Python 新手）。它适用于 M 和 N (<10) 的小值，但除此之外真的很慢。我希望将它用于 M ~ 100 和 N ~ 6。我怎样才能使我的代码更有效率，或者有更好的编码方法吗？

我目前正在学习结构递归/变态意义上的折叠。我使用自然数的折叠来实现幂和阶乘。请注意，我几乎不知道 Haskell，所以代码可能很尴尬：

接下来我想调整斐波那契数列：

我有fib一对作为第二个参数，其字段在每次递归调用时交换。我被困在这一点上，因为我不了解转换过程的机制。

[编辑]

如评论中所述，我的fact功能是错误的。这是一个基于变形的新实现（希望如此）：

文件夹身份是

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

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

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

我知道如何获得

Int -> [Int]

与展开/安娜。

我正在寻找某种方式

Int -> Int

使用递归方案。

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

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

我正在学习递归方案，事实证明，针对列表类型实现它们对我很有帮助。然而，我被困在了同态。

这是tails我最近发现的关于 apo 的实现：

不幸的是，我无法Data.Functor.Foldable使用 GHCi 导入，因为我收到了未找到包的错误。另一项搜索揭示了这种特定于列表的 apo 实现：

显然，apoList的第一个参数与 不匹配tailsApo。我会将类型解释为apoList :: ([b] -> Either (a, b) [a])) -> [b] -> [a].

似乎没有更多关于这个主题的初学者友好信息。我很感激任何帮助。

我一直在尝试将这个递归的 Haskell 实现翻译为专门用于Lists的 futumorphism

进入一个命令式 Javascript 循环。这非常困难（至少对我来说）：

我很难在精神上解析 Haskell 代码，尤其是where包含递归调用的部分。我猜这个调用不在尾部位置，因此我的accJS 循环需要一个显式堆栈 ()。

我的翻译正确吗？