我偶然看到了关于Solo
的文档,一个元素元组,有点困惑于它是如何说它可以防止空间泄漏的,这让我怀疑我没有理解Haskell内存模型和/或垃圾收集器是如何工作的。
引用医生的话,他们说:
Solo最重要的特性是可以强制其“外部”(通常通过模式匹配)而不强制其“内部”,因为它被定义为一个数据类型而不是一个新类型。当编写一个函数从数据结构中提取一个值时,这一点很有用。假设你编写了一个数组的实现,并只提供这个函数来索引它们:
index :: Array a -> Int -> a
现在,假设有人想从数组中提取一个值,并将其存储在一个惰性值有限Map/字典中:
insert "hello" (arr `index` 12) m
这实际上会导致空间泄漏。直到值(现在隐藏在Map中)被强制,值才真正从数组中提取出来。这意味着整个数组可能只通过该值保持活动!通常,解决方案是使用严格的Map,或者在存储值之前强制该值,但对于某些用途,这是不希望的。
这就是我理解起来有困难的地方。假设a
被装箱了,因此数组arr
是一个指针数组(如果它没有被装箱,a
就已经被求值了,这个参数就没有意义了)。
我猜在这个数组arr
中有一个指针指向一个未赋值的thunk,它的类型是a
,然后我们把它放在map中,所以map现在包含了一个指向a
类型的未赋值thunk的指针。现在我不明白为什么这个数组arr
需要在这个点上保持活动状态。我们在map中创建的任何东西都不指向arr
。map有自己的指针指向a
类型的未赋值thunk,它可以在空闲时对它求值。唯一能让arr
保持活动的可能是未赋值thunk是否依赖于数组arr
,但如果是这种情况,我不确定将值 Package 在Solo
数据类型中有什么帮助?
我确信我错过了一些东西。我怀疑理解我错过了什么会暴露我上面的想法是错误的。如果我能找出我错在哪里,那是一件好事。所以有什么想法/解释吗?
3条答案
按热度按时间hwamh0ep1#
Haskell中有两种“空间泄漏”:一种是在thunk上浪费空间,而在早期生成值会更有空间效率;另一种是在大数据结构上浪费空间,而在后期生成它们(或者根本不生成)会更有效率。
作者们正在考虑这样一个表达式:
想象
arr
是一个大的数据结构,结果是包含在其中的单个元素;index
所做的一切就是选择元素。如果表达式index arr 12
被保留为形实转换,则形实转换将必然包含对arr
的引用,因此,当形实转换处于活动状态时,垃圾收集器将无法回收arr
的内存。通常要做的事情是安排
index arr 12
比实际需要的时间更早执行(正如作者所建议的,将其放在严格的Map
中而不是放在懒惰的Map
中,但实际上并不需要“将其放在Map中”的上下文)。如果您在决定要得到的结果时强制使用表达式index arr 12
(就像一个严格的Map在你插入一些东西时所做的那样),而不是在你实际使用它做任何事情的时候,那么函数index
已经在那个决定点运行完成,对arr
的引用不再需要保留,直到你使用结果。但是请记住,强制某个值将其计算为最外层的数据构造函数.
index
并不涉及任何数据构造函数,因为它只返回一个已经在arr
中的值.所以通过计算index arr 12
得到的最外层的数据构造函数将是来自任何类型的元素.但是如果arr
的元素(或至少索引为12的元素)* 本身存储为未计算的thunk ?如果这些元素实际上很大,完全生成其中一个元素并不比存储一个thunks 1的大数组好多少。(保持一个大的thunk太长时间),但导致了另一个(过早地产生一个大的值)。如果不确定所涉及的类型,我们就不能知道哪个更糟糕!问题是对最外层数据构造函数的求值已经“太多”了。我们希望求值进行得足够远,不再依赖于
arr
(即知道它包含了我们要返回的元素中的哪一个),但我们不希望实际输入一个表示该元素的形实转换程序。在这里使用
Solo
的方法就是简单地将数据构造函数 * 包裹 * 返回的元素,因此当您将thunk强制到最外层的构造函数时,您将得到Solo
,而不会再进一步。作者指出,对于索引thunk占用整个数组而导致的空间泄漏问题,一个常见的解决方案是“为了包括能够在任意应用上下文中产生其结果的索引函数:indexA :: Applicative f => Array a -> Int -> f a
“,并且您可以使用Solo
作为应用函数,将额外的数据构造函数放在正确的位置,而无需使用实际上具有任何有趣效果的应用函子。据我所知,用
Solo
Package 只能解决 * 第二个 * 潜在的空间泄漏。如果将indexA arr 12 :: Solo a
作为thunk,它不会神奇地停止依赖arr
。但是,它使您能够使用早期求值来解决arr
空间泄漏,而不必接受来自元素本身的潜在泄漏。1或者仅仅是因为完全生产它在时间或空间上的成本已经足够高,以至于我们还不想为此付出代价,而且我们可能还没有完全确定要使用它;如果下游消费者不需要它,而我们宁愿不产生它, 即使 * 该元素比原始数组小得多(我们所需要的只是它比表示自身的thunk小)。
yftpprvb2#
首先 , 你 引用 的 文档 有 一 个 错误 , 它 实际 上 相当 相关 。
中 的 每 一 个
应该 是
格式
实际 上 , 它 确实 保存 了 一 个 指向
arr
的 指针 。 在index arr 12
被 求值 之前 , 它 是 一 个 thunk , 保存 了 指向index
、arr
和12
的 指针 。 指向index
和12
的 指针 不是 什么 大 问题 , 但arr
可能 很 大 。至于
Solo
的 作用 ... ... 一般 来说 , 它 不会 起 作用 。 这 是 一 个 非常 奇怪 的 说法 。 比如 , 他们 提出 了 一 个 函数格式
然后 使用 它 :
格式
但是 这 实际 上 不会 有 任何 帮助 , 除非
indexA
有 一 个 真正 意 想不到 的 实现 。Solo
的pure
的 实现 是 非 严格 的 , 正如 从 数据 类型 的 描述 中 所 预期 的 那样 。 因此 , 预期 的indexA
的 实现 只是 用pure
Package 查找 的 结果 :格式
为了 使 所 提供 的 解释 有 任何 意义 , 实现 需要 更 像 这样 :
格式
我 想 , 如果 一 个 库 提供 了 该 函数 , 那么 只有 当 它 具有 更 严格 的 实现 时 , 它 才 有 意义 , 但 我 很 谨慎 地 假设 这 是 这样 一 个 函数 的 实现 , 或者
Solo
实际 上 对 解决 本 文档 提出 的 问题 很 有用 。现在 , 关于
Solo
的 严格 性 属性 有 一些 实际 上 有用 的 东西 , 特别 是 对于Monad
示例 。 让 我们 与Identity
的Monad
示例 进行 对比 :格式
Solo
被 提升 而Identity
没有 被 提升 的 事实 使得Solo
的Monad
示例 更加 严格 。(>>=)
在 其 第 一 个 参数 中 强制 对外 部Solo
构造 函数 求值 ,这 意味 着 它 实际 上 会 注意 到 它 是否 得到 了 一 个 底部 值 作为 它 的 第 一 个 参数 , 而 它 在 其他 情况 下 是 不 被 使用 的 。t 在 运行 时 存在 , 对 它们 求值 只是 将 所有 计算 推迟 到 以后 进行 , 从而 使(>>=)
实现 不 那么 严格mrwjdhj33#
我猜数组arr中有一个指针指向一个未赋值的,类型为a的thunk,然后我们把它放到map中,所以map现在包含一个指针指向一个未赋值的,类型为a的thunk,现在我不明白为什么这个数组arr需要在这一点上保持活跃。
关键是
insert "hello" (index arr 12) m
* 并不 * 只是将现有的未赋值的thunk放入map中,它创建了一个新的thunk来表示index arr 12
,并将 * 那个 * 存储在map中,而且这个thunk需要arr
仍然存在。