How should I combine St monad and State monad (or equivalent)?

Question

I am building code to gain understanding, in fact a Solitaire solver. I have a simple brute force implementation which uses the State monad, really just to prove I can use it (it only keeps a count of each move evaluated). But now I want to use Unboxed Mutable arrays to record the visited boards and thereby shortcut evaluation of paths when I reach a board position which was already visited via another path. It seems that the ST monad doesn't allow me to thread implicit state, but that I must use ST (or IO), in order to get access to the Mutable array. So it seems I must combine two Monads - State to thread the state (which will actually include a Mutable array), and another (ST) to gain the Mutable array functions.

• Is this right?
• And if so, is there a better alternative than the (canonical?) combination of Data.Array.ST/Control.Monad.ST/Control.Monad.ST and mtl?
• If I do go this route, does it matter which order I stack ST and State?
• Should I consider rolling my own single Monad based on either or both ST or State in order to avoid using monad transformers?

Answer 1

I'm not 100% sure that the ST monad is the way to improve performance for a search task like this. But assuming it is... You can "thread state" by just putting the state that you want to keep into an STRef. You can do this without needing to mix multiple monads together, which should make things much simpler for you.

You definitely need either the ST or IO monad if you want mutable state. (Or the STM monad, but that's only used for thread synchronisation, which you don't need here.)

The order in which monads are stacked can matter - but in this case, it doesn't. If you had something like the List monad and the Error monad, then depending on the stacking order, an error either fails just one possibility in the list, or all possibilities in the list. For your case, there aren't any effects which change depending on stack order.

...which is fortunate, since there isn't a transformer for turning things into ST. So ST has to be the inner monad.

Having said all that, again, I don't think you actually need a monad stack here. I would think a simple STRef will do.

Answer 2

When using ST, any arrays or references you have are not really state in the State monad sense of the word: they are never modified! You can think of them as a pointer; the pointer is constant, though the things it points at may change. So you can just pass your arrays or references or whatever in to your ST actions as function arguments. The StateT machinery would be appropriate if you expected the ST action to need to return a different array than the one it was passed -- i.e. not just modify the existing array but create a fresh one. Since this is generally not the case, StateT is not appropriate.

If you really want to have a monad transformer stack, you could put your arrays and references into the environment of a ReaderT monad. But this is probably not necessary.