问题标签 [fixpoint-combinators]

xmonad我在包中看到以下代码：

看来这个fix函数来自Data.Function

但我不明白它是如何在这里使用的，什么时候有人会使用这个修复功能？

我想理解函子不动点的抽象概念，但是，我仍在努力弄清楚它的确切实现及其在 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 的回答，因为它直接解决了我的第一个（更大的）问题，但我确实喜欢所有三个答案。非常感谢您的帮助！

大家好，我正在尝试实现高阶函数 fix，它从初始点计算任意函数的有吸引力的不动点。也就是说，对于给定的和，形式的不动点。f :: a -> axfᴷ(x)fx

我目前的尝试是：

注意：如果函数没有从起点收敛，您的函数将不会终止。有人能帮助我吗 ？我试过但它没有返回任何东西

这是 Haskell 中定点组合器的通常定义：

在https://wiki.haskell.org/Prime_numbers上，他们定义了一个不同的定点组合器：

_Y是一个非共享定点组合器，在这里安排一个递归的“伸缩”多级素数生产（生产者塔）。

这到底是什么意思？在这种情况下，什么是“共享”与“非共享”？与有何_Y不同？fix

我尝试学习 haskell 并进行锻炼 - 尝试使用函数修复重写标准列表操作（map、foldr、zip、迭代等）。我有重复的例子：

它进一步简化

谁能帮我看地图？对不起我的英语不好，提前谢谢你。

（这不是专门的 Haskell 问题。）

我有一个递归数据结构。我想在它的每个级别附加一些额外的信息。这是一个简化的示例，其中我将 anX或 a添加Y到树的每个级别：

（TreeF对我来说，定义是不自然的。我更喜欢定义data Tree a = Leaf a | Tree a (Tree a) (Tree a)，但如果我这样做，我不知道如何陈述我的问题。所以我以Base仿函数的形式编写了它，ala Data .Functor.Foldable .)

该Wrap类型可用于附加信息X或Y某种数据。depth1'是一个深度 1 TreeF，其中Wrap每个级别都附加了标志（它只有一个级别）。depth2是一个深度 2 TreeF，Wrap在每个级别上都附加了标志（它有两个级别）。

如何创建任意深度的“包裹树”？我应该如何写它的类型签名？这种数据混搭有类别理论术语吗？

我最喜欢的测试我正在学习的语言能力的方法之一是尝试并实现各种定点组合器。因为我正在学习 Clojure（虽然我对 lisps 并不陌生），所以我也做了同样的事情。

首先，一些“可测试”的代码，阶乘：

对于我实现的任何组合器c，我想验证它((c !') n)是否等于(! n).

我们从传统的 Y 开始：

但是当然 Clojure 并没有那么懒惰，所以我们转向 Z：

事实上，它认为(= ((Z !') n) (! n)).

现在是我的问题：我无法让U或 Turing 组合器 (theta-v) 正常工作。我怀疑 U 是语言限制，而 theta-v 我更倾向于认为这是对维基百科符号的误读：

示例 REPL 体验：

谁能解释

1. 为什么 U 和 theta-v 的这些实现不起作用；和
2. 如何修复它们？

我不知道如何表达fix为尾递归算法。或者它已经是尾递归了？大概是我想多了……

我尝试了很多，但还没有想出任何远程有用的东西。尾递归算法可以很容易地转换为堆栈安全循环。这才是真正的目标。

我试图说服自己类型Fix和功能fix是一回事。
但我找不到他们的定义之间的相关性

构造函数如何Fix适应 的形式(x -> x) -> x？

在recursion-schemes包中定义了以下类型：

它们是同构的吗？如果是，你如何证明？