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