18

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

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

4

3 回答 3

25

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

首先，是的，如果您想严格评估累加器的使用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 章节所述。

于 2009-10-24T19:40:12.700 回答
9

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被隐藏在某个参数中的某个地方，它们可能很长一段时间都不会执行，从而违背了它们的目的。

随着seqs 位置的改变，程序可以很好地执行，而不会使用过多的内存。

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

于 2009-10-24T20:16:04.220 回答
6

您的理解是正确的，这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))，这显然是错误的。

于 2009-10-24T19:40:19.347 回答