# Help me understand Effect stack safety?

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

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

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

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

1 Like