<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">

<head>
<meta http-equiv=Content-Type content="text/html; charset=us-ascii">
<meta name=Generator content="Microsoft Word 12 (filtered medium)">
<style>
<!--
 /* Font Definitions */
 @font-face
        {font-family:Calibri;
        panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
        {font-family:Tahoma;
        panose-1:2 11 6 4 3 5 4 4 2 4;}
 /* Style Definitions */
 p.MsoNormal, li.MsoNormal, div.MsoNormal
        {margin:0cm;
        margin-bottom:.0001pt;
        font-size:12.0pt;
        font-family:"Times New Roman","serif";}
a:link, span.MsoHyperlink
        {mso-style-priority:99;
        color:blue;
        text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
        {mso-style-priority:99;
        color:purple;
        text-decoration:underline;}
span.EmailStyle17
        {mso-style-type:personal-reply;
        font-family:"Calibri","sans-serif";
        color:#1F497D;}
.MsoChpDefault
        {mso-style-type:export-only;}
@page Section1
        {size:612.0pt 792.0pt;
        margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.Section1
        {page:Section1;}
-->
</style>
<!--[if gte mso 9]><xml>
 <o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
 <o:shapelayout v:ext="edit">
  <o:idmap v:ext="edit" data="1" />
 </o:shapelayout></xml><![endif]-->
</head>

<body lang=EN-GB link=blue vlink=purple>

<div class=Section1>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Conal<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>It certainly makes sense to do backward chaining, but I don&#8217;t
know any Haskell implementation that&#8217;s tried it.&nbsp; It&#8217;d be more
complicated in the presence of functional dependencies, since we must &#8220;undo&#8221;
any unifications done as a result of discarded searches, much like the &#8220;trail&#8221;
in a Prolog implementation.<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>To be honest I can&#8217;t see myself trying this anytime
soon.&nbsp; Because of the unification part, it&#8217;d be a significant
structural change.&nbsp; And one would need to dig into the theory to make sure
that the algorithm was both sound and complete (finds all solutions).<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Simon<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><o:p>&nbsp;</o:p></span></p>

<div style='border:none;border-left:solid blue 1.5pt;padding:0cm 0cm 0cm 4.0pt'>

<div>

<div style='border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0cm 0cm 0cm'>

<p class=MsoNormal><b><span lang=EN-US style='font-size:10.0pt;font-family:
"Tahoma","sans-serif"'>From:</span></b><span lang=EN-US style='font-size:10.0pt;
font-family:"Tahoma","sans-serif"'> haskell-bounces@haskell.org
[mailto:haskell-bounces@haskell.org] <b>On Behalf Of </b>Conal Elliott<br>
<b>Sent:</b> 31 July 2007 20:09<br>
<b>To:</b> haskell@haskell.org<br>
<b>Subject:</b> [Haskell] type class instance selection &amp; search<o:p></o:p></span></p>

</div>

</div>

<p class=MsoNormal><o:p>&nbsp;</o:p></p>

<p class=MsoNormal>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'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'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">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>
<o:p></o:p></p>

</div>

</div>

</body>

</html>