This is an attempt to de-mystify how Control.Monad.State.get seems to magically create a State out of nothing.

demystify_state_monad.hs

{-
  Dear reader, 
  
  This is an attempt to de-mystify how Control.Monad.State.get seems to 
  magically create a State out of nothing. 

  Here's an example taken from the documentation: 
  
  tick :: State Int Int
  tick = do 
    n <- get
    put (n+1)
    return n
  
  Now, the magical part is n <- get. Read this source file from top to 
  bottom and hopefully it won't be as magical.
  
  Cheers,
  Mads Hartmann Jensen (mads379@gmail.com , @mads_hartmann )
  
  NOTE: 
    Some of the function bodies I've implemented as an exercise and 
    some I've copied from libraries/mlt/Control/Monad/State/Lazy.hs 
    of the GHC source distribution. All the type signatures have been
    copied. 
  
  PS: 
    This requires to run GHCI with the following flags: 
      -XMultiParamTypeClasses 
      -XFunctionalDependencies 
      -XFlexibleInstances 
      -XTypeSynonymInstances 
  
    (Crazy! I know!)
-}

import Control.Monad.Identity
import Control.Monad.Trans.Identity(IdentityT)

--  Defining what a State is. It's simply a new name for a function that takes 
--  a state and returns a pair with the return value and the new state. This is 
--  key to getting how get works. Read on. 
newtype State s a = State { runState :: s -> (a, s) }

-- A type class that deals with states. So we can use get and put in do-expressions. 
class Monad m => MonadState s m | m -> s where
  get :: m s 
  put :: s -> m ()

-- Make State an instance of Monad by partially applying the State type 
-- constructor with s. 
instance Monad (State s) where
  -- We simple create a new State that preserves the previous state and has a as
  -- the return value. 
  return a = State $ \s -> (a,s)
  -- from documentation: uses the final state of the first computation as 
  -- the initial state of the second.
  (State f) >>= k = State $ \s -> let (a, s') = f s ; (State f') = k a in f' s'

-- Our instance of MonadState.
instance MonadState s (State s) where
  -- yay, finally at the juicy part. Because a State is just a function from State to 
  -- a return value and a new state we simply define 'get' by returning the state as 
  -- the return value and leave the state untouched. 
  get   = State $ \s -> (s,s)
  -- We discard the previous state and use the new state. The return value is () as 
  -- we don't have anything more sensible to return. 
  put s = State $ \_ -> ((),s)

-- From documentation: Execute this state and return the new state, throwing away 
-- the return value
execState :: State s a -> s -> s
execState m s = snd (runState m s)

tick :: State Int Int
tick = do 
  n <- get
  put (n+1)
  return n 
  
run = do putStrLn $ show $ execState tick 0