[Haskell] Re: type class does not compile

[oleg at pobox.com]

Ben Yu wrote:

> class Rule r u u' m where
>   apply :: r -> u -> m u'
>
> data And = And
>
> data Bin a b o = Bin a b o
>
> instance (Monad m, Rule r1 u u' m, Rule r2 u' u'' m) => 
>          Rule (Bin r1 r2 And) u u'' m where
>   apply (Bin r1 r2 _) u = apply r1 u >>= apply r2
>
> Ghc complains about "Could not deduce (Rule r1 u u'1 m, Rule r2 u'1 u''
> m)", but it is obviously same as the constraint I gave in the instance
> declaration.

This is like the famous show . read problem. Here, 'apply r1 u'
produces the value of a type `m v' for _some_ v. and 'apply r2'
consumes this value. There is no way for the compiler to figure out
what this 'v' is. You specified 'Rule r1 u u' m' as a
constraint. However, there is nothing that guarantees that your u' in
the constraint is the same as v that is needed to resolve the
overloading. So, we need either a functional dependency, or a resort
to nifty local type variables. The example of the latter is

> instance (Monad m, Rule r1 u u' m, Rule r2 u' u'' m) => 
>          Rule (Bin r1 r2 And) u u'' m where
>   apply (Bin r1 r2 _) u = ((apply r1 u)::m u') >>= apply r2

which makes your code compile.

For more detail, please see:
http://www.haskell.org/pipermail/haskell/2003-September/012782.html
http://www.haskell.org/pipermail/haskell/2003-October/012783.html