Haskell Monad Transformer Stack and Type Signatures

Question

I am attempting to create a stack of monad transformers and am having trouble getting the correct type signatures for my functions. (I'm still pretty new to Haskell)

The stack combines multiple StateT transformers since I have multiple states I need to keep track of (two of which could be tupled, but I'll get to that in a second) and a WriterT for logging.

Here's what I have so far:

module Pass1 where
import Control.Monad.Identity
import Control.Monad.State
import Control.Monad.Writer
import Data.Maybe
import qualified Data.Map as Map
import Types

data Msg = Error String
         | Warning String

type Pass1 a = WriterT [Msg] (StateT Int (StateT [Line] (StateT [Address] Identity))) a


runPass1 addrs instrs msgs = runIdentity (runStateT (runStateT (runStateT (runWriterT msgs) 1) instrs) addrs)


--popLine :: (MonadState s m) => m (Maybe s)
--popLine :: (Monad m) => StateT [Line] m (Maybe Line)
popLine :: (MonadState s m) => m (Maybe Line)
popLine = do
        ls <- get
        case ls of
          x:xs -> do
                    put xs
                    return $ Just x
          []   -> return Nothing


incLineNum :: (Num s, MonadState s m) => m ()
incLineNum = do
               ln <- get
               put $ ln + 1

curLineNum :: (MonadState s m) => m s
curLineNum = do
               ln <- get
               return ln

evalr = do l <- popLine
           --incLineNum
           return l

I would like the popLine to mess with the [Line] state and the xLineNum functions to affect the Int state. evalr is the computation which will be passed to runPass1.

Whenever I load the code I run into errors which are generally of the following variety:

Pass1.hs:23:14:
    No instance for (MonadState [t] m)
      arising from a use of `get' at Pass1.hs:23:14-16
    Possible fix: add an instance declaration for (MonadState [t] m)
    In a stmt of a 'do' expression: ls <- get
    In the expression:
        do ls <- get
           case ls of {
             x : xs -> do ...
             [] -> return Nothing }
    In the definition of `popLine':
        popLine = do ls <- get
                     case ls of {
                       x : xs -> ...
                       [] -> return Nothing }


Pass1.hs:22:0:
    Couldn't match expected type `s' against inferred type `[Line]'
      `s' is a rigid type variable bound by                        
          the type signature for `popLine' at Pass1.hs:21:23        
    When using functional dependencies to combine                  
      MonadState [Line] m,                                         
        arising from a use of `get' at Pass1.hs:23:14-16            
      MonadState s m,                                              
        arising from the type signature for `popLine'              
                     at Pass1.hs:(22,0)-(28,31)                     
    When generalising the type(s) for `popLine'         




Pass1.hs:23:14:
    Could not deduce (MonadState [Line] m)
      from the context (MonadState s m)   
      arising from a use of `get' at Pass1.hs:23:14-16
    Possible fix:                                    
      add (MonadState [Line] m) to the context of    
        the type signature for `popLine'             
      or add an instance declaration for (MonadState [Line] m)
    In a stmt of a 'do' expression: ls <- get
    In the expression:
        do ls <- get
           case ls of {
             x : xs -> do ...
             [] -> return Nothing }
    In the definition of `popLine':
        popLine = do ls <- get
                     case ls of {
                       x : xs -> ...
                       [] -> return Nothing }

None of the signatures seem to be correct, but popLine is the first function so it's the only one that immediately causes an error.

I try adding what it suggests in the type signature (eg: popLine :: (MonadState [Line] m) => ... but then it errors like so:

Pass1.hs:21:0:
    Non type-variable argument in the constraint: MonadState [Line] m
    (Use -XFlexibleContexts to permit this)                          
    In the type signature for `popLine':                             
      popLine :: (MonadState [Line] m) => m (Maybe Line)

I always seem to get this message whenever I try to do something that isn't a type variable. It seems to like (MonadState s m) ok and error on something else, but when I try it with a [a] instead of s it errors similar to the above. (Initially the [Line] and Int were tupled in a single state, but I was getting this error so I thought I'd try to put them in separate states).

GHC 6.10.4, Kubuntu

So, can anyone tell me what is going on and give an explanation / show me the right type signatures, or does anyone know of a good reference on this stuff (the only thing that has helped so far was "Monad Transformers Step by Step", but that just uses one aux state function and one StateT)?

Many Thanks in advance.

Edit
Here's the compiling code incorporating JFT's and Edward's suggestions:

{-# LANGUAGE GeneralizedNewtypeDeriving #-} -- needed for: deriving (Functor,Monad)
{-# LANGUAGE MultiParamTypeClasses #-}      -- needed for: MonadState instance
{-# LANGUAGE FlexibleContexts #-}           -- needed for: (MonadState PassState m) => ...

module Pass1 where
import Control.Monad.State
import Control.Monad.Writer
import Data.Maybe
import Types

type Lines     = [Line]
type Addresses = [Address]
type LineNum   = Int
type Messages  = [Msg]
data Msg = Error String
         | Warning String

data PassState = PassState { passLineNum :: LineNum
                           , passLines :: Lines
                           , passAddresses :: Addresses
                           }

newtype Pass1 a = Pass1 { unPass1 :: WriterT Messages (State PassState) a
                        }
                        deriving (Functor,Monad)

instance MonadState PassState Pass1 where
        get   = Pass1 . lift $ get
        put s = Pass1 . lift $ put s



runPass1 :: PassState -> Pass1 a -> ((a, Messages), PassState)
runPass1 state = flip runState state .
                 runWriterT          .
                 unPass1


curLineNum :: (MonadState PassState m) => m LineNum
curLineNum = do
               state <- get
               return $ passLineNum state


nextLine :: (MonadState PassState m) => m (Maybe Line)
nextLine = do
             state <- get
             let c = passLineNum state
             let l = passLines state
             case l of
               x:xs -> do
                         put state { passLines = xs, passLineNum = (c+1) }
                         return $ Just x
               _ -> return Nothing



evalr :: Pass1 (Maybe Line,LineNum)
evalr = do
          l <- nextLine
          c <- curLineNum
          --tell $ Warning "hello"
          return (l,c)

I combined incLineNum and popLine into nextLine I still need to get the Writer monad portion to work, but think I know where to go from here. Thanks, guys.

Answer 1

There was many issues with your code snippet. I fixed your snippet adding explanation as to what was broken and added some style advice if you care.

module Pass1_JFT where
import Control.Monad.Identity
import Control.Monad.State
import Control.Monad.Writer
import Data.Maybe
import qualified Data.Map as Map

{- replacing your import Types with simple definitions -}

--import Types
type Line       = String
type Address    = String
type LineNumber = Int

{- Not part of your question but my 2 cents here... Say that you want to changes the collection for your states if you don't use a type alias you'll have to hunt everwhere you used it. Instead just change these definitions if required -}

type Lines     = [Line]
type Addresses = [Address]
type Messages  = [Msg]


data Msg = Error String
         | Warning String

{- What is that Int in StateT Int? Name it easier to read, reason about and to change. Declarative FTW let's use LineNumber instead -}

--type Pass1 a = WriterT [Msg] (StateT Int (StateT [Line] (StateT [Address] Identity))) a

{- Let's use a "real" type so instances can be derived. Since Pass1 is not a monad transfer i.e. not defined as Pass1 m a, no point using StateT for the deepest StateT i.e. StateT [Address] Identity so let's just use a State [Address] -}

newtype Pass1 a = Pass1 {
    unPass1 :: WriterT Messages (StateT LineNumber (StateT Lines (State Addresses))) a
                        }
                        deriving (Functor,Monad)

--runIdentity (runStateT (runStateT (runStateT (runWriterT msgs) 1) instrs) addrs)

{- Let's peel that stack from the outermost (lefmost in the declaration) up to the innermost was Identity in your original declaration. Note that runWriterT does NOT take a starting state... The first parameter for runStateT (and runState) is not the initial state but the monad... so let's flip! -}

runPass1' :: Addresses -> Lines -> Messages -> Pass1 a ->  ((((a, Messages), LineNumber), Lines), Addresses)
runPass1' addrs instrs msgs = flip runState addrs   .
                              flip runStateT instrs .
                              flip runStateT 1      .
                              runWriterT            . -- then get process the WriterT (the second outermost)
                              unPass1                 -- let's peel the outside Pass1

{- now that last function does NOT do what you want since you want to provide an initial log to append to with the WriterT. Since it is a monad transformer we'll do some trick here -}

-- I keep the runStateT convention for the order of the arguments: Monad then state
runWriterT' :: (Monad m,Monoid w) => WriterT w m a -> w -> m (a,w)
runWriterT' writer log = do
    (result,log') <- runWriterT writer
    -- let's use the monoid generic append in case you change container...
    return (result,log `mappend` log')

runPass1 :: Addresses -> Lines -> Messages -> Pass1 a ->  ((((a, Messages), LineNumber), Lines), Addresses)
runPass1 addrs instrs msgs = flip runState addrs   .
                             flip runStateT instrs .
                             flip runStateT 1      .
                             flip runWriterT' msgs . -- then get process the WriterT (the second outermost)
                             unPass1                 -- let's peel the outside Pass1

{- Do you intend to call popLine directly from a Pass1 stack? If so you need to "teach" Pass1 to be a "MonadState Lines" To do so let's derive Pass1 (that's why we declared it with newtype!) -}

instance MonadState Lines Pass1 where
    -- we need to dig inside the stack and "lift" the proper get
    get   = Pass1 . lift . lift $ get
    put s = Pass1 . lift . lift $ put s

{- Better keep thing generic but we now could have written: popLine :: Pass1 (Maybe Line) -}

popLine :: (MonadState Lines m) => m (Maybe Line)
popLine = do
        ls <- get
        case ls of
          x:xs -> do
                    put xs
                    return $ Just x
          []   -> return Nothing

{- Ok now I get the Int => LineNumber.... we could make Pass1 and instance of MonadState LineNumber but LineNumber should not be messed with so instead I'd code the incLine directly and would provide a MonadReader instance for consulation if required

check ":t incLineNum and :t curLineNum"

-}

incLineNum = Pass1 . lift $ modify (+1)

curLineNum = Pass1 $ lift get

evalr = do l <- popLine
           incLineNum
           return l

There it is a long winded response but monad and monad stack as you see are challenging at first. I fixed the code but I encourage you to play and inspect the types of the various functions to understand what is going on and to compare against your original. Haskell's type inference means that usually type annotations are superfluous (unless to remove ambiguity). In general the type we'd give to function is less generic that was is infer so it is better not to type annotate. Type annotation is definitively a good debugging technique though ;)

Cheers

P.S. Real World Haskell chapter on Monad Transformer is excellent: http://book.realworldhaskell.org/read/monad-transformers.html

Answer 2

In general you'll find that code winds up much clearer using one StateT with a larger composite structure for all of the bits of state that you need. One good reason is that when you come up with a piece of state you forgot you can always grow the structure by one field, and you can use the record sugar to write out single field updates or turn to something like the fclabels or data-accessor packages to manipulate state.

data PassState = PassState { passLine :: Int, passLines :: [Line] }

popLine :: MonadState PassState m => m (Maybe Line).   
popLine = do
   state <- get
   case passLines state of
      x:xs -> do 
         put state { passLines = xs }
         return (Just x)
      _ -> return Nothing