了解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)); 
}