What does "Couldn't match type when using functional dependencies to combine" error mean?

Question

I'm currently writing a small compiler for a course I'm taking. So I started writing this monad transformer to handle the typechecking, but got a very cryptic type error. Something involving functional dependencies, which I don't really know very well. A small excerpt from the program that can reproduce the error:

import Control.Monad.RWS.Lazy
import qualified Data.Map as M
import Control.Applicative

--Placeholders for other data types.
data TypeError = TypeError
data Ident = Ident String
data Type = Type

type Typer a = RWS FunctionTable [TypeError] IdentTable a

type FunctionTable = M.Map Ident Type

type IdentTable = [M.Map Ident Type]

emptyIdents :: IdentTable
emptyIdents = []

getIdent :: Ident -> Typer (Maybe Type)
getIdent id = getIdent' id <$> get

getIdent' :: Ident -> IdentTable -> Maybe Type
getIdent' _ [] = Nothing
getIdent' id (x:xs) =
  case M.lookup id x of
    Just t -> Just t
    Nothing -> getIdent' id xs

putIdent :: Ident -> Type -> Typer ()
putIdent id ty = modify $ \xs -> case xs of
  [] -> [M.singleton id ty]
  (x:xs) -> (M.insert id ty x) : xs

scopeEnter :: Typer ()
scopeEnter = modify $ \ids -> emptyIdents : ids

scopeExit :: Typer ()
scopeExit = modify tail

And the actual message:

[1 of 1] Compiling Main             ( ErrorExample.hs, interpreted )

ErrorExample.hs:30:22:
    Couldn't match type `M.Map Ident Type' with `Type'
    When using functional dependencies to combine
      MonadState
        [[M.Map Ident Type]]
        (RWST
           (M.Map Ident Type)
           [TypeError]
           [M.Map Ident Type]
           transformers-0.2.2.0:Data.Functor.Identity.Identity),
        arising from a use of `modify' at ErrorExample.hs:35:18-23
      MonadState
        [M.Map Ident Type]
        (RWST
           (M.Map Ident Type)
           [TypeError]
           [M.Map Ident Type]
           transformers-0.2.2.0:Data.Functor.Identity.Identity),
        arising from a use of `modify' at ErrorExample.hs:30:22-27
    In the expression: modify
    In the expression:
      modify
      $ \ xs
          -> case xs of {
               [] -> [...]
               (x : xs) -> (M.insert id ty x) : xs }

ErrorExample.hs:30:22:
    Couldn't match type `[]' with `M.Map Ident'
    When using functional dependencies to combine
      MonadState
        [[M.Map Ident Type]]
        (RWST
           (M.Map Ident Type)
           [TypeError]
           [M.Map Ident Type]
           transformers-0.2.2.0:Data.Functor.Identity.Identity),
        arising from a use of `modify' at ErrorExample.hs:35:18-23
      MonadState
        [M.Map Ident Type]
        (RWST
           (M.Map Ident Type)
           [TypeError]
           [M.Map Ident Type]
           transformers-0.2.2.0:Data.Functor.Identity.Identity),
        arising from a use of `modify' at ErrorExample.hs:30:22-27
    In the expression: modify
    In the expression:
      modify
      $ \ xs
          -> case xs of {
               [] -> [...]
               (x : xs) -> (M.insert id ty x) : xs }

ErrorExample.hs:35:18:
    Couldn't match type `Type' with `M.Map Ident Type'
    When using functional dependencies to combine
      MonadState s (RWST r w s m),
        arising from the dependency `m -> s'
        in the instance declaration in `Control.Monad.State.Class'
      MonadState
        [[M.Map Ident Type]]
        (RWST
           (M.Map Ident Type)
           [TypeError]
           [M.Map Ident Type]
           transformers-0.2.2.0:Data.Functor.Identity.Identity),
        arising from a use of `modify' at ErrorExample.hs:35:18-23
    In the expression: modify
    In the expression: modify $ \ ids -> emptyIdents : ids

ErrorExample.hs:35:18:
    Couldn't match type `M.Map Ident' with `[]'
    When using functional dependencies to combine
      MonadState s (RWST r w s m),
        arising from the dependency `m -> s'
        in the instance declaration in `Control.Monad.State.Class'
      MonadState
        [[M.Map Ident Type]]
        (RWST
           (M.Map Ident Type)
           [TypeError]
           [M.Map Ident Type]
           transformers-0.2.2.0:Data.Functor.Identity.Identity),
        arising from a use of `modify' at ErrorExample.hs:35:18-23
    In the expression: modify
    In the expression: modify $ \ ids -> emptyIdents : ids
Failed, modules loaded: none.
Leaving GHCi.

Answer 1

It's a very bad error message. The cause is due to a type mismatch in State. Your code is trying to mix [M.Map Ident Type] and [[M.Map Ident Type]].

If you manually inline the emptyIdents call into scopeEnter it looks like this:

scopeEnter :: Typer ()
scopeEnter = modify $ \ids -> [] : ids

... which doesn't make much sense for [M.Map Ident Type]. Compare that to the version that does typecheck:

scopeEnter :: Typer ()
scopeEnter = modify $ \ids -> M.empty : ids