data State s a = ST (s -> (a,s))   -- State : * -> * -> *

instance Monad (State s) where     -- State s : * -> *
  return x = ST(\s -> (x,s))
  (ST m) >>= f = ST(\s -> let (x,s') = m s
                              ST f' = f x
                            in f' s')

type IOState = State (String,String)       -- StrState : * -> *

-- snoc: cons onto the end of a list
snoc :: a -> [a] -> [a]
snoc x xs = xs ++ [x]

getCharX :: IOState Char
getCharX = ST(\(x:ins,outs) -> (x,(ins,outs)))

putCharX :: Char -> IOState ()
putCharX c = ST(\(ins,outs) -> ((),(ins,snoc c outs)))

getput :: IOState ()
-- getput = getCharX >>= (\c -> getCharX >>= (\d -> (putCharX d >> putCharXc)))
-- using "do" notation for composing monad actions
getput = do c <- getCharX
            d <- getCharX
            putCharX d
            putCharX c

run :: (String,String) -> IOState a -> (a, (String,String))
run inout (ST f) = let (x,s) = f inout in (x,s)