是否有以下函数尾调用optmized？

Question

我是haskell的新手(第一次尝试fn编程),并尝试从"真实世界haskell"一书中进行各种练习.有人可以纠正我,并告诉以下函数是否是尾部调用优化？如果是,那么你可以纠正我怎么做？我在递归函数中加1,所以我相信这应该抛出stackoverflow异常？

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

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

Answer 1

GHC可能会优化这个是尾调用递归,但你写它的方式不是.为了进行尾调用递归,树中的"top"函数必须是递归调用.当我在GHCi中运行代码时[1..20000000000000],它会因为分段错误而耗尽内存,因此它不适用于非常大的输入.

如果我们稍微重新安排你的定义,我认为它会更清楚地说明为什么它不是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

所以树中的top函数go是递归调用.或者,您可以使用内置折叠来实现此功能.为了保持从建设了很多的thunk的,我的建议是使用foldl'来自Data.List:

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

虽然这可能需要很长时间才能执行,但它不会炸毁堆栈,也不会构建占用RAM的thunk.

但正如@DonStewart所说,编译器在优化过程中重新安排代码有相当大的自由度.