What is the difference between different orderings of the same monad transformers?

I am attempting to define an API to express a particular type of procedure in my program.

newtype Procedure a = { runProcedure :: ? }

There is state, consisting of a mapping of IDs to records:

type ID = Int
data Record = { ... }
type ProcedureState = Map ID Record

There are three basic operations:

-- Declare the current procedure invalid and bail (similar to some definitions of fail for class Monad)
abort :: Procedure ()
-- Get a record from the shared state; abort if the record does not exist.
retrieve :: ID -> Procedure Record
-- Store (or overwrite) a record in the shared state.
store :: ID -> Record -> Procedure ()

I have a few goals with these operations:

Procedures can make assumptions (unlike a raw Map.lookup call) about which records are available, and if any of their assumptions are wrong, the Procedure as a whole returns failure.
A series of Procedures can be chained together using <|> (from class Alternative) in order to fall back to Procedures that make different assumptions. (Similar to STM's orElse)

Given these goals, I believe I want some combination of the State and Maybe monads.

-- Which to choose?
type Procedure a = StateT ProcedureState Maybe a
type Procedure a = MaybeT (State ProcedureState) a

I can't figure out how the two orderings of Maybe and State will behave differently. Can anyone explain the difference in behavior between the two orderings?

Also, if you see a problem with my original thinking (perhaps I am over-engineering), feel free to point it out.

Conclusion: All three answers were helpful, but there was one common idea that helped me decide which ordering I wanted. By looking at the return type of runMaybeT/runStateT, it was easy to see which combination had the behavior I was looking for. (In my case, I want the return type Maybe (ProcedureState, a)).

Solution

Edit: I originally got the cases backwards. Fixed now.

The difference between orderings of monad transformer stacks really only matters when you're peeling off layers of the stack.

type Procedure a = MaybeT (State ProcedureState) a

In this case, you first run the MaybeT, which results in a stateful computation which returns a Maybe a.

type Procedure a = StateT ProcedureState Maybe a

Here the StateT is the outer monad, which means that after running the StateT with an initial state, you'll be given a Maybe (a, ProcedureState). That is, the computation may have succeeded, or may not have.

So which you choose depends upon how you want to handle partial computations. With MaybeT on the outside, you'll always get some sort of returned state regardless of the computation's success, which may or may not be useful. With StateT on the outside, you guarantee that all stateful transactions are valid. From what you describe, I would probably use the StateT variant myself, but I expect either could work.

The only rule for monad transformer ordering is that if IO (or another non-transformer monad) is involved, it must be the bottom of the stack. Typically people will use ErrorT as the next lowest level if it's required.