關於懶惰

Question

混亂我有一個函數

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

從而未能與大約10^6個元素（myLength [1..1000000]失敗）輸入堆棧溢出。我相信這是因爲當我用foldl'替換foldl時，thunk的構建起作用。 目前爲止這麼好。

但現在我有另一個函數以逆轉列表：

myReverse = foldl (\ acc x -> x : acc) [] 

它使用懶惰版本與foldl（而不是與foldl的「）

當我做 myLength . myReverse $ [1..1000000]。 這次它工作正常。我不明白爲什麼foldl適用於後一種情況而不適用於前者？

在此澄清myLength使用與foldl」，而myReverse使用與foldl

Answer 1

這是我最好的猜測，雖然我對哈斯克爾內部沒有專家（還）。

在構建thunk時，Haskell分配堆上的所有中間累加器變量。

當執行myLength中的添加時，它需要使用中間變量的堆棧。見this page。摘錄：

注意z1000000 = z999999 + 1000000於是1000,000壓棧：

當我們最終評估z1000000的問題開始。然後評估z999999。

請注意，z999999 = z999998 + 999999. 因此999999被壓入堆棧。然後 z999998被評估：

請注意，z999998 = z999997 + 999998. 因此，999998被推入堆棧。然後 z999997評價：

但是，執行列表構造的時候，這就是我認爲發生（這是猜測開始的地方）：

當評估z1000000：

注意z1000000 = 1000000： z999999。所以1000000被存儲在 z1000000內，以及鏈接（指針） 到z999999。然後評估z999999。

請注意，z999999 = 999999：z999998。 因此，999999存儲在z999999, 內，並附有指向z999998的鏈接。然後 z999998被評估。

等

注意z999999，z999998等。從尚未評估的表達式轉換爲單個列表項是Haskell的日常工作:)

由於z1000000，z999999，z999998等都在堆上，因此這些操作不使用任何堆棧空間。 QED。