Be careful to keep track of all types (I do it myself when I write tricky code). First add an accessory for your ST type that makes things easier.
newtype ST a = ST { runST :: State -> ([a], State) }
Now we have runST :: ST a -> State -> ([a], State) . When defining the monad code, I like to immediately apply runST to all ST values, so I know what types I really work with.
st >>= f = ST $ \s -> -- runST st :: State -> ([a], State) -- f :: a -> ST b -- runST . f :: a -> State -> ([b], State) -- s :: State let (as, s') = runST st s in -- I renamed x to as for readability -- as :: [a] -- s' :: State
Now we need a ([b], State) . We can get b using f . We have a list a , so try matching
-- map (runST . f) as :: [State -> ([b], State)]
Hmm, this is not so useful, try to apply also the state we entered:
Perhaps we can work with this. We have a list of lists b and some other things. Call it rs (for "results"):
let rs = map (\a -> runST (fa) s) as in
Now we can get the list b by combining all the results of bs:
let bs = concat (map fst rs) in -- bs :: [b]
Thus, presumably this is what we want to return. Now, where is the State we want to go with him? We have a problem because we have many different State to choose from. Choose the last one from the list or the first? If the list is empty, perhaps we will simply return the State that came. This is an arbitrary choice - as one of my physics professors said: "Now we need to make a choice, which is a problem, because we are going to make the wrong one." This is very true in functional programming; whenever you have to make arbitrary choices like this, you probably messed up.
If we take a step back and think about the value intuitively, computing ST a takes a state and returns a list of options with a new state that will be used for future calculations, each of which will create a list of options and a new state. We can merge all lists together using concat , but we have no way to merge all the states together into one. With the random API, we don’t have this (we could imagine, perhaps, bitxor combining all the states ...).
Without a way of combining states, our monadic binding will have to forget most of the data that it has, which is a worthy sign that it will not obey the laws (although it is difficult with such a monad, I am afraid of the difficulty of proving laws). And as far as I know, there is no monad with this type.
There is a monad with this type:
newtype ST' a = ST' { runST' :: State -> [(a, State)] }
And this is equivalent to StateT State [] . Now each branch of the calculation has its own random state, so we no longer need to combine many states. Perhaps you are fortunate enough to define this monad - do it like me, and write down the types of everything you know and try to find what you need with a focus on the type. Try not to forget any information and try to use each input exactly once when constructing the output.
Sorry, this post was a bit vague and intimidating - I understand that I use a lot of intuitive principles when defining monads, and I thought I would try to separate them. Remember, this is not enough to get definitions that check type (although this gives you a lot of way): also check the laws, otherwise you will get strange things when you go to use do notation and the like.