Monad transformers: Implementation of a stack machine with MaybeT (State Stack)


I'm trying to implement a Maybe-State monad transformer and use it to implement a simple stack machine. The definitions of state monad and maybe should be correct. Now I'm trying to implement pop:

pop :: MaybeT (State Stack) Int

So that if the stack is empty it returns nothing, otherwise it returns Just <popped stack>. This is what I have so far:

pop :: MaybeT (State Stack) Int
pop = guard True (do (r:rs) <- get
                     put rs
                     return r)

(Obviously True is just a dummy placeholder - I'll implement the condition later, for now I want to get the other part right).

What is wrong with my code? From my understanding guard takes a conditional (True) and a function f. If the conditional is true it then gives pure f.

In my case,

pure = MaybeT . return . Just

So shouldn't my function f just return a State Stack Int?

Here is the full code, with my implementations of MaybeT and State:

import Control.Applicative (Alternative(..))
import Control.Monad (liftM, ap, guard)
import Control.Monad.Trans.Class (MonadTrans(lift))

main :: IO()
main = return ()

-- State Monad

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

instance Functor (State s) where
    fmap  = liftM

instance Applicative (State s) where
    pure a = MakeState $ \s -> (a, s)
    (<*>)  = ap

instance Monad (State s) where
    return a = MakeState $ \s -> (a, s)
    m >>= k  = MakeState $ \s -> let (x, s') = runState m s
                              in runState (k x) s'

get :: State s s
get = MakeState $ \s -> (s, s)

put :: s -> State s ()
put s = MakeState $ \_ -> ((), s)

modify :: (s -> s) -> State s ()
modify f = MakeState $ \s -> ((), f s)

-- MaybeT MonadTransformer

newtype MaybeT m a = MaybeT { runMaybeT :: m (Maybe a) }

instance Monad m => Functor (MaybeT m) where
    fmap a x = MaybeT $ do e <- runMaybeT x
                           return $ fmap a e

instance Monad m => Applicative (MaybeT m) where
    pure      = MaybeT . return . Just
    (<*>) a b = MaybeT $ do e <- runMaybeT a
                            f <- runMaybeT b
                            return $ e <*> f

instance Monad m => Monad (MaybeT m) where
    return  = pure
    a >>= b = MaybeT $ do aa <- runMaybeT a
                          maybe (return Nothing) (runMaybeT . b) aa

instance Monad m => Alternative (MaybeT m) where
  empty   = MaybeT $ return Nothing
  a <|> b = MaybeT $ do aa <- runMaybeT a
                        bb <- runMaybeT b
                        return $ aa <|> bb

instance MonadTrans MaybeT where
    -- "herwrappen" van het argument
    lift x = MaybeT $ do r <- x
                         return $ Just r

-- Stack Manipulation

type Stack = [Int]

-- plaats het argument bovenop de stack
push :: Int -> State Stack ()
push x = do r <- get
            put (x:r)
-- geef de grootte van de stack terug
size :: State Stack Int
size = do r <- get
          return $ length r

-- neem het eerste element van de stack, als het aanwezig is
-- (hint: hoogle naar `guard`)
pop :: MaybeT (State Stack) Int
pop = guard (True) (do (r:rs) <- get
                       put rs
                       return r)

Show source
| haskell   | monads   | monad-transformers   | state-monad   2016-12-05 12:12 3 Answers

Answers to Monad transformers: Implementation of a stack machine with MaybeT (State Stack) ( 3 )

  1. 2016-12-05 12:12

    First of all, you should understand if your stack is empty, your pattern r:rs <- get fails. But you write it in do-block, so the fail function will be called. It is implemented for Monad m => MaybeT m like this: fail _ = MaybeT (return Nothing). This means that if the pattern fails it returns Nothing. That what you want.

    So, you can do like this:

    pop :: MaybeT (State Stack) Int
    pop = do r:rs <- get
             put rs
             return r
  2. 2016-12-05 13:12

    guard doesn't take two arguments, it only takes a Bool argument.

    You also need to lift your state manipulations into MaybeT:

    pop :: MaybeT (State Stack) Int
    pop = do
      guard True
      (r:rs) <- lift get
      lift $ put rs
      return r
  3. 2016-12-05 13:12

    For the sake of comparison, here is a cruder implementation which doesn't rely neither on guard nor on fail:

    pop :: MaybeT (State Stack) Int
    pop = do
      stk <- lift get
      case stk of
        [] -> empty
        (r:rs) -> do
          lift (put rs)
          return r

    Producing empty when the stack is [] amounts to the same thing that using guard in the way you intend, or using fail to exploit a failed pattern match (as in freestyle's answer).

Leave a reply to - Monad transformers: Implementation of a stack machine with MaybeT (State Stack)

◀ Go back