[Haskell] type class instance selection & search

[Conal Elliott]

I keep running into situations in which I want more powerful search in
selecting type class instances.  One example I raised in June, in which all
of the following instances are useful.

> instance (Functor g, Functor f) => Functor (O g f) where
>   fmap h (O gf) = O (fmap (fmap h) gf)

> instance (Cofunctor g, Cofunctor f) => Functor (O g f) where
>   fmap h (O gf) = O (cofmap (cofmap h) gf)

> instance (Functor g, Cofunctor f) => Cofunctor (O g f) where
>   cofmap h (O gf) = O (fmap (cofmap h) gf)

> instance (Cofunctor g, Functor f) => Cofunctor (O g f) where
>   cofmap h (O gf) = O (cofmap (fmap h) gf)

My understanding is that this sort of instance collection doesn't work
together because instance selection is based only on the matching the head
of an instance declaration (part after the "=>").  I'm wondering why not use
the preconditions as well, via a Prolog-like, backward-chaining search for
much more flexible instance selection?  Going further, has anyone
investigated using Prolog as a model for instance selection?  Better yet,
how about LambdaProlog (
http://www.lix.polytechnique.fr/Labo/Dale.Miller/lProlog), which generalizes
from Horn clauses to (higher-order) hereditary Harrop formulas, including
(restricted but powerful) universals, implication, and existentials?  Once
search is in there, ambiguity can arise, but perhaps the compiler could
signal an error in that case (i.e., if the ambiguity is not eliminated by
further search pruning).

My motivation: I've been playing with a programming style in which my type
formulation leads to automatic construction of much of the code, thanks to
use of Functor, Applicative, Monoid, and type composition.  An example is
http://haskell.org/haskellwiki/Applicative_data-driven_programming, and I'm
trying now to do the same to create a much simpler implementation of Eros (
http://conal.net/papers/Eros).  I think this programming style is what Conor
was alluding to recently as "types don't just contain data, types explain
data" (http://article.gmane.org/gmane.comp.lang.haskell.cafe/26520).
(Conor: I hope you chime in.)  My hunch is that this programming style tends
to run up against the head-only instance matching mechanism and would work
much better with a more powerful means of selecting instances.

   - Conal
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell/attachments/20070731/143c1ee8/attachment.htm