“Solo”如何防止空间泄漏？

Question

我查阅了关于单元素元组Solo的文档，对它如何防止空间泄漏有点困惑，这让我怀疑我对Haskell内存模型和/或垃圾收集器的工作原理一无所知。

引用文件，他们说:

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

索引:: 数组a-

现在，假设有人想从数组中提取一个值，并将其存储在惰性值有限映射/字典中:

< code >插入“hello”(arr index 12)m

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

这就是我难以理解的地方。大概a是装箱的，因此数组arr是一个指针数组（如果它没有装箱，a将已经被计算并且这个参数将是无意义的）。

所以我猜这个数组中有一个指针指向一个类型为a的未赋值的thunk。然后我们将它放在地图中，因此地图现在包含一个指针，指向a类型的未评估的thunk。现在我不明白为什么这个数组arr此时需要保持活动状态。我们在地图中创建的任何内容都不指向arr。地图有自己的指针指向a类型的未评估的沉闷，它可以自己评估。保持arr活性的唯一方法可能是，未评估的thunk是否依赖于数组arr，但如果是这种情况，我不确定将值包装在 data-type中有何帮助？

我肯定我错过了什么。我怀疑理解我错过了什么会暴露我上面的想法是错误的。如果我能找出我错的地方，那就太好了。有什么想法/解释吗？

Answer 1

匿名用户

所以我猜数组arr中有一个指针指向a类型的未赋值的thunk，然后我们把它放在map中，所以map现在包含一个指向a类型的未赋值的thunk的指针，现在我不明白为什么数组arr需要在这一点上保持活动。

关键是< code > insert " hello "(index arr 12)m 不只是将现有的未赋值的thunk放入映射中。它创建一个新的thunk来表示< code>index arr 12，并将其存储在映射中。并且thunk确实需要< code>arr仍然有效。

Answer 2

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

insert "hello" (arr index 12) m

应该是

insert "hello" (index arr 12) m

事实上，这会保持指向arr的指针。在计算index arr 12之前，它是一个thunk，用于保存指向index和 的指针。指向 index和 12的指针并不是什么大问题，但

现在，至于索罗的帮助方式...一般来说，它不会。这是一个非常奇怪的说法。比如，他们提出了一个函数

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

然后这样使用它:

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

但这实际上没有任何帮助，除非indexA有一个真正意想不到的实现Solo的pureindexA的预期实现只是用pure包装查找结果：

indexA arr i = pure $ index arr i

为了使所提供的解释有意义，实现应该更像这样:

indexA arr i = pure $! index arr i

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

现在，Solo的严格性属性有一些实际有用的东西，特别是关于Monadinstance。让我们对比一下Identity的Monad实例：

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在不被提升身份的地方，使得Solo的Monad实例更加严格。（

Answer 3

哈斯克尔基本上有两种“空间泄漏”。一种是在 thunks 上浪费空间，而如果只是提前产生价值会更节省空间。另一个是在大数据结构上浪费空间，而以后（或者根本不生产）会更有效率。

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

index arr 12

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

通常显而易见的事情是安排索引arr 12比实际要求更早执行（正如作者所建议的那样，把它放在一个严格的Map而不是一个懒惰的Map中，但“把它放在地图中”的上下文实际上并没有必要）。如果你在决定这是你得到的东西时强制表达式索引ar 12（就像你在其中插入一些东西时一样，而不是当你实际使用它做任何事情时，那么函数索引已经运行到完成，并且在你使用结果之前不再需要保留对arr的引用。

但是请记住，强制某些东西将其评估为最外面的数据构造函数。index不涉及任何数据构造函数，因为它只是返回一个已经在arr中的值。因此，通过评估index arr 12到达的最外面的数据构造函数将是来自任何类型的元素。但是如果arr的元素（或者至少是索引12中的元素）本身作为未评估的thunks存储怎么办？如果这些元素实际上很大，完全生成其中一个元素并不比存储一大组thunks¹好多少。通过提前强制index arr 12，我们可能避免了一种空间泄漏（将大thunk保留太长时间），但会导致另一种空间泄漏（过早产生大值）。如果不确定所涉及的类型，我们就不知道哪个更糟糕！

问题是对最外层的数据构造函数求值已经“太过分了”。我们希望计算进行得足够远，不再依赖于< code>arr(即，知道我们返回的是它包含的哪些元素)，但是我们不希望实际输入表示元素的thunk。

这里可以使用Solo的方法是简单地围绕返回的元素包装一个数据构造函数，这样当您将thunk强制到最外层的构造函数时，您就得到了Solo。作者指出，对于索引thunk保留在整个数组上的空间泄漏问题，一个常见的解决方案是“包含一个索引函数，该函数可以在任意的应用上下文中生成其结果：indexA:：Applicative f”=

不过，据我所知，在Solo中包装只能解决第二个潜在的空间泄漏。indexA arr 12:: Solo a不会神奇地根据arr停止，如果您将其作为thunk保留。然而，它使您能够使用早期评估来解决arr空间泄漏，而不必接受元素本身的潜在泄漏。

1 或者简单地说，在时间或空间上，完全生产它的成本都足够高，以至于我们还不想为此付出代价。而且可能还没有绝对确定我们将要使用它;如果下游消费者被证明不需要它，而我们宁愿不生产它，即使元素比原始数组小得多（我们所需要的只是它比代表自己的 thunk 小）。