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

我在这方面写了很多:

• 真实世界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 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被隐藏在某个参数的某个地方,它们可能会被执行很长时间,从而无法实现它们的目的.

通过改变seqs的位置,程序可以正常执行,而不会使用过多的内存.

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

Answer 3

你的理解是正确的,seq s (s+x)迫使你评价s.但它并没有强制s+x,因此你仍然在积极推进.

通过使用,$!您可以强制评估添加(对于两个参数,两次).这与使用爆炸模式的效果相同:

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