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

Question

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

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带来的问题。但我仍然遇到堆栈溢出。

Answer 1

一旦调用该函数，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 的惰性，这导致它们首先被求值：使用尚未求值的参数 s 和 seq l (go (s+x) (l +1) xs)，评估参数被推迟到有人实际尝试访问其值的时候。

现在，seq 可以强制在返回表达式的其余部分之前计算其第一个参数。那么评估的下一步将是第二个seq。如果对 seq 的调用被隐藏在某个参数中的某个位置，它们可能很长时间都不会被执行，从而达不到它们的目的。

随着 seq 位置的改变，程序可以正常执行，而不会使用过多的内存。

该问题的另一个解决方案是在编译程序时在 GHC 中启用优化（-O 或 -O2）。优化器认识到可有可无的惰性，并生成不分配不必要内存的代码。

Answer 2

我对此写了大量文章：

• 真实世界 Haskell，第 24 章：控制评估
• 关于 Haskell 中的递归和严格性

首先，是的，如果你想要求对累加器进行严格评估，请使用 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 章节所述。

Answer 3

您的理解是正确的，seq s (s+x) 强制对s 求值。但它不会强制 s+x，因此您仍在构建 thunk。

通过使用 $! 您可以强制计算加法（对于两个参数，两次）。这实现了与使用 bang 模式相同的效果：

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