How to understand evalState in this State Monad Haskell code snippet?

I am looking at this compiler code snippet and do not understand what evalState does, being new to State Monad.

compileToAst :: FilePath -> String -> Either Errors (Contract (Check Type, Env, SourcePos))
compileToAst source code = case parse parser source code of
    Right ast -> let ast'            = evalState ast [globals]
                     errors          = lefts $ map ann $ toList ast'
                     ann (a, _, pos) = a `extend` sourcePosPretty pos
                 in if null errors then Right ast' else Left errors
    Left err  -> Left [(SyntaxError $ parseErrorTextPretty err, sourcePosPretty . NE.head $ errorPos err)]

Assuming stateful computation is in the form of s -> (a, s), ast is a monad, [globals] is s, and evalState ast [globals] returns type a. Where can I find the stateful computation definition transforming s to new s and yielding result a?

Solution

The function evalState has type:

evalState :: State s a -> s -> a

The type of the first argument, namely State s a, is actually isomorphic to the function type s -> (a, s). What this means formally is that there exist two functions that convert between them:

runState :: State s a -> (s -> (a, s))
state :: (s -> (a, s)) -> State s a

and if you apply one of these functions and then the other, you get back what you started with (i.e., they are inverses, and their composition is the identity function).

Less formally, it means that wherever you see State s a you can pretend it's the type s -> (a, s) and vice versa, since you can convert back and forth at will using these utility functions runState and state.

Therefore, all evalState does is take a first argument that's isomorphic to a stateful computation s -> (a, s) and runs it using an initial state given by its second argument. It then throws away the final state s and yields the final result of the computation.

Since it's the first argument to evalState that's the stateful computation, it's actually the ast returned when parse parser source code succeeds that's the stateful transformation s -> (a, s) you're looking for.

That is, the value ast has type:

ast :: State Env (Contract (Check Type, Env, SourcePos))

which is isomorphic to:

ast :: Env -> (Contract (Check Type, Env, SourcePos), Env)

so it's a stateful transformation that operates on a state consisting of an environment (list of symbol tables) and yields a contract. All evalState does is pass this stateful transformation an initial state/environment consisting of a singleton representing the global symbol table and then yields its final contract result (throwing away the final list of symbol tables, since it's no longer important once the contract is generated).

So, the way this compiler is designed, it compiles code into an "abstract syntax tree" that, instead of being a tree-like data structure, is actually a function giving a stateful transformation over an environment state that produces a contract; evalState just "runs" the transformation to generate the contract.