Haskell尾递归如何工作？

Question

我写了这段代码,我假设len是尾递归,但仍然会发生堆栈溢出.怎么了？

myLength :: [a] -> Integer

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

main = print $ myLength [1..10000000]

Answer 1

请记住,Haskell很懒惰.在绝对必要之前,您的计算(l + 1)不会发生.

'简单'修复是使用'$!' 强制评估:

myLength :: [a] -> Integer
myLength xs = len xs 0
where len [] l = l
      len (x:xs) l = len xs $! (l+1)

      main = print $ myLength [1..10000000]

Answer 2

似乎懒惰导致len构建thunk:

len [1..100000] 0
-> len [2..100000] (0+1)
-> len [3..100000] (0+1+1)

等等.你必须强迫每次len减少l:

len (x:xs) l = l `seq` len xs (l+1)

有关更多信息,请访问http://haskell.org/haskellwiki/Stack_overflow.