共享与非共享定点组合器

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

fix :: (a -> a) -> a
fix f = let x = f x in x

On 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是一个非共享固定点组合器，这里安排一个递归“伸缩”多级素数产生（atower的生产者）。

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

“分享”的意思f x重新使用x它创造了；但与_Y g = g . g . g . g . ..., each g重新计算其输出（参见this and this).

In that context, the sharing version has much worse memory usage, leads to a space leak.¹

的定义_Y反映了通常的 lambda 演算定义的效果Y组合器，其中emulates重复递归，而真正的递归是指same（因此，shared） 实体。

In

    x      = f x
    (_Y g) = g (_Y g)

both xs 请参阅same实体，但每个(_Y g)s 指等效但独立的实体。无论如何，这就是它的意图。

当然，由于引用透明度，无法保证哈斯克尔语言对于这一切。但GHC 编译器确实有这样的行为。

_Y g是一个公共子表达式，它could编译器通过给它一个名称并重用该命名实体来“消除”它，从而破坏了它的整个目的。这就是为什么 GHC 拥有“没有公共子表达式消除” -fno-cse明确阻止这种情况的标志。过去，您必须使用此标志来实现此处所需的行为，但现在不再这样了。随着更新的（阅读：几年前）版本的出现，GHC 将不再那么积极地消除常见的子表达式。

免责声明：我是您所指的页面那部分的作者。我希望能像维基页面上常见的那样来回讨论，但它从未出现过，所以我的作品没有得到这样的审查。要么没人打扰，要么is尚可（没有重大错误）。维基百科似乎已经被废弃很多年了。

¹ The g function involved,

(3:) . minus [5,7..] . foldr (\ (x:xs) ⟶ (x:) . union xs) [] 
                      . map (\ p ⟶ [p², p² + 2p..])

给定所有奇素数的递增流，产生所有奇素数的递增流。产生素数N在值上，它消耗其输入流直到上面的第一个素数sqrt(N)至少在价值上。因此，通过重复平方粗略地给出生产点，并且有~ log (log N)这样的g链中的总功能（或"tower"） 这些素数生产者，每个立即垃圾收集，最低的一个产生其素数，仅给出第一个奇数素数，3，先验已知。

并且随着两阶段_Y2 g = g x where { x = g x }链条中只有两个，但是只有最上面的一个将立即被垃圾回收，如上面引用的链接中所述。