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

user_13500986 0
Viewed 93

If actions is a suitably large array, this creates a stack overflow:

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

This does not:

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

I'm assuming that's why Control.Monad.ST has its own version of foreach. for_'s Applicative & Foldable is a much looser constraint than foreach's Array. That being said, I'm not sure what Applicative & Foldable is missing such that for_ can't be stack safe (or can't be without some other drawback)

I've dug into the source a bit and have noted that for_ is implemented via foldr. I'm not sure where to find Array's foldr instance.

I'm pretty new to a lot of this, just trying to broaden my general understanding. :)

purescript
1 Answers

The Foldable instance for Array is here, and here is the actual code for foldr. As you can see, it's stack-safe, because it doesn't use stack at all: it's just a plain old JS loop that mutates an accumulator.

What ends up being not stack-safe is traverse_ (which is for_ with flipped arguments). Check out the source: see that the folding function is (*>) f? This means that the result of running traverse_ on some Foldable would be a series of *> calls, something like this:

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

The key insight here is that the f computations are not actually run during traverse_'s execution. traverse_ merely builds a chain of them like that, and only when you go and bind it (either with >>= or inside a do) - that's when that chain gets executed.

And what happens when you try to run a computation built on *>? Well, *> is an alias for 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.

The body of ap binds the first computation, which is f 1 *> f 2 *> f 3 *> f 4, but this is not a tail call, so it goes on the stack. In turn, binding that computation leads to trying to bind its own left part, which is f 1 *> f 2 *> f 3, and so on, all the way to f 1. So the stack blows up.

traverse_ (and for_) can't really do any better, because they're both pure, so they can't run effects, so all they can do is build up a chain of them in hopes that somebody else will execute it later.

And herein lies the answer: why not a special version of traverse_ that does know how to run effects?

And behold: Traversable!

It's a type class somewhat similar to Foldable, but with effects built-in. Basically it can fold over a sequence, but the folding function is effectful.

This allows running a series of effects without blowing the stack, but there is a different gotcha: you can't ignore the end result. If you have an array with 100K elements to start, you're going to get another one at the end. Thankfully, this isn't such a big problem as blowing the stack.

user_1802860
Related