Haskell中执行代码的默认方式

Question

在下面的通用代码中：

nat = [1..xmax]
xmax = *insert arbitrary Integral value here*   

setA = [2*x | x <- nat]
setB = [3*x | x <- nat]

setC = [4*x | x <- nat]
setD = [5*x | x <- nat]

setOne = setA `f` setB
setTwo = setC `f` setD

setAll = setOne ++ setTwo

setAllSorted = quicksort setAll

请注意，此处的 'f' 表示一种类型为函数的。

f :: Integral a => [a] -> [a] -> [a] 

这不仅仅是 ++）。

Haskell 如何处理尝试打印 setAllSorted 的情况？

它是否获取 setA 和 setB 的值，计算 setOne，然后仅将 setOne 的值保留在内存中（在计算其他内容之前）？

还是 Haskell 会一直保留所有东西，直到得到 setAllSorted 的值为止？

如果是后者的情况，那么我该如何指定（使用 main、do 函数和所有其他 IO 方面的内容），让它执行前者而非后者？

我能告诉程序按照什么顺序计算和回收垃圾吗？如果可以，我该如何做到？

- user1125052

---

Haskell 并不定义代码的执行方式，只定义了结果必须是什么；这个问题本质上是与实现相关的。 - ehird

Answer 1

< p > setAllSorted函数的头部必须小于或等于尾部中的每个元素。因此，为了确定头部，必须计算setOne和setTwo中的所有元素。此外，由于所有集合都是常量应用形式，我相信它们在计算后不会被垃圾回收。这些数字本身可能会在集合之间共享，但将它们粘合在一起的cons节点可能不会（您对某些节点的定义取决于f的定义）。< /p >

- pat

---

即使它们是CAF，如果编译器可以确定在打印后它们不再被引用，它们也可以被收集。如果程序是main = print setAllSorted，那么有很大的机会，GHC（带有优化）将垃圾回收不再需要的部分。然而，这只是峰值内存的一个常数因子减少。 - Daniel Fischer

“常数因子”是指当数据量更大时，它会给出更大的减少吗？也就是说，它是否意味着峰值内存减少与计算和垃圾收集的数据量成正比？ - user1125052

Answer 2

由于Haskell的惰性求值特性，代码只有在需要时才会被执行。你可以把最终的打印输出看作是从列表setAllSorted中“拉取”元素，这可能会同时带来其他元素。

也就是说，运行此代码的过程如下：

1. 打印操作首先会对setAllSorted列表的第一个元素进行求值。
2. 由于该元素来自排序过程，因此需要对setAll中的所有元素进行求值（因为最小的元素可能是最后一个）。
3. 对setAll中的第一个元素进行求值需要先对setOne中的第一个元素进行求值。
4. f函数的实现方式决定了对setA和setB是否需要全部或部分进行求值，进而决定了是否需要对setOne中的所有元素进行求值。
5. 完成对setAllSorted的第一个元素的打印后，setAll将被完全求值。此时不再引用setOne、setTwo和较小的集合，因此它们都可以被垃圾回收。同时，setAllSorted的第一个元素也可以被回收。

因此，理论上来说，这段代码会一直占用setAll的内存，而setAllSorted、setOne和setTwo在任何时候都只会占用恒定的空间。对于较小的集合，取决于f函数的具体实现方式，它们也可能是同样的情况。

- hammar