[Haskell] Re: type class instance selection & search

[Conal Elliott]

Here are some other instances that could work with backward chaining:

\begin{code}
instance Monad m => Applicative m where
   pure  = return
   (<*>) = ap

 instance (Applicative f, Monoid a) => Monoid (f a) where
  mempty  = pure mempty
  mappend = liftA2 mappend

instance (Applicative f, Num a) => Num (f a) where
  (+)         = liftA2 (+)
  fromInteger = pure . fromInteger
  -- etc
\end{code}

Currently, I place such instance declarations in comments as boilerplate to
be instantiated manually.  - Conal


On 7/31/07, Conal Elliott <conal at conal.net> wrote:
>
> 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/1b14327c/attachment.htm