Using Maybe with State Monad

Question

I'm trying to implement a FIFO Queue in Haskell with push/pop/peek operations, and this is what I got so far.

data Queue a = Queue { 
  inbox :: [a], 
  outbox :: [a] 
} deriving (Eq, Show)

push :: a -> Queue a -> Queue a
push e (Queue inb out) = Queue (e:inb) out

pop :: Queue a -> (Maybe a, Queue a)
pop q = 
  case top of
    Nothing   -> (top, emptyQueue)
    Just elem -> (Just elem, poppedQueue)
    where
      (top, q') = peek q
      poppedQueue = Queue (inbox q') (tail $ outbox q')

peek :: Queue a -> (Maybe a, Queue a)
peek q@(Queue [] [])    = (Nothing, emptyQueue)
peek q@(Queue inb [])   = peek $ Queue [] (reverse inb)
peek q@(Queue _ outb)   = (Just $ head outb, q)

emptyQueue = Queue [] []

So the above works, and I can push/pop/peek at my Queue. As you see, I wrapped up the return type in a Maybe, so that I get a Nothing if I pop an empty queue or peek at an empty queue, and a Just element otherwise.

So I also thought I could use the State monad to easily chain operations. I proceeded as follows:

type QueueState a = State (Queue a)

pushQueue :: a -> QueueState a ()
pushQueue e = state $ \q -> ((),push e q)

popQueue :: QueueState a (Maybe a)
popQueue = state $ \q -> pop q

Allright, so that seems to work. I can do:

runState (pushQueue 2 >> pushQueue 3 >> popQueue >> pushQueue 1 >> popQueue) emptyQueue

and get back (Just 3,Queue {inbox = [1], outbox = []}), which is what I wanted. But I can't do something like:

runState (pushQueue 2 >> popQueue >>= pushQueue) emptyQueue

which results in an:

Occurs check: cannot construct the infinite type: a0 = Maybe a0
Expected type: Maybe a0
               -> StateT (Queue a0) Data.Functor.Identity.Identity ()
  Actual type: Maybe a0 -> QueueState (Maybe a0) ()

Now I think I understand why that this, but I can't figure out how to make it do what I want. That is, a chaining using >>= from a pop should be able to feed into a push. I'm thinking I might need to use a StateT transformer, but I don't really understand them yet, so I'm looking for help on how do implement that functionality. Or do I need to do this in a completely different way? Thanks.

I'm not familiar enough with monad transformers to really answer, but it sounds like a task for either the StateT or MaybeT transformer. Kleisli arrows might be useful too. — Jeremy List

Thomas M. DuBuisson Thomas M. DuBuisson · Accepted Answer · 2013-11-20T02:18:15

It is because the compiler can not construct an infinite type ;-).

More helpfully, consider the line:

runState (pushQueue 2 >> popQueue >>= pushQueue) emptyQueue

What is the type of popQueue? QueueState Int (Maybe Int). (think m (Maybe Int))

What is the type of >>= pushQueue? QueueState Int Int -> QueueState Int () (think m Int -> m ())

So the typechecker tries to unify the types Maybe a and a - the only way those types unify is if a if an infinite type of Maybe (Maybe (Maybe (Maybe ....

The solution is to do something to handle the Nothing case. For example, return () or push depending on the Maybe.

runState (pushQueue 2 >> popQueue >>= maybe (return ()) pushQueue) emptyQueue

Using Maybe with State Monad

1 Answers