foldRecM is the stack-safe way to traverse_ an Array

#1

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
#2

Post about Stack-safe foldr Stack-safe default foldr?

#3

Here is a stack-safe traverse Dissect.Class - purescript-dissect - Pursuit

#4

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
#5

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