performance - 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

我已经写了很多关于这个:

Real World Haskell, ch 24: controlling evaluation

On recursion and strictness in 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 章节所述。