State Monad containing Random and List in Haskell

Question

As I'm learning for my exam Functional Programming, I'm still trying to really understand Monads. What better way than to define one yourself? I defined this:

newtype ST a = ST (State -> ([a], State))
type State = StdGen

Basically a List Monad and a Random Monad in one. This monad should enable you to work with random functions and lists. Now comes the trouble because I was able to define the return function, however >>= does not quite do the trick.

instance Monad ST where
    return a = ST $ \g -> ([a], g)
    -- M a -> (a -> M b) -> M b
    st >>= f  = ST $ \s -> 
                let (x,s') = st s 
                in (f x) s'

Code is inspired from This paper p.218

Any explanations?

Answer 1

Let's be careful to keep track of all the types (I do this myself when I'm writing tricky code). First let's add an accessor for your ST type which will make things easier.

newtype ST a = ST { runST :: State -> ([a], State) }

Now we have runST :: ST a -> State -> ([a], State). When defining monad code, I like to immediately apply runST to all ST values, so I know what types I am really working 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 bs by using f. We have a list of as so let's try mapping

    -- map (runST . f) as :: [State -> ([b], State)]

Hmm, that's not so useful, let's try applying the state we have coming in, too:

    -- map (\a -> runST (f a) s) as :: [([b], State)]

Maybe we can work with this. We have a list of lists of b, and some other stuff. Let's name this rs (for "results"):

    let rs = map (\a -> runST (f a) s) as in

Now we can get a list of bs by concatenating all the result bs:

    let bs = concat (map fst rs) in  -- bs :: [b]

So that presumably is what we want to return. Now which State do we want to go with it? We have a problem because we have a lot of different States to choose from. Do we pick the last one in the list, or the first one? If the list is empty maybe we just return the State that came in. These are arbitrary choices -- as a physics professor of mine once said: "now we have to make a choice, which is a problem, because we're about to make the wrong one". This is very much true in functional programming; whenever you have to make an arbitrary choice like this, you're probably messing up.

If we take a step back and think about the meaning intuitively, an ST a computation takes a state and returns a list of choices with a new state to use for future calculations, each of which will produce a list of choices and a new state. We can combine all the lists together using concat, but we don't have a way to combine all the states together into one. With the random API we don't have this (we could imagine maybe bitxoring together all the states...).

Without a way to combine the states, our monad bind will have to forget most of the data it has, which is a decent sign that it's not going to obey the laws (though with a monad this complicated I fear the complexity of proving the 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 it is equivalent to StateT State []. Now each branch of the computation comes with its own random state, so we don't need to combine many states into one anymore. You might have better luck defining this monad -- do as I did and write down the types of everything you know, and try to get to what you need in a type-directed way. Try not to "forget" any information, and strive to use each input exactly once in constructing the output.

Sorry, this post was a bit vague and rambly -- I realize that I use a lot of intuitive principles when defining monads and I thought I'd try to share them. Remember, it's not enough to get definitions that type check (though that does get you a lot of the way there): check the laws, too, otherwise you will get weird stuff happening when you go to use do notation and the like.