我在 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 的总和与相同的列表我没有得到任何错误。
最佳答案
您的函数因堆栈溢出而失败,因为它不是 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。严格。
关于haskell - 为什么这个递归函数没有被优化? ( haskell ),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23893320/