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 

从我能理解，以次应该在这里强制评估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 

由于“双师型”是在严格的原子类型双＃的包装，对优化和精确类型，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 2

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

Answer 3

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）。优化器识别不必要的懒惰，并生成不分配不必要内存的代码。