Solo 如何防止空间泄漏？

Question

我遇到了有关单元素元组的文档Solo，并且对它如何防止空间泄漏感到有点困惑，这让我怀疑我不了解 Haskell 内存模型和/或垃圾收集器的工作原理。

引用文档，他们说：

Solo 最重要的特征是可以强制其“外部”（通常通过模式匹配）而不强制其“内部”，因为它被定义为数据类型而不是新类型。一种有用的情况是编写函数以从数据结构中提取值时。假设您编写数组的实现并仅提供此函数来索引它们：

index :: Array a -> Int -> a

现在想象一下有人想要从数组中提取一个值并将其存储在惰性值有限映射/字典中：

insert "hello" (arr `index` 12) m

这实际上可能导致空间泄漏。在强制该值（现在埋在映射中）之前，实际上不会从数组中提取该值。这意味着整个数组可以仅通过该值保持活动状态！通常，解决方案是使用严格的映射，或者在存储之前强制该值，但出于某些目的，这是不可取的。

这就是我难以理解的。大概a是装箱的，因此该数组arr是一个指针数组（如果它没有装箱，a则已经被评估，并且这个参数没有实际意义）。

所以我猜测这个数组中有arr一个指向类型为 的未评估的 thunk 的指针a。然后我们将它放入映射中，因此映射现在包含一个指向类型 未计算的 thunk 的指针a。现在我不明白为什么这个数组arr此时需要保持活动状态。我们在地图中创建的任何内容都没有指向arr。该映射有自己的指针，指向 type 的未计算的 thunk a，它可以在闲暇时对其进行评估。唯一保持arr活动状态的可能是未评估的 thunk 依赖于 array arr，但如果是这种情况，我不确定将值包装在Solo数据类型中有何帮助？

我确信我错过了一些东西。我怀疑了解我所遗漏的内容会暴露我上述想法的错误之处。如果我能找出自己错在哪里，那就太好了。那么有什么想法/解释吗？

Answer 1

Haskell 中本质上有两种“空间泄漏”。一种是在 thunk 上浪费空间，而尽早产生值会更有效地节省空间。另一个是在大数据结构上浪费空间，而稍后生成它们会更有效（或者根本不生成）。

作者正在考虑这样的表达：

index arr 12

想象这arr是一个大型数据结构，结果是其中包含的单个元素；所做的只是index选择元素。如果表达式index arr 12保留为 thunk，则 thunk 必然包含对 的引用arr，因此垃圾收集器将无法回收arrthunk 处于活动状态时的内存。

通常显而易见的事情是安排index arr 12比实际需要更早执行（正如作者建议的那样，将其放在严格的Map而不是惰性的中，但“将其放入映射中”的上下文实际上并不必要的）。如果您在决定这就是您要得到的内容时强制执行该表达式index arr 12（就像严格映射在向其中插入某些内容时所做的那样），而不是在您实际将其用于任何用途时，那么该函数index已在该点运行完成。arr在您使用结果之前，不再需要保留决策和参考。

但请记住，强制某些内容会将其计算为最外层的数据构造函数。index不涉及任何数据构造函数，因为它只是返回一个已经在arr. 因此，通过评估达到的最外层数据构造函数index arr 12将来自元素的任何类型。但是，如果 的元素arr（或至少索引 12 处的元素）本身存储为未计算的 thunk呢？如果这些元素实际上很大，那么完全生成这些元素之一完全可能并不比存储一大堆 thunks ¹好多少。通过index arr 12尽早强制，我们可能避免了一种空间泄漏（将大重击保持太长时间），但导致了另一种空间泄漏（太早产生大值）。如果不确定所涉及的类型，我们无法知道哪一种更糟糕！

问题在于，对最外层数据构造函数的评估强制“太多”。我们希望评估进行得足够远，不再依赖arr（即知道我们要返回它包含的哪些元素），但我们不想实际输入代表该元素的 thunk。

这里可以使用的方法Solo只是将数据构造函数包装在返回的元素周围，这样当您将 thunk 强制到最外面的构造函数时，您就可以到达Solo并且不再进一步。作者指出，解决保留整个数组的索引 thunk 造成的空间泄漏问题的一个常见解决方案是“包含一个可以在任意 Applicative 上下文中生成其结果的索引函数：indexA :: Applicative f => Array a -> Int -> f a”，并且您可以将Solo其用作 applicative将额外的数据构造函数放在正确的位置，而不需要使用实际上具有任何有趣效果的应用函子。

据我了解，包裹Solo只能解决第二个潜在的空间泄漏。indexA arr 12 :: Solo a不会神奇地停止，具体取决于arr您是否将其保留为重击。然而，它使您能够使用早期评估来解决arr空间泄漏，而不必接受元素本身的潜在泄漏。

^{1或者简单地说，完全生产它在时间或空间上的成本已经足够高，以至于我们}还不想为此付费。我们可能还没有完全确定是否要使用它；如果下游消费者事实证明不需要它，而我们宁愿不生成它，即使该元素比原始数组小得多（我们所需要的只是它比代表自身的 thunk 小）。

Answer 2

首先，您引用的文档有一个错误，但它实际上相当相关。

insert "hello" (arr index 12) m

应该

insert "hello" (index arr 12) m

事实上，这确实持有一个指向 的指针arr。在index arr 12求值之前，它是一个 thunk，保存着指向index、arr和 的指针12。index指向和 的指针12不是什么大问题，但arr可能很大。

现在，至于这种方式Solo有帮助……一般来说，它不会。这真是一个奇怪的说法。就像，他们提出了一个函数

indexA :: Applicative f => Array a -> Int -> f a

然后这样使用它：

case arr indexA 12 of
    Solo a -> insert "hello" a m

但这实际上不会有任何帮助，除非indexA有一个真正意想不到的实现。Solo正如数据类型描述所预期的那样，的实现pure是非严格的。因此，预期的实现indexA只是将查找结果包装为pure：

indexA arr i = pure $ index arr i

为了使所提供的解释有意义，实现需要更像这样：

indexA arr i = pure $! index arr i

我想如果一个库提供了该函数，那么只有在它有更严格的实现时才有意义，但我谨慎地假设这是类似函数的实现，或者Solo实际上对于解决本文档提出的问题很有用。

现在， 的严格性属性确实有用Solo，特别是对于Monad实例而言。让我们与Monad的实例进行对比Identity：

ghci> do { x <- pure () ; y <- undefined ; pure x } :: Identity ()
Identity ()

ghci> do { x <- pure () ; y <- undefined ; pure x } :: Solo ()
*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  undefined, called at <interactive>:8:26 in interactive:Ghci4

事实上，Solo在哪里被解除Identity并不会使Monad实例变得Solo更严格。(>>=)强制在其第一个参数中评估外部Solo构造函数，这意味着它实际上会注意到它是否在未使用时获得底部值作为其第一个参数。由于Identity构造函数在运行时不存在，因此对它们求值只是将所有计算推迟到以后，从而使实现(>>=)不那么严格

Answer 3

所以我猜测这个数组 arr 中有一个指向 a 类型的未计算的 thunk 的指针。然后我们将它放入映射中，因此映射现在包含一个指向 a 类型的未计算 thunk 的指针。现在我不明白为什么这个数组 arr 需要在此时保持活动状态。

重点是，这insert "hello" (index arr 12) m 不仅仅是将现有的未评估的 thunk 放入映射中。它创建一个新的 thunk 来表示index arr 12，并将其存储在地图中。而那一声重击确实需要arr还活着。