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)会作为thunks（惰性求值的函数）被传递到递归中去。因此，整个计算过程将崩溃：

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

- Hisnessness

Answer 1

我曾经写过相关内容:

• 《Real World 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章节所述。

- Don Stewart

---

不错的东西。了解GHC优化很好，感谢提供书籍链接，看起来是一个很好的资源。然而，当我看到sth的帖子时，我想到了使用seq应该会破坏尾递归。seq必须在对go的递归调用已经被评估之后进行评估，因此根据我对尾递归的理解，它不再是尾递归，因此会导致堆栈溢出。当然，这种情况并没有发生，所以这里肯定有什么问题。Haskell是否特别处理seq？还是我对尾递归的理解有误？ - Hisnessness

seq 在运行时并不存在，它只是使用不同的求值策略的提示。生成的代码会完全不同。可以将其视为 {-# STRICT_WHNF #-} pragma（一种严格求值指令）。 - Don Stewart

Answer 2

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的位置，程序可以正常执行，而不会使用过多的内存。

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

- sth

---

没有bang模式的情况下，我喜欢这种方式，因为它将强制和递归调用分开，使其状态更清晰。 - Mr. Putty

Answer 3

你对seq s (s+x)的理解是正确的，它会强制评估s。但是它不会强制评估s+x，因此你仍然在构建thunks。

通过使用$!，您可以强制计算加法（两个参数都要计算两次）。这与使用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的情况下，最外层的函数是+，因此在传递给go之前，y被完全计算为一个数字。

---

哦，你可能收到了无限类型错误消息，因为括号没有放在正确的位置。当我第一次编写您的程序时，我也遇到了同样的错误 :-)

由于$!运算符是右结合的，没有括号go $! (s+x) $! (l+1)的含义与go $! ((s+x) $! (l+1))相同，这显然是错误的。

- Tom Lokhorst