Here are some other instances that could work with backward chaining:<br><br>
\begin{code}<br><span style="font-family: courier new,monospace;">
instance Monad m =&gt; Applicative m where</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">
&nbsp; pure&nbsp; = return</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">
&nbsp; (&lt;*&gt;) = ap</span><br style="font-family: courier new,monospace;">

<br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;"></span><span style="font-family: courier new,monospace;">
instance (Applicative f, Monoid a) =&gt; Monoid (f a) where </span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">
&nbsp; mempty&nbsp; = pure mempty</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">
&nbsp; mappend = liftA2 mappend</span><br style="font-family: courier new,monospace;">
<br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;"></span><span style="font-family: courier new,monospace;">instance (Applicative f, Num a) =&gt; Num (f a) where</span><br style="font-family: courier new,monospace;">
<span style="font-family: courier new,monospace;">
&nbsp; (+)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = liftA2 (+)</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">
&nbsp; fromInteger = pure . fromInteger</span><br style="font-family: courier new,monospace;"><span style="font-family: courier new,monospace;">
&nbsp; -- etc</span><br>
\end{code}<br><br>Currently, I place such instance declarations in comments as boilerplate to be instantiated manually.&nbsp; - Conal<br><br><br><div><span class="gmail_quote">On 7/31/07, <b class="gmail_sendername">Conal Elliott
</b> &lt;<a href="mailto:conal@conal.net">conal@conal.net</a>&gt; wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">I keep running into situations in which I want more powerful search in selecting type class instances.&nbsp; One example I raised in June, in which all of the following instances are useful.
<br><br>&gt; instance (Functor g, Functor f) =&gt; Functor (O g f) where
<br>&gt;&nbsp;&nbsp; fmap h (O gf) = O (fmap (fmap h) gf)<br><br>&gt; instance (Cofunctor g, Cofunctor f) =&gt; Functor (O g f) where<br>&gt;&nbsp;&nbsp; fmap h (O gf) = O (cofmap (cofmap h) gf)<br><br>&gt; instance (Functor g, Cofunctor f) =&gt; Cofunctor (O g f) where
<br>&gt;&nbsp;&nbsp; cofmap h (O gf) = O (fmap (cofmap h) gf)<br><br>&gt; instance (Cofunctor g, Functor f) =&gt; Cofunctor (O g f) where<br>&gt;&nbsp;&nbsp; cofmap h (O gf) = O (cofmap (fmap h) gf)<br><br>My understanding is that this sort of instance collection doesn&#39;t work together because instance selection is based only on the matching the head of an instance declaration (part after the &quot;=&gt;&quot;).&nbsp; I&#39;m wondering why not use the preconditions as well, via a Prolog-like, backward-chaining search for much more flexible instance selection?&nbsp; Going further, has anyone investigated using Prolog as a model for instance selection?&nbsp; Better yet, how about LambdaProlog (
<a href="http://www.lix.polytechnique.fr/Labo/Dale.Miller/lProlog" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">http://www.lix.polytechnique.fr/Labo/Dale.Miller/lProlog</a>), which generalizes from Horn clauses to (higher-order) hereditary Harrop formulas, including (restricted but powerful) universals, implication, and existentials?&nbsp; 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).<br><br>My motivation: I&#39;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.&nbsp; An example is 
<a href="http://haskell.org/haskellwiki/Applicative_data-driven_programming" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">http://haskell.org/haskellwiki/Applicative_data-driven_programming</a>, and I&#39;m trying now to do the same to create a much simpler implementation of Eros (
<a href="http://conal.net/papers/Eros" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">http://conal.net/papers/Eros</a>).&nbsp; I think this programming style is what Conor was alluding to recently as &quot;types don&#39;t just contain data, types explain data&quot; (
<a href="http://article.gmane.org/gmane.comp.lang.haskell.cafe/26520" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">
http://article.gmane.org/gmane.comp.lang.haskell.cafe/26520</a>).&nbsp; (Conor: I hope you chime in.)&nbsp; 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.
<br><span class="sg"><br>&nbsp;&nbsp; - Conal<br>
</span></blockquote></div><br>