普雷斯金的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实例是这里，这里是foldr的实际代码。正如您所看到的，它是堆栈安全的，因为它根本不使用堆栈:它只是一个简单的老JS循环，可以对累加器进行变异。

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

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

这里的关键洞见是，f计算实际上并不是在traverse_的执行过程中运行的。traverse_只是像这样构建一个链，并且只有当您使用bind (使用>>=或在do中)时才会这样做--这就是执行该链的时候。

当您试图运行构建在*>上的计算时，会发生什么呢？*>是applySecond的别名，它本身使用<*> -- apply的别名，apply是Apply的方法，Apply的ST使用，这反过来又依赖于一元绑定。。

ap的主体绑定第一个计算，即f 1 *> f 2 *> f 3 *> f 4，但这不是一个尾调用，所以它在堆栈上运行。反过来，绑定计算导致试图绑定自己的左侧部分，即f 1 *> f 2 *> f 3，等等，一直绑定到f 1。所以堆就爆炸了。

traverse_ (和for_)不能做得更好，因为它们都是纯的，所以它们不能运行效果，所以他们所能做的就是建立一个链，希望其他人稍后会执行它。

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

可穿! ：

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

这允许在不触发堆栈的情况下运行一系列效果，但是有一个不同的缺点:不能忽略最终结果。如果您有一个具有100 K元素的数组要启动，您将在最后得到另一个数组。谢天谢地，这不是那么大的问题，如吹倒堆栈。