Confusing type missmatch error in nested do blocks

Question

I'm trying to write an interpreter for a simple embedded scripting language.

The core of it is the eval function, which has the following signature.

type EvalState = () --for later
type EvalResult = State EvalState (IO (Either T.Text Value))
eval :: Expr -> EvalResult

The result type is like this because it is statefull, eval should be able todo IO and it can fail.

There are two datatypes: Expressions and Values and eval converts expression to values. For simple expressions, literals of primitive data types, it's implemented like this:

ok :: Value -> EvalResult
ok val = state (return . Right $ val,)

eval :: Expr -> EvalResult

eval (StrLit t) = ok (StrVal t)
eval (SymLit t) = ok (SymbolVal t)
eval (IntLit i) = ok (IntVal i)
eval (FloatLit f) = ok (FloatVal f)

My problem now is implementing eval for the list literal. Currently my code looks like this:

eval (ListLit elems) = do
  elems <- mapM eval elems
  do 
    opts <- sequence elems
    return $ fmap (Right . ListVal . V.fromList) (sequence opts)

And this produces the following error:

/home/felix/git/vmail/src/Interpreter/EvalAst.hs:37:13: error:
    • Couldn't match type ‘IO’
                     with ‘StateT EvalState Data.Functor.Identity.Identity’
      Expected: StateT
                  EvalState Data.Functor.Identity.Identity [Either T.Text Value]
        Actual: IO [Either T.Text Value]
    • In a stmt of a 'do' block: opts <- sequence elems
      In a stmt of a 'do' block:
        do opts <- sequence elems
           fmap (Right . ListVal . V.fromList) (sequence opts)
      In the expression:
        do elems <- mapM eval elems
           do opts <- sequence elems
              fmap (Right . ListVal . V.fromList) (sequence opts)
   |
37 |     opts <- sequence elems
   |             ^^^^^^^^^^^^^^

My problem is that I'm not understanding this error. My thinking goes like this: the first do puts me in the State monad, so I shold be able to "extract" the results from mapM eval elems which I expect to be [ IO (Either ...) ] The next do should put me in the IO monad (because that's the next inner type in the result type), so I should be able to extract IO values, and as far as I understood it, sequence elems should give me a IO [ Either ... ] which I can then extract, so what is my mistake?

user_3234959 · Answer

Monad do not compose, in general. I think you are being bit by this.

In general, if m and n are monads, we can not write m (n a) for a monadic action that mixes the features of m and n. In general, it could even fail to be a monad.

In your case, you are using something like State A (IO B) hoping to be able to access the state of type A and still do IO, but that's not the case.

Indeed, by definition we have (up to some wrappers):

State a b = a -> (a,b)
            |     | |-- result
            |     |-- new state
            |-- old state

which in your case State A (IO B) it becomes

State A (IO B) = A -> (A, IO B)
                 |     |  |-- result
                 |     |-- new state
                 |-- old state

Here, we can see that the new state must be generated without doing IO at all! This is a computation which forces the new state and the IO effects to be completely separated. It effectively behaves as if we had two separate functions

A -> A     -- state update, no IO here
A -> IO B  -- IO depending on the old state

Likely, that's not what you actually want. That is probably something like

A -> IO (A, B)

allowing the new state to be generated after IO is done.

To obtain that type, you can not nest monads, but you need a monad transformer like StateT:

StateT A IO B = A -> IO (A, B)

This is a monad. You will probably need to use lift or liftIO to convert IO actions to this type, but it should behave as desired.

Confusing type missmatch error in nested do blocks

1 Answers