<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:Wingdings;
        panose-1:5 0 0 0 0 0 0 0 0 0;}
@font-face
        {font-family:"Cambria Math";
        panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
        {font-family:Calibri;
        panose-1:2 15 5 2 2 2 4 3 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;}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
        {mso-style-priority:34;
        margin-top:0cm;
        margin-right:0cm;
        margin-bottom:0cm;
        margin-left:36.0pt;
        margin-bottom:.0001pt;
        font-size:12.0pt;
        font-family:"Times New Roman","serif";}
span.EmailStyle17
        {mso-style-type:personal-compose;
        font-family:"Calibri","sans-serif";
        color:windowtext;}
.MsoChpDefault
        {mso-style-type:export-only;}
@page WordSection1
        {size:612.0pt 792.0pt;
        margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
        {page:WordSection1;}
 /* List Definitions */
 @list l0
        {mso-list-id:215361242;
        mso-list-type:hybrid;
        mso-list-template-ids:1951290878 -1476893524 134807555 134807557 134807553 134807555 134807557 134807553 134807555 134807557;}
@list l0:level1
        {mso-level-start-at:3;
        mso-level-number-format:bullet;
        mso-level-text:\F06E;
        mso-level-tab-stop:none;
        mso-level-number-position:left;
        margin-left:20.4pt;
        text-indent:-18.0pt;
        font-family:Wingdings;
        mso-fareast-font-family:Calibri;
        mso-bidi-font-family:"Times New Roman";}
@list l1
        {mso-list-id:264507450;
        mso-list-type:hybrid;
        mso-list-template-ids:1382838248 -1902344770 134807555 134807557 134807553 134807555 134807557 134807553 134807555 134807557;}
@list l1:level1
        {mso-level-start-at:3;
        mso-level-number-format:bullet;
        mso-level-text:\F06E;
        mso-level-tab-stop:none;
        mso-level-number-position:left;
        margin-left:22.8pt;
        text-indent:-18.0pt;
        font-family:Wingdings;
        mso-fareast-font-family:Calibri;
        mso-bidi-font-family:"Times New Roman";}
@list l2
        {mso-list-id:928931316;
        mso-list-type:hybrid;
        mso-list-template-ids:-1459083692 986896848 134807555 134807557 134807553 134807555 134807557 134807553 134807555 134807557;}
@list l2:level1
        {mso-level-start-at:3;
        mso-level-number-format:bullet;
        mso-level-text:\F06E;
        mso-level-tab-stop:none;
        mso-level-number-position:left;
        margin-left:22.8pt;
        text-indent:-18.0pt;
        font-family:Wingdings;
        mso-fareast-font-family:Calibri;
        mso-bidi-font-family:"Times New Roman";}
@list l3
        {mso-list-id:1365642515;
        mso-list-type:hybrid;
        mso-list-template-ids:-378912800 -1349322164 134807555 134807557 134807553 134807555 134807557 134807553 134807555 134807557;}
@list l3:level1
        {mso-level-start-at:3;
        mso-level-number-format:bullet;
        mso-level-text:\F06E;
        mso-level-tab-stop:none;
        mso-level-number-position:left;
        margin-left:20.4pt;
        text-indent:-18.0pt;
        font-family:Wingdings;
        mso-fareast-font-family:Calibri;
        mso-bidi-font-family:"Times New Roman";}
@list l4
        {mso-list-id:2096243981;
        mso-list-type:hybrid;
        mso-list-template-ids:1154107692 134807553 134807555 134807557 134807553 134807555 134807557 134807553 134807555 134807557;}
@list l4:level1
        {mso-level-number-format:bullet;
        mso-level-text:\F0B7;
        mso-level-tab-stop:none;
        mso-level-number-position:left;
        text-indent:-18.0pt;
        font-family:Symbol;}
ol
        {margin-bottom:0cm;}
ul
        {margin-bottom:0cm;}
-->
</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=WordSection1>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>Oleg points out, and Martin also mentions, that functional
dependencies appear to interact OK with overlapping instances, but type
families do not. I this impression is mistaken, and I&#8217;ll try to explain
why in this message, in the hope of exposing any flaws in my reasoning.<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'>We can&#8217;t permit overlap for type families because it is <b>unsound
</b>to do so (ie you can break &#8220;well typed programs don&#8217;t go wrong&#8221;).
But if it&#8217;s unsound for type families, it would not be surprising if it
was unsound for fundeps too. &nbsp;(I don&#8217;t think anyone has done a
soundness proof for fundeps + local constraints + overlapping instances, have
they?)&nbsp; And indeed I think it is.&nbsp; <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'>So the short summary of this message is: <b>if it works for
fundeps it works for type families, and vice versa</b>.&nbsp; (NB this
equivalence is not true about GHC&#8217;s current implementation, however.&nbsp;&nbsp;
GHC doesn&#8217;t support the combination of fundeps and local constraints at
all.)<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'>Such an equivalence doesn&#8217;t argue against fundeps; I&#8217;m
only suggesting the that the two really are very closely equivalent.&nbsp;&nbsp;
I much prefer type families from a programming-style point of view, but that&#8217;s
a subjective opinion.<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>

<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'>Imagine a system &#8220;FDL&#8221; that has functional dependencies
and local type constraints. &nbsp;The big deal about this is that you get to exploit
type equalities in *<b>given</b>* constraints.&nbsp; Consider Oleg&#8217;s
example, cut down a bit:<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 style='text-indent:36.0pt'><span style='font-size:11.0pt;
font-family:"Calibri","sans-serif";color:#1F497D'>class C a b | a -&gt; b<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:36.0pt'><span style='font-size:11.0pt;
font-family:"Calibri","sans-serif";color:#1F497D'>instance C Int Bool<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:36.0pt'><span style='font-size:11.0pt;
font-family:"Calibri","sans-serif";color:#1F497D'>newtype N2 a = N2 (forall b.
C a b =&gt; b)<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 style='text-indent:36.0pt'><span style='font-size:11.0pt;
font-family:"Calibri","sans-serif";color:#1F497D'>t2 :: N2 Int<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:36.0pt'><span style='font-size:11.0pt;
font-family:"Calibri","sans-serif";color:#1F497D'>t2 = N2 True<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'>We end up type-checking (True :: forall b. C Int b =&gt;
b).&nbsp;&nbsp; From the functional dependency we know that (b~Bool), so the
function should typecheck.&nbsp; GHC rejects this program; FDL would not.<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'>But making use of these extra equalities in &#8220;given&#8221;
constraints is quite tricky.&nbsp; To see why look first at Example 1: &nbsp;<o:p></o:p></span></p>

<div style='mso-element:para-border-div;border:none;border-bottom:double windowtext 2.25pt;
padding:0cm 0cm 1.0pt 0cm'>

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

</div>

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

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>&nbsp;&nbsp; class C a b | a -&gt; b<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'>&nbsp;&nbsp; data T a where<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>&nbsp;&nbsp;&nbsp;&nbsp; MkT :: C a b =&gt; b -&gt; T a<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'><o:p>&nbsp;</o:p></span></p>

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

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

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

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

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>&nbsp; f c = MkT c<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><b><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>module</span></b><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'> M2 where<o:p></o:p></span></p>

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

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

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

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>&nbsp; g (MkT x) = x<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><b><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>module</span></b><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'> Bad where<o:p></o:p></span></p>

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

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

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

<div style='mso-element:para-border-div;border:none;border-bottom:double windowtext 2.25pt;
padding:0cm 0cm 1.0pt 0cm'>

<p class=MsoNormal style='border:none;padding:0cm'><span style='font-size:11.0pt;
font-family:"Calibri","sans-serif";color:#1F497D'>&nbsp; bad = g . f<o:p></o:p></span></p>

</div>

<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'>This program is unsound: it lets you cast an Int to a Bool;
result is a seg-fault. <o:p></o:p></span></p>

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

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>You may say that the problem is the inconsistent functional
dependencies in M1 and M2.&nbsp; But GHC won&#8217;t spot that.&nbsp; For type
families, to avoid this we &#8220;<b>eagerly</b>&#8221; check for conflicts in
type-family instances.&nbsp; In this case the conflict would be reported when
compiling module Bad, because that is the first time when both instances are
visible together.<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'>So any FDL system should also make this eager check for
conflicts.<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'>What about overlap?&nbsp; Here&#8217;s Example 2: <o:p></o:p></span></p>

<div style='mso-element:para-border-div;border:none;border-bottom:double windowtext 2.25pt;
padding:0cm 0cm 1.0pt 0cm'>

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

</div>

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

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

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

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

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

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>&nbsp; instance C a [a]&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; --
Instance 2<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'>&nbsp; f :: Char -&gt; T Int<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>&nbsp; f c = MkT c&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; --
Uses Instance 1<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'>&nbsp; g :: T a -&gt; a<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>&nbsp; g (MkT x) = x&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; --
Uses Instance 2<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'>&nbsp; bad :: Char -&gt; Int<o:p></o:p></span></p>

<div style='mso-element:para-border-div;border:none;border-bottom:double windowtext 2.25pt;
padding:0cm 0cm 1.0pt 0cm'>

<p class=MsoNormal style='border:none;padding:0cm'><span style='font-size:11.0pt;
font-family:"Calibri","sans-serif";color:#1F497D'>&nbsp; bad = g . f<o:p></o:p></span></p>

</div>

<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'>Again, a seg fault if it typechecks.&nbsp; But will it?&nbsp; When
typechecking &#8216;g&#8217;, we get a constraint (C a ?), where &#8216;a&#8217;
is a skolem constant.&nbsp; Without IncoherentInstances GHC would reject the
program on the grounds that it does not know what instance to choose.&nbsp; But
*<b>with</b>* IncoherentInstances it would probably go through, which is
unsound.&nbsp; So IncoherentInstances has moved from causing varying dynamic
behaviour to causing seg faults.<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'>Very well, so FDL must get rid of IncoherentInstances altogether,
at least for classes that have functional dependencies (or that have superclasses
that do).&nbsp;&nbsp; <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'>But at the moment GHC makes an exception for *<b>existentials</b>*.&nbsp;
Consider Example 3:<o:p></o:p></span></p>

<div style='mso-element:para-border-div;border:none;border-bottom:double windowtext 2.25pt;
padding:0cm 0cm 1.0pt 0cm'>

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

</div>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>&nbsp; class C a b | a -&gt; b<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'>&nbsp;&nbsp;-- Overlapping instances<o:p></o:p></span></p>

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

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>&nbsp; instance C a [a]&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; --
Instance 2<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'>&nbsp; data T where<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>&nbsp;&nbsp;&nbsp; MkT :: C a b =&gt; a -&gt; b -&gt; T<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'>&nbsp; f :: Bool -&gt; T<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>&nbsp; f x = MkT (3::Int) x&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; --
Uses Instance 1<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'>&nbsp; g :: T -&gt; T<o:p></o:p></span></p>

<div style='mso-element:para-border-div;border:none;border-bottom:double windowtext 2.25pt;
padding:0cm 0cm 1.0pt 0cm'>

<p class=MsoNormal style='border:none;padding:0cm'><span style='font-size:11.0pt;
font-family:"Calibri","sans-serif";color:#1F497D'>&nbsp; g (MkT n x) = MkT n
(reverse x)&nbsp;&nbsp; -- Uses Instance 2<o:p></o:p></span></p>

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

<p class=MsoNormal style='border:none;padding:0cm'><span style='font-size:11.0pt;
font-family:"Calibri","sans-serif";color:#1F497D'>&nbsp; bad :: Bool -&gt; T<o:p></o:p></span></p>

<p class=MsoNormal style='border:none;padding:0cm'><span style='font-size:11.0pt;
font-family:"Calibri","sans-serif";color:#1F497D'>&nbsp; bad = g . f<o:p></o:p></span></p>

</div>

<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'>In the pattern match for MkT in g we have the constraint (C a
b), where &#8216;a&#8217; is existentially bound.&nbsp;&nbsp; So under GHC&#8217;s
current rules it&#8217;ll choose the (C a [a]) instance, and conclude that (b ~
[a]).&nbsp; So it&#8217;s ok to reverse x.&nbsp; But it isn&#8217;t; see function
bad!<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'>So to avoid unsoundness we must not choose a particular instance
from an overlapping set unless we know, absolutely positively, that the other
cases <b>cannot</b> match.&nbsp;&nbsp; <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'>(GHC&#8217;s exception for existentials was introduced in
response to user demand. Usually, overlapping instances are somehow semantically
coherent, and with an existential we are *<b>never</b>* going to learn more
about the instantiating type, so choosing the best available seems like a good
thing to do.)<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='mso-element:para-border-div;border:none;border-bottom:double windowtext 2.25pt;
padding:0cm 0cm 1.0pt 0cm'>

<p class=MsoNormal style='border:none;padding:0cm'><span style='font-size:11.0pt;
font-family:"Calibri","sans-serif";color:#1F497D'>But even nuking
IncoherentInstances altogether is not enough.&nbsp; Consider this variant of
Example 3, call it Example 4:<o:p></o:p></span></p>

</div>

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

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>&nbsp; class C a b | a -&gt; b<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'>&nbsp; instance C a [a]&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; --
Instance 2<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'>&nbsp; data T where<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>&nbsp;&nbsp;&nbsp; MkT :: C a b =&gt; a -&gt; b -&gt; T<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'>&nbsp; g :: T -&gt; T<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>&nbsp; g (MkT n x) = MkT n (reverse x)&nbsp;&nbsp; -- Uses Instance
2 <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><b><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>module</span></b><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'> Bad where<o:p></o:p></span></p>

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

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>&nbsp; instance C Int Bool&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; --
Instance 1<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'>&nbsp; f :: Bool -&gt; T<o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>&nbsp; f x = MkT (3::Int) x&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; --
Uses Instance 1<o:p></o:p></span></p>

<div style='mso-element:para-border-div;border:none;border-bottom:double windowtext 2.25pt;
padding:0cm 0cm 1.0pt 0cm'>

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

<p class=MsoNormal style='border:none;padding:0cm'><span style='font-size:11.0pt;
font-family:"Calibri","sans-serif";color:#1F497D'>&nbsp; bad :: Bool -&gt; T<o:p></o:p></span></p>

<p class=MsoNormal style='border:none;padding:0cm'><span style='font-size:11.0pt;
font-family:"Calibri","sans-serif";color:#1F497D'>&nbsp; bad = g . f<o:p></o:p></span></p>

</div>

<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'>This is nasty.&nbsp; In module M we have only one instance
declaration for C, so there&#8217;s no overlap, and function g typechecks
fine.&nbsp; <o:p></o:p></span></p>

<p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'><br>
Now module Bad adds an overlapping instance declaration and &#8216;f&#8217; uses
it; moreover, it&#8217;s clear that the new instance declaration is the right
one to use.<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&#8217;s not clear how to fix this.&nbsp; The only way I can
think of is to insist that all the instances appear in a single module, so that
you cannot add more &#8220;later&#8221;. But that loses part of the point of
overlap in the first place, namely to provide a generic instance and then later
override it.<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'><o:p>&nbsp;</o:p></span></p>

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

<p class=MsoListParagraph style='text-indent:-18.0pt;mso-list:l4 level1 lfo1'><![if !supportLists]><span
style='font-size:11.0pt;font-family:Symbol;color:#1F497D'><span
style='mso-list:Ignore'>&middot;<span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span></span></span><![endif]><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>embody eager checking for inconsistent instances, across modules<o:p></o:p></span></p>

<p class=MsoListParagraph style='text-indent:-18.0pt;mso-list:l4 level1 lfo1'><![if !supportLists]><span
style='font-size:11.0pt;font-family:Symbol;color:#1F497D'><span
style='mso-list:Ignore'>&middot;<span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span></span></span><![endif]><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>never resolve overlap until only a unique instance can possibly
match<o:p></o:p></span></p>

<p class=MsoListParagraph style='text-indent:-18.0pt;mso-list:l4 level1 lfo1'><![if !supportLists]><span
style='font-size:11.0pt;font-family:Symbol;color:#1F497D'><span
style='mso-list:Ignore'>&middot;<span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span></span></span><![endif]><span style='font-size:11.0pt;font-family:"Calibri","sans-serif";
color:#1F497D'>put all overlapping instances in a single module<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'>Type families already implement the first of these.&nbsp;&nbsp;&nbsp;
I believe that if we added the second and third, then overlap of type families would
be fine.&nbsp; (I may live to eat my words here.)&nbsp; <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'>I&#8217;d be interested to know what Chameleon does on these examples.<o:p></o:p></span></p>

</div>

</body>

</html>