Trampolined state monad in Haskell, translated from RO Bjarnason's Stackless Scala With Free Monads,

SimpleStateMonad.hs

newtype State s a = State {runS :: s -> (a, s)}

instance Monad (State s) where
    return x = State $ \s -> (x, s)
    ma >>= f = State $ \s -> let (a, s1) = runS ma s
                             in runS (f a) s1

get = State $ \s -> (s, s)
put x = State $ \_ -> ((), x)

SimpleTrampoline.hs

data Trampoline a = More (() -> Trampoline a)
                  | Done a

runT (Done a) = a
runT (More k) = runT $ k ()

newtype State s a = State { runS :: s -> Trampoline (a, s)}

instance Monad (State s) where
    return x = State $ \s -> Done (x, s)

    ma >>= f = State $ \s -> let (a, s1) = runT (runS ma s)
                              in More (\() -> runS (f a) s1)

get = State $ \s -> Done (s, s)
put x = State $ \_ -> Done ((), x)

Trampoline.hs

{-# LANGUAGE GADTs #-}

data Trampoline a where
    Done :: a -> Trampoline a
    More :: (() -> Trampoline a) -> Trampoline a
    Bind :: Trampoline a -> (a -> Trampoline b) -> Trampoline b

interp (Done x) = Right x
interp (More k) = Left k
interp (Bind ma f) =
    case ma of
      Done a -> interp (f a)
      More k -> Left (\() -> Bind (k ()) f)
      Bind mb g -> interp (Bind mb (\x -> Bind (g x) f))

runT m = case interp m of
           Right a -> a
           Left k  -> runT (k ())

newtype State s a = State { runS :: s -> Trampoline (a, s)}

instance Monad (State s) where
    return x = State $ \s -> Done (x, s)
    ma >>= f = State $ \s -> More (\() -> runS ma s `Bind` (\(a,s1) -> More $ \() -> runS (f a) s1))

get = State $ \s -> Done (s, s)
put x = State $ \_ -> Done ((), x)