Haskell 中的惰性和尾递归，为什么会崩溃？

StackOverflow https://stackoverflow.com/questions/1618838

题

我有一个相当简单的函数来计算一个大列表的元素的平均值，使用两个累加器来保存到目前为止的总和和到目前为止的计数：

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）），这显然是错误的。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top