Help me understand Effect stack safety?

Help
#1

I’m looking at this definition of traverse for arrays:

        return function (f) {
          return function (array) {
            function go(bot, top) {
              switch (top - bot) {
              case 0: return pure([]);
              case 1: return map(array1)(f(array[bot]));
              case 2: return apply(map(array2)(f(array[bot])))(f(array[bot + 1]));
              case 3: return apply(apply(map(array3)(f(array[bot])))(f(array[bot + 1])))(f(array[bot + 2]));
              default:
                // This slightly tricky pivot selection aims to produce two
                // even-length partitions where possible.
                var pivot = bot + Math.floor((top - bot) / 4) * 2;
                return apply(map(concat2)(go(bot, pivot)))(go(pivot, top));
              }
            }
            return go(0, array.length);
          };
        };

and this definition of apply for Effect

ap f a = do
  f' <- f
  a' <- a
  pure (f' a')

and I would have expected this to blow the stack

traverse (pure :: _ -> Effect _) (1 .. 1000000)

But it doesn’t. Can somebody help me understand how this is okay? I don’t suppose I can universally extrapolate that using traverse and sequence are stack-safe for any monad, and that I only need to worry about stack safety when manually recursing?

3 Likes
#2

Interestingly, I’ve noticed that I can quite easily blow the stack if I use Lists instead of arrays, which have traversable like

traverse f = map (foldl (flip (:)) Nil) <<< foldl (\acc -> lift2 (flip (:)) acc <<< f) (pure Nil)

where then just traversing 10000 elements gets me a stack overflow on a call to bind like I would expect.

So maybe it’s just safe for arrays because of that trick with splitting it on some pivot? Though I can’t fully understand how that gets you fewer bind calls…
Is traversing an array generally stack-safe for any monad?

3 Likes
#3

IIRC the Array instance basically creates a binary tree of applications and thus gets the stack depth down to log2(n). That works for traverse, because Applicative guarantees that the individual effects are independent (but still have to be run in order of course).

You can’t really do that for Lists because you can’t “slice” ranges out of a List in an efficient manner. As a more general tip if you have a large collection I’d generally avoid Lists in PureScript and stick to Arrays because JS engines optimize them so well.

6 Likes
#4

If you want Effect to be stack safe you can try this https://github.com/safareli/purescript-effect/tree/fast (from)

1 Like