为什么这个递归函数没有被优化？(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

您的函数因堆栈溢出而失败,因为它不是尾递归的.在每个步骤中消耗一个堆栈帧,保持每个步骤的'a'的部分和.

该前奏的总和与尾调用来实现:

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)

使严格假设明确.这几乎相当于foldl'版本wrt.严格.