Haskell尾递归可预测性

Question

我对haskell最大的问题之一是能够(正确地)预测haskell代码的性能。虽然我有一些更难的问题，但我意识到我几乎没有理解。

举个简单的例子：

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

据我所知，这并不是严格意义上的尾部调用(它应该在堆栈上保留1)，所以看看这个定义--我能从中推断出什么呢？count函数显然应该有O(1)的空间需求，但是这个函数有吗？我能保证它会或不会吗？

Answer 1

如果你想更容易地推断递归函数，请使用具有已知时间和空间复杂度的高阶函数。如果您使用foldl或foldr，您就知道它们的空间复杂度不能为O(1)。但是如果您使用Data.List中的foldl‘，如

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

你的函数的空间复杂度将为O(1)，因为根据定义，foldl‘是尾递归的。

HTH克里斯