瞭解Haskell的`map` - 堆棧還是堆？

Question

鑑於以下功能：

f :: [String] 
f = map integerToWord [1..999999999] 

integerToWord :: Integer -> String 

讓我們忽略的實施。下面是一個示例輸出：

ghci> integerToWord 123999 
"onehundredtwentythreethousandandninehundredninetynine" 

當我執行f，做所有的結果，即f(0) through f(999999999)獲得存儲在堆棧或堆嗎？

注意 - 我假設哈斯克爾有堆棧和堆。

運行此功能約1分鐘後，我沒有看到RAM從原來的使用增加。

Answer 1

準確地說 - 當你「執行」f它不會被評估，除非你以某種方式使用它的結果。當你這樣做時 - 根據滿足呼叫者需求的方式存儲它。

就本例而言 - 它不存儲在任何地方：函數應用於每個數字，結果輸出到您的終端並被丟棄。因此，在給定的時刻，你只分配足夠的內存來存儲當前值和結果（這是一個近似值，但對於這種情況它足夠精確）。

參考文獻：

• https://wiki.haskell.org/Non-strict_semantics
• https://wiki.haskell.org/Lazy_vs._non-strict

Answer 2

第一：吹毛求疵，下面的答案適用於GHC。一個不同的Haskell編譯器可以合理地實現不同的事情。

確實有堆和堆棧。幾乎所有東西都堆在一起，幾乎沒有任何東西在堆疊上。

考慮，例如，表達

let x = foo 17 in ... 

讓我們假設優化器不將其轉化成完全不同的東西。對foo的呼叫根本不出現在堆棧上;相反，我們在堆上創建了一個註釋，說明我們需要在某個時刻執行foo 17，並且x成爲本筆記的指針。

所以，要回答你的問題：當你打電話給f時，說明「我們需要在某一天執行map integerToWord [1..999999999]」的筆記被存儲在堆上，並且你得到一個指針。接下來會發生什麼取決於你的結果做了什麼。

例如，如果您嘗試打印整個東西，那麼是的，每次調用f的結果都會堆在堆上。在任何特定時刻，只有一個呼叫f在堆棧上。

或者，如果您只是嘗試訪問結果的第8個元素，那麼一堆「有問題f 5」的筆記最終堆在堆上，再加上f 8的結果，再加上其餘列表的註釋。

順便說一下，這裏有一個包（「真空」？），它允許您打印出您正在執行的實際對象圖。你可能會覺得它很有趣。

Answer 3

GHC程序使用堆棧和堆......但它根本無法像您熟悉的渴望語言堆棧機一樣工作。其他人將不得不解釋這一點，因爲我不能。

在回答你的問題的另一個挑戰是，GHC使用以下兩種方法：

1. 懶惰的評價
2. List fusion

在Haskell懶評價是指（爲默認規則）表達式僅在需求值時才被評估，即使這樣，它們也可能只被部分評估 - 只需要足夠遠以解決需要該值的模式匹配。所以我們不能說你的例子不知道什麼是要求其價值。

列表融合是內置於GHC中的一組重寫規則，它承認許多情況，其中「好」列表製作者的輸出僅作爲「好」列表消費者的輸入被消耗。在這些情況下，Haskell可以將生產者和消費者融合爲一個對象代碼循環，而不需要分配列表單元。

你的情況：

1. [1..999999999]是一個很好的製片人
2. map既是一個良好的消費和良好的生產
3. 但你似乎可以用ghci的，不這樣做融合。你需要用-O編譯你的程序才能發生融合。
4. 你還沒有告訴我們什麼會消耗map的輸出。如果它是一個好消費者，它將與map融合。

但有一個很好的機會，GHC會消除大部分或全部的列表單元分配的，如果你編譯（與-O）剛剛打印出碼結果的程序。在這種情況下，該列表將不會在內存中的所有編譯器存在，作爲一個數據結構會產生不大致相當於此東西對象代碼：

for (int i = 1; i <= 999999999; i++) { 
    print(integerToWord(i)); 
}