Haskell尾部遞歸可預測性

我與haskell最大的問題之一是能夠（正確）預測haskell代碼的性能。雖然我遇到了更多難題，但我意識到我幾乎沒有理解。Haskell尾部遞歸可預測性

採取簡單的東西是這樣的：

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

據我所知，這不是嚴格意義上的尾調用（它應該需要保持1堆棧上），所以在看這個定義 - 什麼我可以推理嗎？計數函數顯然應該具有O（1）空間要求，但是這樣做嗎？我可以保證它會或不會？

2011-09-05 Heptic

你的意思_O（1）_除了列表，它現在必須創造空間的需求！該名單可能以前是一個懶惰的thunk。個人而言，對於像列表這樣的高級數據結構，當編譯器變得更快時，即使它在優化得到應用時以推理爲代價，我也會很高興;否則按照什麼克里斯建議 – gatoatigrado

回答你的問題是：[如何Haskell尾遞歸工作？]（http://stackoverflow.com/questions/412919/how-does-haskell-tail-recursion-work） –

在一個尾遞歸調用，遞歸調用是函數內發生的最後一件事。在你的例子中，1必須在遞歸調用返回後添加*，因此它不是尾遞歸。 – fredoverflow

如果您想更容易推理遞歸函數，請使用具有已知時間和空間複雜度的高階函數。如果你使用foldl或foldr，你就知道他們的空間複雜性不能是O（1）。但是如果你使用與foldl「從作爲Data.List模塊在

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

的功能將O（1）空間複雜性與foldl」是每個定義尾遞歸。

HTH克里斯

2011-09-05 05:15:16 Chris

回答