“Sharing” 表示
f x
会重复使用它创建的
x
;但是对于
_Y g = g . g . g . g . ...
,每个
g
都会重新计算其输出(参见
这里和
这里)。
在这种情况下,共享版本的内存使用率要差得多,会导致空间泄漏(
参考)。
1
_Y
的定义反映了通常的 lambda 演算中 Y 组合子的效果,通过复制来模拟递归,而真正的递归则指相同(因此是“共享”的)实体。
在
x = f x
(_Y g) = g (_Y g)
两个 x
引用了同一个实体,但是每个 (_Y g)
引用了等价但不同的实体。这就是初衷。
当然,由于引用透明性,在 Haskell 语言中并不能保证任何这样的情况。但是 GHC 编译器确实会像这样运行。
_Y g
是常见的子表达式,它 可能 通过给它一个名称并重复使用该命名实体来被编译器“消除”,从而破坏整个目的。这就是为什么 GHC 有 “no common sub-expressions elimination” -fno-cse
标志,用于明确防止此类情况。以前你必须使用这个标志才能实现这里想要的行为,但现在不需要了。GHC 不再像几年前那样过于依赖公共子表达式的消除法。
免责声明:我是你正在引用页面的那一部分的作者。我希望获得维基页面上通常会出现的互动,但是这种情况从未发生过,所以我的工作没有像那样接受审查。也许是没人关心,或者它没有严重错误。维基页面似乎已经被荒废了多年。
1 涉及的 g
函数,
(3:) . minus [5,7..] . foldr (\ (x:xs) ⟶ (x:) . union xs) []
. map (\ p ⟶ [p², p² + 2p..])
给定所有奇素数的递增流,它会产生一个递增的奇素数流。为了产生值为N
的素数,它会消耗输入流,直到第一个大于sqrt(N)
的素数为止。因此,这些生产点大致由重复平方给出,在这些素数生成器的链(或"塔")中总共有~ log (log N)
个这样的g
函数,每个都可以立即进行垃圾回收,最低的一个仅使用已知的第一个奇素数3
就能产生其素数。
使用两级_Y2 g = g x where { x = g x }
,链中只有两个,但仅有顶部可以立即进行垃圾回收,如上面引用链接所述。