Conal Elliott wrote:
The problem is that instance selection (in GHC at least) ignores the contexts... Is it plausible to improve instance selection to use contexts? I imagine doing so would require some kind of backtracking search.
Indeed the instance selection depends only on the types but not on their constraints. That is a feature of Haskell, and it is a useful feature (as shown in the HList paper). Still, as Jeff said, instance selection based on contexts and backtracking compile-time search are possible. For example, the article http://okmij.org/ftp/Haskell/poly2.txt says: We also show how to write typeclass instances with back-tracking: if one instance does not apply, the typechecker will chose the `next' instance -- in the precise meaning of `next'. The following article about controlling instance selection and resolving ambiguous overloading might also be helpful: http://okmij.org/ftp/Haskell/typecast.html#ambiguity-resolution