共享与非共享定点组合器
Sharing vs. non-sharing fixed-point combinator
这是Haskell中定点组合子的通常定义：
fix :: (a -> a) -> a
fix f = let x = f x in x
在 https://wiki.haskell.org/Prime_numbers 上，他们定义了一个不同的定点组合器：
_Y :: (t -> t) -> t
_Y g = g (_Y g) -- multistage, non-sharing, g (g (g (g ...)))
-- g (let x = g x in x) -- two g stages, sharing
_Y is a non-sharing fixpoint combinator, here arranging for a recursive "telescoping" multistage primes production (a tower of producers).
这到底是什么意思？在这种情况下，"sharing" 与 "non-sharing" 是什么？ _Y 与 fix 有何不同？
_Y 翻译成以下 STG：
_Y f = let x = _Y f in f x
fix 的翻译与 Haskell 来源相同：
fix f = let x = f x in x
所以fix f设置了一个递归thunk x和returns它，而_Y是一个递归函数，重要的是它不是尾递归的。强制 _Y f 进入 f，将 new 调用作为参数传递给 _Y f，因此每次递归调用都会设置一个 new 砰的一声；强制 fix f 返回的 x 进入 f，将 x 本身作为参数传递，因此每次递归调用都进入同一个 thunk——这就是“共享”的含义.
共享版通常有更好的内存使用率，也能让GHC RTS检测到某些无限循环。当一个 thunk 被强制时，在评估开始之前，它被替换为一个“黑洞”；如果在评估 thunk 期间的任何时候从同一线程到达黑洞，那么我们知道我们有一个无限循环并且可以抛出异常（您可能已经看到显示为 Exception: <<loop>>）。
"Sharing" 表示 f x 重新使用它创建的 x；但是对于 _Y g = g . g . g . g . ...，每个 g 都会重新计算其输出（参见 this and this）。
在这种情况下，共享版本的内存使用率要差得多，leads to a space leak。1
_Y 的定义反映了通常的 lambda 演算定义对 Y 组合子的影响，它 通过复制模拟 递归，而真正的递归指的是 same（因此，shared）实体。
在
x = f x
(_Y g) = g (_Y g)
两个 x 都指的是 相同的 实体，但是每个 (_Y g) 指的是等效但独立的实体。无论如何，这就是它的意图。
当然，由于引用透明性，Haskell 语言 无法保证任何这些。但是 GHC 编译器 确实是这样的。
_Y g 是一个常见的子表达式，它 可以 由编译器通过给它一个名称并重用该命名实体来 "eliminated" ，颠覆它的全部目的。这就是为什么 GHC 有 "no common sub-expressions elimination" -fno-cse 标志来明确阻止这种情况。过去，您必须使用此标志才能在此处实现所需的行为，但现在不是了。 GHC 将不再像最近的（阅读：现在几年）版本那样积极地消除常见的子表达式。
免责声明：我是您所指页面那部分的作者。希望维基页面上经常出现来回的来回，但它从来没有出现过，所以我的工作没有得到那样的评论。要么没有人打扰，要么 还过得去（没有重大错误）。 wiki 似乎已经被废弃很多年了。
1涉及的g函数，
(3:) . minus [5,7..] . foldr (\ (x:xs) ⟶ (x:) . union xs) []
. map (\ p ⟶ [p², p² + 2p..])
给定所有奇素数的增加流，产生所有奇素数的增加流。为了产生价值 N 的质数，它消耗其输入流直到价值超过 sqrt(N) 的第一个质数， 至少。因此生产点数通过重复平方得到粗略的，并且链中总共有~ log (log N)个这样的g个函数（或"tower") of these primes producers, 每个立即垃圾收集器，最低的产生它的素数给定第一个奇数素数，3，先验已知。
并且对于两阶段 _Y2 g = g x where { x = g x } 链中只有两个，但是 只有最上面的 会立即成为垃圾回收器，如讨论的那样在上面引用的link处。
从 GHC/Haskell 的角度来看，我认为您已经收到了很好的答案。我只是想插话并添加一些 historical/theoretical 注释。
递归的展开视图和循环视图之间的对应关系在长谷川的博士论文中得到了严格的研究：https://www.springer.com/us/book/9781447112211
（这是一篇较短的论文，您无需支付 Springer 费用即可阅读：https://link.springer.com/content/pdf/10.1007%2F3-540-62688-3_37.pdf）
Hasegawa 假设一个有迹幺半群范畴，这一要求比领域理论的通常 PCPO 假设要宽松得多，这构成了我们一般思考 Haskell 的基础。长谷川展示的是，可以在这样的设置中定义这些 "sharing" 个不动点运算符，并确定它们对应于 Church 的 lambda 演算中不动点的通常展开视图。也就是说，无法通过让它们产生不同的答案来区分它们。
长谷川的信件适用于所谓的中心箭头；即，当不涉及 "effects" 时。后来，Benton 和 Hyland 扩展了这项工作，并表明当底层箭头也可以执行 "mild" 单子效应时，对应关系适用于某些情况：https://pdfs.semanticscholar.org/7b5c/8ed42a65dbd37355088df9dde122efc9653d.pdf
不幸的是，Benton 和 Hyland 只允许相当 "mild" 的效果：像状态和环境 monad 这样的效果符合要求，但不适合像异常、列表或 IO 这样的一般效果。 （用于这些有效计算的定点运算符在 Haskell 中称为 mfix，类型签名为 (a -> m a) -> m a，它们构成了递归 do 表示法的基础。）
如何扩展这项工作以涵盖任意单子效应仍然是一个悬而未决的问题。尽管这些天它似乎并没有受到太多关注。 （对于那些对 lambda 演算、单子效应和基于图形的计算之间的对应关系感兴趣的人来说，这将是一个很好的博士课题。）
这是Haskell中定点组合子的通常定义：
fix :: (a -> a) -> a
fix f = let x = f x in x
在 https://wiki.haskell.org/Prime_numbers 上，他们定义了一个不同的定点组合器：
_Y :: (t -> t) -> t
_Y g = g (_Y g) -- multistage, non-sharing, g (g (g (g ...)))
-- g (let x = g x in x) -- two g stages, sharing
_Yis a non-sharing fixpoint combinator, here arranging for a recursive "telescoping" multistage primes production (a tower of producers).
这到底是什么意思？在这种情况下，"sharing" 与 "non-sharing" 是什么？ _Y 与 fix 有何不同？
_Y 翻译成以下 STG：
_Y f = let x = _Y f in f x
fix 的翻译与 Haskell 来源相同：
fix f = let x = f x in x
所以fix f设置了一个递归thunk x和returns它，而_Y是一个递归函数，重要的是它不是尾递归的。强制 _Y f 进入 f，将 new 调用作为参数传递给 _Y f，因此每次递归调用都会设置一个 new 砰的一声；强制 fix f 返回的 x 进入 f，将 x 本身作为参数传递，因此每次递归调用都进入同一个 thunk——这就是“共享”的含义.
共享版通常有更好的内存使用率，也能让GHC RTS检测到某些无限循环。当一个 thunk 被强制时，在评估开始之前，它被替换为一个“黑洞”；如果在评估 thunk 期间的任何时候从同一线程到达黑洞，那么我们知道我们有一个无限循环并且可以抛出异常（您可能已经看到显示为 Exception: <<loop>>）。
"Sharing" 表示 f x 重新使用它创建的 x；但是对于 _Y g = g . g . g . g . ...，每个 g 都会重新计算其输出（参见 this and this）。
在这种情况下，共享版本的内存使用率要差得多，leads to a space leak。1
_Y 的定义反映了通常的 lambda 演算定义对 Y 组合子的影响，它 通过复制模拟 递归，而真正的递归指的是 same（因此，shared）实体。
在
x = f x
(_Y g) = g (_Y g)
两个 x 都指的是 相同的 实体，但是每个 (_Y g) 指的是等效但独立的实体。无论如何，这就是它的意图。
当然，由于引用透明性，Haskell 语言 无法保证任何这些。但是 GHC 编译器 确实是这样的。
_Y g 是一个常见的子表达式，它 可以 由编译器通过给它一个名称并重用该命名实体来 "eliminated" ，颠覆它的全部目的。这就是为什么 GHC 有 "no common sub-expressions elimination" -fno-cse 标志来明确阻止这种情况。过去，您必须使用此标志才能在此处实现所需的行为，但现在不是了。 GHC 将不再像最近的（阅读：现在几年）版本那样积极地消除常见的子表达式。
免责声明：我是您所指页面那部分的作者。希望维基页面上经常出现来回的来回，但它从来没有出现过，所以我的工作没有得到那样的评论。要么没有人打扰，要么 还过得去（没有重大错误）。 wiki 似乎已经被废弃很多年了。
1涉及的g函数，
(3:) . minus [5,7..] . foldr (\ (x:xs) ⟶ (x:) . union xs) []
. map (\ p ⟶ [p², p² + 2p..])
给定所有奇素数的增加流，产生所有奇素数的增加流。为了产生价值 N 的质数，它消耗其输入流直到价值超过 sqrt(N) 的第一个质数， 至少。因此生产点数通过重复平方得到粗略的，并且链中总共有~ log (log N)个这样的g个函数（或"tower") of these primes producers, 每个立即垃圾收集器，最低的产生它的素数给定第一个奇数素数，3，先验已知。
并且对于两阶段 _Y2 g = g x where { x = g x } 链中只有两个，但是 只有最上面的 会立即成为垃圾回收器，如讨论的那样在上面引用的link处。
从 GHC/Haskell 的角度来看，我认为您已经收到了很好的答案。我只是想插话并添加一些 historical/theoretical 注释。
递归的展开视图和循环视图之间的对应关系在长谷川的博士论文中得到了严格的研究：https://www.springer.com/us/book/9781447112211
（这是一篇较短的论文，您无需支付 Springer 费用即可阅读：https://link.springer.com/content/pdf/10.1007%2F3-540-62688-3_37.pdf）
Hasegawa 假设一个有迹幺半群范畴，这一要求比领域理论的通常 PCPO 假设要宽松得多，这构成了我们一般思考 Haskell 的基础。长谷川展示的是，可以在这样的设置中定义这些 "sharing" 个不动点运算符，并确定它们对应于 Church 的 lambda 演算中不动点的通常展开视图。也就是说，无法通过让它们产生不同的答案来区分它们。
长谷川的信件适用于所谓的中心箭头；即，当不涉及 "effects" 时。后来，Benton 和 Hyland 扩展了这项工作，并表明当底层箭头也可以执行 "mild" 单子效应时，对应关系适用于某些情况：https://pdfs.semanticscholar.org/7b5c/8ed42a65dbd37355088df9dde122efc9653d.pdf
不幸的是，Benton 和 Hyland 只允许相当 "mild" 的效果：像状态和环境 monad 这样的效果符合要求，但不适合像异常、列表或 IO 这样的一般效果。 （用于这些有效计算的定点运算符在 Haskell 中称为 mfix，类型签名为 (a -> m a) -> m a，它们构成了递归 do 表示法的基础。）
如何扩展这项工作以涵盖任意单子效应仍然是一个悬而未决的问题。尽管这些天它似乎并没有受到太多关注。 （对于那些对 lambda 演算、单子效应和基于图形的计算之间的对应关系感兴趣的人来说，这将是一个很好的博士课题。）