If you are blowing the stack when doing `traverse_`

over an `Array`

then you can use this stack-safe `traverseRec_`

function instead, written in terms of `Data.Array.foldRecM`

```
-- | Traverse an `Array`, performing some effects
-- | at each value, ignoring the final result. Stack-safe.
traverseRec_
:: forall m a b
. MonadRec m
=> (a -> m b)
-> Array a
-> m Unit
traverseRec_ f ta = Data.Array.foldRecM (\_ x -> void $ f x) unit ta
```

I kind of think `traverseRec_`

should be in a library, but I’m not sure which library.

Who can write `traverseRec`

in terms of `foldRecM`

as a stack-safe alternative to `traverse`

?

```
-- | Traverse an `Array`, performing some effects
-- | at each value and accumulating the result. Stack-safe.
traverseRec
:: forall m a b
. MonadRec m
=> (a -> m b)
-> Array a
-> m (Array b)
```

2 Likes

Post about Stack-safe `foldr`

Stack-safe default foldr?

Here is an implementation of stack-safe `traverseRec`

based on What Nate told me about Array building

```
-- | Traverse an `Array`, performing some effects
-- | at each value and accumulating the result. Stack-safe.
traverseRec
:: forall m a b
. MonadRec m
=> (a -> m b)
-> Array a
-> m (Array b)
traverseRec f ta =
Array.reverse <$> Array.fromFoldable <$> Array.foldRecM accum Nil ta
where
accum bs a = do
b <- f a
pure $ List.Cons b bs
```

1 Like

FWIW, a `traverse`

over an array should generally be stack safe on the *Array* side. A traversal has stack-safety issues on two axes:

- Walking over the structure (in this case
`Array`

).
- Evaluating the effects (eg.
`Effect`

or `Aff`

).

For Array specifically, it’s `traverse`

implementation uses `log(n)`

depth, so many common effects which strictly evaluate (`Maybe`

, `Either`

) will probably be OK. However, effects which are (semantically) suspended under a function (`Effect`

, `ReaderT`

) won’t benefit from this as you will just essentially be building a long chain of thunks. Likewise, an effect that is always stack safe (`Aff`

or `ParserT`

) won’t help you if traversing your structure can blow the stack (`List`

).

The most reliable way to avoid stack safety issues is to make both axes stack safe. My personal opinion is that `MonadRec`

tends to be a bit of a kludge. You’ll end up paying for the abstraction (it requires at minimum *double* the number of binds) whether your underlying effects are stack safe or not. To me that’s a cost I don’t really want to pay. Like, you pay for stack safety one way or another, it’s just not obvious to me that you *always* want to pay for it in your effects. I prefer to make both “just work” along their appropriate axis.

Dissection is really neat because it is a systematic/mechanical way to make the first axes stack safe. Unfortunately, the overhead using Generics for this use case is just insane. To me, it makes a nice demo, but is unusable without a way to make it automatic *and efficient*.

1 Like