<html><head><meta http-equiv="Content-Type" content="text/html; charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">Aha. So you're viewing complete sets as a type-directed property, where we can take a type and look up what complete sets of patterns of that type might be.<div class=""><br class=""></div><div class="">Then, when checking a pattern-match for completeness, we use the inferred type of the pattern, access its complete sets, and if these match up. (Perhaps an implementation may optimize this process.)</div><div class=""><br class=""></div><div class="">What I like about this approach is that it works well with GADTs, where, e.g., VNil is a complete set for type Vec a Zero but not for Vec a n.</div><div class=""><br class=""></div><div class="">I take back my claim of "No types!" then, as this does sound like it has the right properties.</div><div class=""><br class=""></div><div class="">For now, I don't want to get bogged down by syntax -- let's figure out how the idea should work first, and then we can worry about syntax.</div><div class=""><br class=""></div><div class="">Here's a stab at a formalization of this idea, written in metatheory, not Haskell:</div><div class=""><br class=""></div><div class="">Let C : Type -> Set of set of patterns. C will be the lookup function for complete sets. Suppose we have a pattern match, at type tau, matching against patterns Ps. Let S = C(tau). S is then a set of sets of patterns. The question is this: Is there a set s in S such that Ps is a superset of s? If yes, then the match is complete.</div><div class=""><br class=""></div><div class="">What do we think of this design? Of course, the challenge is in building C, but we'll tackle that next.</div><div class=""><br class=""></div><div class="">Richard<br class=""><div class=""><div><br class=""><blockquote type="cite" class=""><div class="">On Oct 26, 2018, at 5:20 AM, Sylvain Henry <<a href="mailto:sylvain@haskus.fr" class="">sylvain@haskus.fr</a>> wrote:</div><br class="Apple-interchange-newline"><div class="">
  
    <meta http-equiv="Content-Type" content="text/html;
      charset=windows-1252" class="">
  
  <div text="#000000" bgcolor="#FFFFFF" class=""><p class="">Sorry I wasn't clear. I'm not an expert on the topic but it seems
      to me that there are two orthogonal concerns:</p><p class="">1) How does the checker retrieve COMPLETE sets.</p><p class="">Currently it seems to "attach" them to data type constructors
      (e.g. Maybe). If instead it retrieved them by matching types (e.g.
      "Maybe a", "a") we could write:</p><p class="">{-# COMPLETE LL #-}<br class="">
    </p><p class="">From an implementation point of view, it seems to me that finding
      complete sets would become similar to finding (flexible,
      overlapping) class instances. Pseudo-code:<br class="">
    </p>
    <pre class="">class Complete a where
  conlikes :: [ConLike]
instance Complete (Maybe a) where
  conlikes = [Nothing @a, Just @a]
instance Complete (Maybe a) where
  conlikes = [N @a, J @a]
instance Complete a where
  conlikes = [LL @a]
...
</pre><p class=""><br class="">
    </p><p class="">2) COMPLETE set depending on the matched type.</p><p class="">It is a thread hijack from me but while we are thinking about
      refactoring COMPLETE pragmas to support polymorphism, maybe we
      could support this too. The idea is to build a different set of
      conlikes depending on the matched type. Pseudo-code:<br class="">
    </p>
    <pre class="">instance Complete (Variant cs) where
  conlikes = [V @c | c <- cs] -- cs is a type list
</pre><p class="">(I don't really care about the pragma syntax)</p><p class="">Sorry for the thread hijack!<br class="">
      Regards,<br class="">
      Sylvain<br class="">
    </p><p class=""><br class="">
    </p>
    <div class="moz-cite-prefix">On 10/26/18 5:59 AM, Richard Eisenberg
      wrote:<br class="">
    </div>
    <blockquote type="cite" cite="mid:7031558E-BDD9-4571-A5C3-CFF486455BEA@cs.brynmawr.edu" class="">
      <meta http-equiv="Content-Type" content="text/html;
        charset=windows-1252" class="">
      I'm afraid I don't understand what your new syntax means. And,
      while I know it doesn't work today, what's wrong (in theory) with
      <div class=""><br class="">
      </div>
      <div class="">{-# COMPLETE LL #-}</div>
      <div class=""><br class="">
      </div>
      <div class="">No types! (That's a rare thing for me to extol...)</div>
      <div class=""><br class="">
      </div>
      <div class="">I feel I must be missing something here.</div>
      <div class=""><br class="">
      </div>
      <div class="">Thanks,</div>
      <div class="">Richard<br class="">
        <div class=""><br class="">
          <blockquote type="cite" class="">
            <div class="">On Oct 25, 2018, at 12:24 PM, Sylvain Henry
              <<a href="mailto:sylvain@haskus.fr" class="" moz-do-not-send="true">sylvain@haskus.fr</a>> wrote:</div>
            <br class="Apple-interchange-newline">
            <div class="">
              <meta http-equiv="Content-Type" content="text/html;
                charset=windows-1252" class="">
              <div text="#000000" bgcolor="#FFFFFF" class="">
                <pre class="moz-quote-pre" wrap="">> In the case where all the patterns are polymorphic, a user must
> provide a type signature but we accept the definition regardless of
> the type signature they provide. </pre><p class="">Currently we can specify the type
                  *constructor* in a COMPLETE pragma:</p>
                <pre class=""><tt class="">pattern J :: a -> Maybe a</tt><tt class="">
</tt><tt class="">pattern J a = Just a</tt><tt class="">
</tt><tt class="">
</tt><tt class="">pattern N :: Maybe a</tt><tt class="">
</tt><tt class="">pattern N = Nothing</tt><tt class="">
</tt><tt class="">
</tt><tt class="">{-# COMPLETE N, J :: Maybe #-}</tt><tt class="">
</tt></pre><p class=""><br class="">
                </p><p class="">Instead if we could specify the type with
                  its free vars, we could refer to them in conlike
                  signatures:</p>
                <pre class=""><span class="p">{-# COMPLETE N, [</span><span class="p"><span class="kt"> J</span></span><span class="p"><span class="kt"></span> <span class="ow">::</span> a -> Maybe a ] :: Maybe a #-}</span></pre><p class="">The COMPLETE pragma for LL could be:<span class="p"></span><br class="">
                  <span class="p"></span></p>
                <pre class=""><pre class=""><span class="p">{-# COMPLETE [</span><span class="p"><span class="kt"> LL</span> <span class="ow">::</span> <span class="kt">HasSrcSpan</span> a <span class="ow">=></span> <span class="kt">SrcSpan</span> <span class="ow">-></span> <span class="kt">SrcSpanLess</span> a <span class="ow">-></span> a ] :: a #-}
</span></pre></pre>
                <br class=""><p class="">I'm borrowing the list comprehension syntax
                  on purpose because it would allow to define a set of
                  conlikes from a type-list (see my request [1]):<span class="p"></span><br class="">
                  <span class="p"></span></p>
                <pre class=""><pre class=""><span class="p">{-# COMPLETE [</span><span class="p"><span class="kt"> V</span> <span class="ow">::</span> </span><span class="p"><span class="p">(c :< cs) => c -> Variant cs</span>
             | c <- cs
             ] :: Variant cs
  #-}</span>
</pre>
>    To make things more formal, when the pattern-match checker
> requests a set of constructors for some data type constructor T, the
> checker returns:
>
>    * The original set of data constructors for T
>    * Any COMPLETE sets of type T
>
> Note the use of the phrase <b class="moz-txt-star"><span class="moz-txt-tag">*</span>type constructor<span class="moz-txt-tag">*</span></b>. The return type of all
> constructor-like things in a COMPLETE set must all be headed by the
> same type constructor T. Since `LL`'s return type is simply a type
> variable `a`, this simply doesn't work with the design of COMPLETE
> sets.

</pre><p class="">Could we use a mechanism similar to instance
                  resolution (with FlexibleInstances) for the checker to
                  return matching COMPLETE sets instead?</p>
                <pre class="">--Sylvain


[1] <a class="moz-txt-link-freetext" href="https://mail.haskell.org/pipermail/ghc-devs/2018-July/016053.html" moz-do-not-send="true">https://mail.haskell.org/pipermail/ghc-devs/2018-July/016053.html</a>
<span class="p"></span></pre>
              </div>
              _______________________________________________<br class="">
              ghc-devs mailing list<br class="">
              <a href="mailto:ghc-devs@haskell.org" class="" moz-do-not-send="true">ghc-devs@haskell.org</a><br class="">
              <a class="moz-txt-link-freetext" href="http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs">http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs</a><br class="">
            </div>
          </blockquote>
        </div>
        <br class="">
      </div>
    </blockquote>
  </div>

</div></blockquote></div><br class=""></div></div></body></html>