<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:"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;}
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;}
--></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'm not saying this is a good idea for GHC or that it's implementable. But the idea of having type inference account for exhaustivity in this way does not seem, a priori, unspecified.<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">No, but I’m pointing out that specifying it might be tricky, involving some highly non-local reasoning. I can’t yet see how to write a formal specification. Note “yet” -- growth mindset!<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>
<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"> Richard Eisenberg <rae@richarde.dev>
<br>
<b>Sent:</b> 30 March 2021 04:58<br>
<b>To:</b> Simon Peyton Jones <simonpj@microsoft.com><br>
<b>Cc:</b> Alexis King <lexi.lambda@gmail.com>; 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">As usual, I want to separate out the specification of a feature from the implementation. So let's just focus on specification for now -- with the caveat that there might be no possible implementation of these ideas.<o:p></o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">The key innovation I see lurking here is the idea of an *exhaustive* function, where we know that any pattern-match on an argument is always exhaustive. I will write such a thing with @->, in both the type and in the arrow that appears
after the lambda. The @-> type is a subtype of -> (and perhaps does not need to be written differently from ->).<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">EX1: \x @-> case x of HNil -> blah<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">This is easy: we can infer HList '[] @-> blah's type, because the pattern match is declared to be exhaustive, and no other type grants that property.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">EX2: \x @-> (x, case x of HNit -> blah)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Same as EX1.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">EX3: \x @-> case x of { HNil1 -> blah; HNil2 -> blah }<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Same as EX1. There is still a unique type for which the patten-match is exhaustive.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">EX4: Reject. There are multiple valid types, and we don't know which one to pick. This is like classic untouchable-variables territory.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">EX5: This is hard. A declarative spec would probably choose HL2 [a] -> ... as you suggest, but there may be no implementation of such an idea.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">EX6: Reject. No type leads to exhaustive matches.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">I'm not saying this is a good idea for GHC or that it's implementable. But the idea of having type inference account for exhaustivity in this way does not seem, a priori, unspecified.<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>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<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 29, 2021, at 5:00 AM, Simon Peyton Jones <<a href="mailto:simonpj@microsoft.com">simonpj@microsoft.com</a>> wrote:<o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div style="margin-left:36.0pt">
<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">As I wrote in another post on this thread, it’s a bit tricky. <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">What would you expect of (EX1)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New""> \x -> case x of HNil -> blah</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">Here the lambda and the case are separated<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">Now (EX2)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New""> </span><o:p></o:p></p>
</div>
<div style="margin-left:18.0pt">
<p class="MsoNormal"><span style="font-family:"Courier New"">\x -> (x, case x of HNil -> blah)</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">Here the lambda and the case are separated more, and x is used twice.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">What if there are more data constructors that share a common return type? (EX3)<o:p></o:p></p>
</div>
<div style="margin-left:36.0pt">
<p class="MsoNormal"><span style="font-family:"Courier New""> </span><o:p></o:p></p>
</div>
<div style="margin-left:18.0pt">
<p class="MsoNormal"><span style="font-family:"Courier New"">data HL2 a where</span><o:p></o:p></p>
</div>
<div style="margin-left:36.0pt">
<p class="MsoNormal" style="text-indent:36.0pt"><span style="font-family:"Courier New"">HNil1 :: HL2 []</span><o:p></o:p></p>
</div>
<div style="margin-left:36.0pt">
<p class="MsoNormal" style="text-indent:36.0pt"><span style="font-family:"Courier New"">HNil2 :: HL2 []</span><o:p></o:p></p>
</div>
<div style="margin-left:36.0pt">
<p class="MsoNormal" style="text-indent:36.0pt"><span style="font-family:"Courier New"">HCons :: …blah…</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New""> </span><o:p></o:p></p>
</div>
<div style="margin-left:36.0pt">
<p class="MsoNormal"><span style="font-family:"Courier New"">\x -> case x of { HNil1 -> blah; HNil 2 -> blah }</span><o:p></o:p></p>
</div>
<div style="margin-left:36.0pt">
<p class="MsoNormal"><span style="font-family:"Courier New""> </span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">Here HNil1 and HNil2 both return HL2 []. Is that “singular”? <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">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></p>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<div style="margin-left:18.0pt">
<p class="MsoNormal"><span style="font-family:"Courier New"">data HL3 a where</span><o:p></o:p></p>
</div>
<div style="margin-left:36.0pt">
<p class="MsoNormal" style="text-indent:36.0pt"><span style="font-family:"Courier New"">HNil1 :: HL2 [Int]</span><o:p></o:p></p>
</div>
<div style="margin-left:36.0pt">
<p class="MsoNormal" style="text-indent:36.0pt"><span style="font-family:"Courier New"">HNil2 :: HL2 [a]</span><o:p></o:p></p>
</div>
<div style="margin-left:36.0pt">
<p class="MsoNormal" style="text-indent:36.0pt"><span style="font-family:"Courier New"">HCons :: …blah…</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New""> </span><o:p></o:p></p>
</div>
<div style="margin-left:36.0pt">
<p class="MsoNormal"><span style="font-family:"Courier New"">\x -> case x of { HNil1 -> blah; HNil 2 -> blah }</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">What if the cases were incompatible? (EX5)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<div style="margin-left:18.0pt">
<p class="MsoNormal"><span style="font-family:"Courier New"">data HL4 a where</span><o:p></o:p></p>
</div>
<div style="margin-left:36.0pt">
<p class="MsoNormal" style="text-indent:36.0pt"><span style="font-family:"Courier New"">HNil1 :: HL2 [Int]</span><o:p></o:p></p>
</div>
<div style="margin-left:36.0pt">
<p class="MsoNormal" style="text-indent:36.0pt"><span style="font-family:"Courier New"">HNil2 :: HL2 [Bool]</span><o:p></o:p></p>
</div>
<div style="margin-left:36.0pt">
<p class="MsoNormal" style="text-indent:36.0pt"><span style="font-family:"Courier New"">HCons :: …blah…</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New""> </span><o:p></o:p></p>
</div>
<div style="margin-left:36.0pt">
<p class="MsoNormal"><span style="font-family:"Courier New"">\x -> case x of { HNil1 -> blah; HNil 2 -> blah }</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">Would you expect that to somehow generalise to `HL4 [a] -> blah`?<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><br>
What if x matched multiple times, perhaps on different constructors (EX6)<br>
<br>
<br>
<o:p></o:p></p>
</div>
<div style="margin-left:18.0pt">
<p class="MsoNormal"><span style="font-family:"Courier New"">\x -> (case s of HNil1 -> blah1; case x of HNil2 -> blah)</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">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></p>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">Simon<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<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">
<div>
<p class="MsoNormal"><b><span lang="EN-US">From:</span></b><span class="apple-converted-space"><span lang="EN-US"> </span></span><span lang="EN-US">ghc-devs <<a href="mailto:ghc-devs-bounces@haskell.org">ghc-devs-bounces@haskell.org</a>><span class="apple-converted-space"> </span><b>On
Behalf Of<span class="apple-converted-space"> </span></b>Richard Eisenberg<br>
<b>Sent:</b><span class="apple-converted-space"> </span>29 March 2021 03:18<br>
<b>To:</b><span class="apple-converted-space"> </span>Alexis King <<a href="mailto:lexi.lambda@gmail.com">lexi.lambda@gmail.com</a>><br>
<b>Cc:</b><span class="apple-converted-space"> </span><a href="mailto:ghc-devs@haskell.org">ghc-devs@haskell.org</a><br>
<b>Subject:</b><span class="apple-converted-space"> </span>Re: Type inference of singular matches on GADTs</span><o:p></o:p></p>
</div>
</div>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<div>
<div>
<p class="MsoNormal"><br>
<br>
<br>
<o:p></o:p></p>
</div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<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>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<div>
<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>
</div>
</blockquote>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<div>
<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>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">Another way to think about this:<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div>
<p class="MsoNormal">f1 :: HList '[] -> ()<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">f1 HNil = ()<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">f2 :: HList as -> ()<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">f2 HNil = ()<o:p></o:p></p>
</div>
</div>
</blockquote>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<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>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<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>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<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>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">But first: does this match your understanding?<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">Richard<o:p></o:p></p>
</div>
</div>
</div>
</div>
</blockquote>
</div>
<div style="border:none;border-left:solid blue 1.5pt;padding:0cm 0cm 0cm 4.0pt">
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</div>
</body>
</html>