haskell - 为什么这个递归函数没有被优化？ ( haskell )

Question

我在 Haskell 中编写了自己的“sum”函数:

mySum [a] = a
mySum (a:as) = a + mySum as

并测试它

main = putStrLn . show $ mySum [1 .. 400000000]

只收到堆栈溢出错误。

以相同的方式使用 Prelude 的总和:

main = putStrLn . show $ sum [1 .. 400000000]

我没有堆栈溢出。

这可能是我正在评估的庞大列表，特别是如果传递给我的函数的列表正在被严格评估，尽管我不怀疑这一点的唯一原因是使用 Prelude 的总和与相同的列表我没有得到任何错误。

Answer 1

您的函数因堆栈溢出而失败，因为它不是 tail recursive .每次调用都会消耗一个堆栈帧，并在每一步保持 'a' 的部分和。

Prelude's sum是通过尾调用实现的:

sum     l       = sum' l 0
   where
    sum' []     a = a
    sum' (x:xs) a = sum' xs (a+x)

{-# SPECIALISE sum     :: [Int] -> Int #-}
{-# SPECIALISE sum     :: [Integer] -> Integer #-}
{-# INLINABLE sum #-}

这不消耗堆栈空间。

请注意， specialize 和 inline pragma 是必要的，以公开使 'a' 累加器安全使用而不会累积 thunk 的严格性信息。更现代的版本是:

    sum' []     !a = a
    sum' (x:xs) !a = sum' xs (a+x)

使严格性假设明确。这是 almost相当于 foldl'版本wrt。严格。