Hep*_*tic 1 optimization haskell
我使用haskell的一个最大问题是能够(正确地)预测haskell代码的性能.虽然我遇到了一些更难的问题,但我发现自己几乎没有理解.
采取这样简单的事情:
count [] = 0
count (x:xs) = 1 + count xs
据我了解,这不是严格的尾部调用(它应该在堆栈上保持1),所以看看这个定义 - 我能解释什么呢？计数函数显然应该有O(1)空间要求,但是这个是吗？我可以保证会不会或不会？
如果您想更容易推理递归函数,请使用具有已知时间和空间复杂度的高阶函数.如果您使用foldl或foldr,您就会知道它们的空间复杂度不能为O(1).但是,如果您使用Data.List中的foldl',请参阅
count = foldl' (\acc x -> acc + 1) 0
你的函数在空间复杂度上将是O(1),因为foldl'是每个定义的尾递归.
HTH Chris