TypeFamilies vs. FunctionalDependencies & type-level recursion

Simon Peyton-Jones simonpj at microsoft.com
Wed Jun 15 12:36:46 CEST 2011


| Suppose you want to define an instance of MonadState for another monad like 
| MaybeT.  You would need to write code like this:
|  
|  	instance (MonadState s m) => MonadState s (MaybeT m) where
|  	    get = lift get
|  	    put = lift . put
|  
|  This code fails the coverage condition, because class argument
|  (MaybeT m) does not contain the type variable s. 

The issue doesn't even arise with type families:

	class MonadState m where
	  type State m :: *

	instance MonadState m => MonadState (MaybeT m) where
	  type State (MaybeT m) = State m

So examples that fail the coverage condition in fundeps, but (as you argue) are ok because the context expresses the dependency, are sometimes just fine with type families.

|  Now if, in addition to lifting the coverage condition, you add
|  OverlappingInstances, you can do something even better--you can write
|  one single recursive definition of MonadState that works for all
|  MonadTrans types (along with a base case for StateT).  This is far
|  preferable to the N^2 boilerplate functions currently required by N
|  monad transformers:
|  
|  	instance (Monad m) => MonadState s (StateT s m) where
|  	    get = StateT $ \s -> return (s, s)
|  
|  	instance (Monad (t m), MonadTrans t, MonadState s m) =>
|              MonadState s (t m) where
|  	        get = lift get
|  	        put = lift . put

Why do you need the first instance?  Isn't the second sufficient for (StateT s m) as well?

Simon



More information about the Haskell-prime mailing list