import Control.Monad
import Control.Monad.Trans.Class
import Control.Monad.Trans.State
import Control.Monad.Trans.Maybe
import Control.Monad.IO.Class

type Stack = [String]

pop :: Stack -> (Maybe String, Stack)
pop (x:xs)  = (Just x, xs)
pop []      = (Nothing, [])

push :: String -> Stack -> ((), Stack)
push s xs = ((), s:xs)

mainLoop :: StateT Stack (MaybeT IO) ()
mainLoop = do
    input <- liftIO getLine
    if null input
         then do
             Just x <- state pop
             liftIO . putStrLn $ x
         else state $ push input
    mainLoop

main = runMaybeT (runStateT mainLoop [])

pop :: Monad m
    => StateT [a] m (Maybe a)
pop = do
  s <- get
  case s of
    x : s' -> Just x <$ put s'
    [] -> pure Nothing

push :: Monad m
     => a -> StateT [a] ()
push a = modify (a :)

pop :: MonadState [a] m
    => m (Maybe a)
push :: MonadState [a] m
     => a -> m a

s -> MaybeT m (a, s)

s -> m (Maybe (a, s))

StateT s m (Maybe a)

s -> m (Maybe a, s)

mainLoop :: MaybeT (StateT Stack IO) x
mainLoop = do
  input <- liftIO getLine
  if null input
    then do
      -- No pattern match!
      x <- MaybeT pop
      liftIO . putStrLn $ x
    else push input
  mainLoop

pop :: (MonadState [a] m, MonadFail m)
    => m a
pop = do
  s <- get
  case s of
    x : s' -> x <$ put s'
    [] -> fail "Empty stack"

mainLoop :: ( MonadState Stack m
            , MonadIO m
            , MonadFail m )
         => m x
mainLoop = do
  input <- liftIO getLine
  if null input
    then do
      x <- pop
      liftIO . putStrLn $ x
    else push input
  mainLoop