CODEWITHSUNDEEP
haskellstate-monad
Adam Smith
Adam Smith

Reputation: 54233

Sequence partially-applied Monadic Actions

I'm aware this is probably obvious, but my hoogle-fu is failing me here. I have a list of actions of type:

import Data.Vector.Mutable (STVector)
[STVector s a -> ST s ()]

That is, a set of actions that take a starting MVector and mutate it in some way

I also have a starting vector

import Data.Vector         (Vector, thaw, freeze)
v :: Vector a

After thawing v, how do I sequence these actions into a final result?

doIt :: forall s. Vector a -> [STVector s a -> ST s ()] -> Vector a
doIt v ops = runST $ do
  v' <- thaw v
  -- do all the things to v'
  unfreeze v'

If context helps, I'm attempting Advent of Code's day 16 puzzle (part 2), so ops is a long list of mutations that I actually need to run through literally a billion times. I expected to be able to use replicateM_ to do this, but can't see how to provide a starting value. I similarly thought foldM_ would work, but I can't seem to get it to typecheck. Perhaps I'm doing something fundamentally wrong? I can't say I understand the ST monad backwards and forwards yet.

Upvotes: 1

Views: 140

Answers (1)

Carl
Carl

Reputation: 27023

The operation you're looking for is traverse_. It visits each value in a data structure, applies a function with a monadic return type, and sequences their effects together while discarding their results. The "discarding their results" part is important. It means that the return type of traverse_ in this case will be ST s () instead of ST s [()]. The difference there is significant. It means that the operation won't build up a giant list of () values to eventually throw away.

The function you want to pass to traverse_ is the one that means "apply a function to v'". That could be written as \f -> f v', but there's a shorter version that's idiomatic and uses the $ operator. Note that you can rewrite the lambda above as \f -> f $ v', which can be rewritten as the section ($ v').

So you have traverse_ ($ v') ops, which is the correct operation, but it still won't type check. That's because of the type of runST, which requires that the type s in ST s be polymorphic. With your type signature as written, s is chosen by the caller of doIt. To make this work, you need to enable the RankNTypes extension by making sure {-# LANGUAGE RankNTypes #-} is at the top of the file, and then change the type to Vector a -> (forall s. [STVector s a -> ST s ()]) -> Vector a. This narrowing of the scope of the s type variable requires that s be polymorphic in the value passed to doIt. With that restriction in place, runST will type check successfully with the operation above.

For more information on why runST has such a funny type, see Lazy Functional State Threads, the paper which introduced the ST type and showed how it can be used to constrain mutability inside an externally-pure interface.

Upvotes: 3

Related Questions