`traverse` but also thread state?

Help
#1

I’m trying to read data from a database for each element in a list, but a lot of the data retrieved for each would be duplicated, so I’m wanting to put together a cache of the data that I pulled. My first thought was I wanted to do something like a foldl where my cache could be part of the state/accumulator that gets threaded through each call, but I’m going to need to use traverse or sequence because I’ve got Effects being run for each iteration too. Is there a way to thread some state through each iteration of traverse or sequence? Or do I just fallback on an EffectRef? Or monad transformers with StateT _ Effect _? Or just abandon traverse/sequence and sort of manually build up my own version where I keep some extra state in there (I say that not having looked at the definiton of traverse so I don’t even know if that’s possible).

Thanks everyone!

#2

You can traverse using any Applicative effect. Generally, yes, you would use transformers (or some equivalent) to compose effects. Pure effects like StateT, ReaderT, WriterT essentially just extend you base type with additional inputs and output. So anytime you think something like:

  • I want to use traverse, but I need to thread in an extra argument: ReaderT extends your base effect with an additional function argument that is implicitly threaded around.
  • I want to use traverse, but I really need to collect additional data: WriterT extends your base effect with an additional output type that gets combined with append for every action. Note that many folds can be expressed in terms of append, since foldMap is a minimal implementation for Foldable.
  • I want to use traverse, but I need to thread and potentially change additional context: StateT extends your base effect with an input type, and a corresponding output. This lets you take in an additional argument, and modify it before sending it out again.

In fact I think it’s useful to think of an Applicative constraint as the bare minimum “this API is designed to let you use any effects you want”.

For threading state specifically, you might do something like:

processStrings :: Array String -> Effect (Tuple (Array String) Int)
processStrings  = flip runStateT 0 <<< traverse \elem -> do
  modify_ (add 1)
  lift $ Console.log elem
  pure $ elem <> " Processed"

main :: Effect Unit
main = do
  Tuple strings count <- processStrings [ "A", "B", "C" ]
  Console.logShow strings
  Console.logShow count
4 Likes
#3

Monad transformers it is. Thanks!!

#4

Interesting to see you’d recommend transformers over just using foldM - I see a comment that the foldM “function is not generally stack-safe”. Is that the motivation?

1 Like
#5

Stack-safety is determined by the underlying Monad/Applicative instance for whatever effect you are using. So a transformer itself doesn’t usually matter as far as stack-safety goes, but your base effect type does, since everything is interleaved through the base effect. Effect is not stack-safe, but something like Aff is always stack-safe. If you have something that can be written tail-recursively, you can use MonadRec to recover stack safety (which Effect does implement).

So both traverse and foldM are “not stack-safe in general” because stack-safety is determined by your choice of effect. foldM is certainly useful, and is absolutely one way to solve this. I was just providing an answer to the question of traverse. This pattern of choosing some Applicative to recover fold-like, or threading, or accumulation behavior is very common and general. You can smuggle pretty much any behavior into some Applicative or Monad.

5 Likes