haskell - 下面的函数尾调用优化了吗？

Question

我是haskell的新手(第一次尝试fn编程)，只是尝试了“真实世界haskell”书中的各种练习。有人可以纠正我并告诉我以下功能是否经过尾调用优化吗？如果是，那么你能纠正我是怎么做的吗？我在递归函数中加 1，所以我相信这应该抛出一个 stackoverflow 异常？

我尝试调用 myLength [1..2000000] 但它没有抛出任何 stackoverflow 异常

myLength (x:xs) = 1 + myLength(xs) 
myLength [] = 0

Answer 1

GHC 可能会将其优化为尾调用递归，但您编写的方式并非如此。为了尾调用递归，树中的“顶部”函数必须是递归调用。当我使用 [1..20000000000000] 在 GHCi 中运行您的代码时，它会因段错误而耗尽内存，因此它不适用于非常大的输入。

如果我们稍微重新安排一下您的定义，我认为它会更清楚地说明为什么它不是 TCR:

myLength (x:xs) =
    (+)
        1
        (myLength xs)
myLength [] = 0

在这里，我将其分解为本质上是一棵树的内容，并且可以表示为

        (+)
       /   \
      /     \
     1     myLength
              \
               xs

如你所见，这棵树中最后一个要调用的函数是 (+) , 不是 myLength .要解决此问题，您可以使用折叠模式:

myLength = go 0
    where
        go acc (x:xs) = go (1 + acc) xs
        go acc []     = acc

现在这棵树看起来像

             go
           /    \
         (+)     xs
        /   \
       1    acc

所以树中的顶部函数是 go ，这是递归调用。或者，您可以使用内置折叠来实现这一点。为了避免产生大量的 thunk，我的建议是使用 foldl'来自 Data.List :

myLength = foldl' (\acc x -> acc + 1) 0

虽然这可能需要很长时间来执行，但它不会炸毁堆栈，也不会建立吃掉 RAM 的 thunk。

但正如@DonStewart 所说，编译器在优化期间重新排列代码方面有相当大的自由度。