Haskell 中的惰性和尾递归,为什么会崩溃?
-
06-07-2019 - |
题
我有一个相当简单的函数来计算一个大列表的元素的平均值,使用两个累加器来保存到目前为止的总和和到目前为止的计数:
mean = go 0 0
where
go s l [] = s / fromIntegral l
go s l (x:xs) = go (s+x) (l+1) xs
main = do
putStrLn (show (mean [0..10000000]))
现在,用严格的语言来说,这将是尾递归,并且不会有问题。然而,由于 Haskell 很懒,我的谷歌搜索让我明白 (s+x) 和 (l+1) 将作为 thunk 传递到递归中。所以这整件事都崩溃了:
Stack space overflow: current size 8388608 bytes.
经过进一步谷歌搜索,我发现 seq
和 $!
. 。我似乎不明白,因为我在这种情况下使用它们的所有尝试都被证明是徒劳的,错误消息说明了有关无限类型的内容。
最后我发现 -XBangPatterns
, ,它通过改变递归调用来解决这一切:
go !s !l (x:xs) = go (s+x) (l+1) xs
但我对此并不满意,因为 -XBangPatterns
目前是一个扩展。我想知道如何在不使用 -XBangPatterns
. 。(也许还能学到一些东西!)
为了让您理解我的缺乏理解,这是我尝试过的(唯一编译的尝试):
go s l (x:xs) = go (seq s (s+x)) (seq l (l+1)) xs
据我所知, seq 应该在这里强制评估 s 和 l 参数,从而避免 thunk 引起的问题。但我仍然遇到堆栈溢出。
解决方案
我已经就此写了大量文章:
首先,是的,如果您想要求对累加器进行严格评估,请使用 seq
并留在 Haskell 98 中:
mean = go 0 0
where
go s l [] = s / fromIntegral l
go s l (x:xs) = s `seq` l `seq`
go (s+x) (l+1) xs
main = print $ mean [0..10000000]
*Main> main
5000000.0
第二:如果您提供一些类型注释并使用 -O2 进行编译,则严格性分析将会启动:
mean :: [Double] -> Double
mean = go 0 0
where
go :: Double -> Int -> [Double] -> Double
go s l [] = s / fromIntegral l
go s l (x:xs) = go (s+x) (l+1) xs
main = print $ mean [0..10000000]
$ ghc -O2 --make A.hs
[1 of 1] Compiling Main ( A.hs, A.o )
Linking A ...
$ time ./A
5000000.0
./A 0.46s user 0.01s system 99% cpu 0.470 total
因为“Double”是严格原子类型 Double# 的包装器,并且具有优化和精确类型,所以 GHC 运行严格性分析并推断严格版本是可以的。
import Data.Array.Vector
main = print (mean (enumFromToFracU 1 10000000))
data Pair = Pair !Int !Double
mean :: UArr Double -> Double
mean xs = s / fromIntegral n
where
Pair n s = foldlU k (Pair 0 0) xs
k (Pair n s) x = Pair (n+1) (s+x)
$ ghc -O2 --make A.hs -funbox-strict-fields
[1 of 1] Compiling Main ( A.hs, A.o )
Linking A ...
$ time ./A
5000000.5
./A 0.03s user 0.00s system 96% cpu 0.038 total
如上面 RWH 章节所述。
其他提示
调用函数后, seq
函数强制评估第一个参数。当您将 seq s(s + x)
作为参数传递时, seq
函数立即被而不是调用,因为无需评估该参数的值。您希望在递归调用之前对 seq
的调用进行求值,这样就可以强制对其参数进行求值。
通常这样就完成了这个:
go s l (x:xs) = s `seq` l `seq` go (s+x) (l+1) xs
这是 seq s(seq l(go(s + x)(l + 1)xs))
的语法变体。这里对 seq
的调用是表达式中最外层的函数调用。由于Haskell的懒惰,这导致首先评估它们: seq
使用仍未评估的参数 s
和 seq l(go(s + x)(l)调用+1)xs)
,评估参数被推迟到某人实际尝试访问其值的点。
现在 seq
可以在返回表达式的其余部分之前强制计算其第一个参数。然后评估的下一步将是第二个 seq
。如果对 seq
的调用被隐藏在某个参数的某个地方,它们可能会被执行很长时间,从而无法实现其目的。
使用 seq
的更改位置,程序可以正常执行,而不会占用过多的内存。
该问题的另一个解决方案是在编译程序时( -O
或 -O2
)简单地在GHC中启用优化。优化器识别可有可无的懒惰并产生不分配不必要内存的代码。
您的理解是 seq s(s + x)
强制评估 s
。但它并没有强制 s + x
,因此你仍在构建thunk。
通过使用 $!
,您可以强制评估添加(对于两个参数,两次)。这与使用爆炸模式的效果相同:
mean = go 0 0
where
go s l [] = s / fromIntegral l
go s l (x:xs) = ((go $! s+x) $! l+1) xs
使用 $!
函数将转换 go $! (s + x)
相当于:
let y = s+x
in seq y (go y)
因此 y
首先被强制进入弱头正常形式,这意味着应用了最外层的函数。在 y
的情况下,最外面的函数是 +
,因此 y
在传递给 go <之前被完全评估为一个数字。 /代码>
哦,你可能得到了无限类型的错误信息,因为你没有在正确的地方使用括号。我第一次写下你的程序时遇到了同样的错误: - )
因为 $!
运算符是右关联的,所以没有括号 go $! (s + x)$! (l + 1)
的含义与: go $! ((s + x)$!(l + 1))
,这显然是错误的。