<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=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Helvetica;
panose-1:2 11 6 4 2 2 2 2 2 4;}
@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;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
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;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.apple-converted-space
{mso-style-name:apple-converted-space;}
span.EmailStyle20
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@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:725836192;
mso-list-type:hybrid;
mso-list-template-ids:474889682 134807567 134807577 134807579 134807567 134807577 134807579 134807567 134807577 134807579;}
@list l0:level1
{mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:72.0pt;
text-indent:-18.0pt;}
@list l0:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:108.0pt;
text-indent:-18.0pt;}
@list l0:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
margin-left:144.0pt;
text-indent:-9.0pt;}
@list l0:level4
{mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:180.0pt;
text-indent:-18.0pt;}
@list l0:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:216.0pt;
text-indent:-18.0pt;}
@list l0:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
margin-left:252.0pt;
text-indent:-9.0pt;}
@list l0:level7
{mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:288.0pt;
text-indent:-18.0pt;}
@list l0:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:324.0pt;
text-indent:-18.0pt;}
@list l0:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
margin-left:360.0pt;
text-indent:-9.0pt;}
@list l1
{mso-list-id:796949859;
mso-list-type:hybrid;
mso-list-template-ids:-1217788568 134807567 134807555 134807557 134807553 134807555 134807557 134807553 134807555 134807557;}
@list l1:level1
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
@list l1:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l1:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l1:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l1:level5
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l1:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l1:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l1:level8
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l1:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
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" style="word-wrap:break-word">
<div class="WordSection1">
<p class="MsoNormal" style="margin-left:36.0pt">I haven't thought about how to implement such a thing. At the least, it would probably require some annotation saying that we expect `\HNil -> ()` to be exhaustive (as GHC won't, in general, make that assumption).
Even with that, could we get type inference to behave? Possibly.<o:p></o:p></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">As I wrote in another post on this thread, it’s a bit tricky.
<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">What would you expect of (EX1)<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";mso-fareast-language:EN-US"> \x -> case x of HNil -> blah<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">Here the lambda and the case are separated<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">Now (EX2)<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal" style="margin-left:18.0pt"><span style="font-family:"Courier New";mso-fareast-language:EN-US">\x -> (x, case x of HNil -> blah)<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">Here the lambda and the case are separated more, and x is used twice.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">What if there are more data constructors that share a common return type? (EX3)<o:p></o:p></span></p>
<p class="MsoListParagraph"><span style="font-family:"Courier New";mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal" style="margin-left:18.0pt"><span style="font-family:"Courier New";mso-fareast-language:EN-US">data HL2 a where<o:p></o:p></span></p>
<p class="MsoListParagraph" style="text-indent:36.0pt"><span style="font-family:"Courier New";mso-fareast-language:EN-US">HNil1 :: HL2 []<o:p></o:p></span></p>
<p class="MsoListParagraph" style="text-indent:36.0pt"><span style="font-family:"Courier New";mso-fareast-language:EN-US">HNil2 :: HL2 []<o:p></o:p></span></p>
<p class="MsoListParagraph" style="text-indent:36.0pt"><span style="font-family:"Courier New";mso-fareast-language:EN-US">HCons :: …blah…<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal" style="margin-left:36.0pt"><span style="font-family:"Courier New";mso-fareast-language:EN-US">\x -> case x of { HNil1 -> blah; HNil 2 -> blah }<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:36.0pt"><span style="font-family:"Courier New";mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">Here HNil1 and HNil2 both return HL2 []. Is that “singular”? <o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">What if one was a bit more general than the other? Do we seek the least common generalisation of the alternatives given? (EX4)<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal" style="margin-left:18.0pt"><span style="font-family:"Courier New";mso-fareast-language:EN-US">data HL3 a where<o:p></o:p></span></p>
<p class="MsoListParagraph" style="text-indent:36.0pt"><span style="font-family:"Courier New";mso-fareast-language:EN-US">HNil1 :: HL2 [Int]<o:p></o:p></span></p>
<p class="MsoListParagraph" style="text-indent:36.0pt"><span style="font-family:"Courier New";mso-fareast-language:EN-US">HNil2 :: HL2 [a]<o:p></o:p></span></p>
<p class="MsoListParagraph" style="text-indent:36.0pt"><span style="font-family:"Courier New";mso-fareast-language:EN-US">HCons :: …blah…<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal" style="margin-left:36.0pt"><span style="font-family:"Courier New";mso-fareast-language:EN-US">\x -> case x of { HNil1 -> blah; HNil 2 -> blah }<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">What if the cases were incompatible? (EX5)<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal" style="margin-left:18.0pt"><span style="font-family:"Courier New";mso-fareast-language:EN-US">data HL4 a where<o:p></o:p></span></p>
<p class="MsoListParagraph" style="text-indent:36.0pt"><span style="font-family:"Courier New";mso-fareast-language:EN-US">HNil1 :: HL2 [Int]<o:p></o:p></span></p>
<p class="MsoListParagraph" style="text-indent:36.0pt"><span style="font-family:"Courier New";mso-fareast-language:EN-US">HNil2 :: HL2 [Bool]<o:p></o:p></span></p>
<p class="MsoListParagraph" style="text-indent:36.0pt"><span style="font-family:"Courier New";mso-fareast-language:EN-US">HCons :: …blah…<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-family:"Courier New";mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal" style="margin-left:36.0pt"><span style="font-family:"Courier New";mso-fareast-language:EN-US">\x -> case x of { HNil1 -> blah; HNil 2 -> blah }<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">Would you expect that to somehow generalise to `HL4 [a] -> blah`?<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><br>
What if x matched multiple times, perhaps on different constructors (EX6)<br>
<br>
<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:18.0pt"><span style="font-family:"Courier New";mso-fareast-language:EN-US">\x -> (case s of HNil1 -> blah1; case x of HNil2 -> blah)<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">The water gets deep quickly here. I don’t (yet) see an obviously-satisfying design point that isn’t massively ad-hoc.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US">Simon<o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="mso-fareast-language:EN-US"><o:p> </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 #E1E1E1 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal"><b><span lang="EN-US">From:</span></b><span lang="EN-US"> ghc-devs <ghc-devs-bounces@haskell.org>
<b>On Behalf Of </b>Richard Eisenberg<br>
<b>Sent:</b> 29 March 2021 03:18<br>
<b>To:</b> Alexis King <lexi.lambda@gmail.com><br>
<b>Cc:</b> ghc-devs@haskell.org<br>
<b>Subject:</b> Re: Type inference of singular matches on GADTs<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal"><br>
<br>
<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal">On Mar 26, 2021, at 8:41 PM, Alexis King <<a href="mailto:lexi.lambda@gmail.com">lexi.lambda@gmail.com</a>> wrote:<o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif">If there’s a single principal type that makes my function well-typed<span class="apple-converted-space"> </span><i>and exhaustive</i>, I’d really like GHC to pick it.</span><o:p></o:p></p>
</div>
</blockquote>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">I think this is the key part of Alexis's plea: that the type checker take into account exhaustivity in choosing how to proceed.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Another way to think about this:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal">f1 :: HList '[] -> ()<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">f1 HNil = ()<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">f2 :: HList as -> ()<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">f2 HNil = ()<o:p></o:p></p>
</div>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Both f1 and f2 are well typed definitions. In any usage site where both are well-typed, they will behave the same. Yet f1 is exhaustive while f2 is not. This isn't really about an open-world assumption or the possibility of extra cases
-- it has to do with what the runtime behaviors of the two functions are. f1 never fails, while f2 must check a constructor tag and perhaps throw an exception.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">If we just see \HNil -> (), Alexis seems to be suggesting we prefer the f1 interpretation over the f2 interpretation. Why? Because f1 is exhaustive, and when we can choose an exhaustive interpretation, that's probably a good idea to pursue.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">I haven't thought about how to implement such a thing. At the least, it would probably require some annotation saying that we expect `\HNil -> ()` to be exhaustive (as GHC won't, in general, make that assumption). Even with that, could
we get type inference to behave? Possibly.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">But first: does this match your understanding?<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Richard<o:p></o:p></p>
</div>
</div>
</div>
</body>
</html>