Purescript 的 Data.Foldable for_ 不是堆栈安全的吗？

Question

如果 actions 是一个合适的大数组，这会造成堆栈溢出：

modifyPerIndex :: forall a. Array (Tuple Int (a -> a)) -> Array a -> Array a
modifyPerIndex actions array = run do
  mutableArray <- thaw array
  for_ actions \(Tuple index action) -> modify index action mutableArray
  pure mutableArray

这不是：

modifyPerIndex :: forall a. Array (Tuple Int (a -> a)) -> Array a -> Array a
modifyPerIndex actions array = run do
  mutableArray <- thaw array
  foreach actions \(Tuple index action) -> void $ modify index action mutableArray
  pure mutableArray

我假设 为什么 Control.Monad.ST 有自己的 foreach 版本。 for_ 的 Applicative & Foldable 比 foreach 的 Array 的约束要宽松得多。话虽这么说，我不确定 Applicative & Foldable 丢失了什么 for_ 不能堆栈安全（或者不能没有其他缺点）

我深入研究了源代码并注意到 for_ 是通过 foldr 实现的。我不确定在哪里可以找到 Array 的 foldr 实例。

我对其中的很多东西都很陌生，只是想拓宽我的一般理解。 :)

Answer 1

Array 的 Foldable 实例是 here, and here 是 foldr 的实际代码。如您所见，它是堆栈安全的，因为它根本不使用堆栈：它只是一个普通的旧 JS 循环，它改变了一个累加器。

最终不是堆栈安全的是traverse_（for_带有翻转参数）。查看the source：看到折叠函数是(*>) f？这意味着运行ning traverse_ 在某些 Foldable 上的结果将是一系列 *> 调用，如下所示：

traverse_ f [1,2,3,4] == f 1 *> f 2 *> f 3 *> f 4 *> pure unit

这里的关键见解是在 traverse_ 执行期间 f 计算实际上并不是运行。 traverse_ 只是像那样构建它们的链，并且只有当你去 bind 它时（使用 >>= 或在 do 内） - 那就是那个链被执行的时候.

当您尝试运行建立在 *> 上的计算时会发生什么？嗯，*> 是 applySecond, which itself utilizes <*> - an alias for apply, which is a method of Apply, whose instance for ST uses ap, which in turn relies on monadic bind 的别名。

ap 的主体绑定了第一个计算，即 f 1 *> f 2 *> f 3 *> f 4，但这不是尾调用，因此它进入堆栈。反过来，绑定该计算会导致尝试绑定它自己的左侧部分，即 f 1 *> f 2 *> f 3，依此类推，一直到 f 1。所以堆栈爆炸了。

traverse_（和for_）真的做不到更好，因为他们都是纯粹的，所以他们不能运行效果，所以他们只能做正在建立它们的链，希望其他人稍后会执行它。

答案就在这里：为什么不用知道如何运行效果的 traverse_ 的特殊版本？

然后看：Traversable!

它是一种 class 有点类似于 Foldable 的类型，但具有内置效果。基本上它可以折叠一个序列，但是折叠功能很有效。

这允许运行在不破坏堆栈的情况下产生一系列效果，但有一个不同的问题：您不能忽略最终结果。如果你有一个包含 100K 个元素的数组开始，你将在最后得到另一个。值得庆幸的是，这不是炸毁堆栈那么大的问题。

Purescript 的 Data.Foldable for_ 不是堆栈安全的吗？

Purescript's Data.Foldable for_ isn't stack safe?

purescript