<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta name="robots" content="index,nofollow">



<title>AdmitsEquality - MLton Standard ML Compiler (SML Compiler)</title>
<link rel="stylesheet" type="text/css" charset="iso-8859-1" media="all" href="common.css">
<link rel="stylesheet" type="text/css" charset="iso-8859-1" media="screen" href="screen.css">
<link rel="stylesheet" type="text/css" charset="iso-8859-1" media="print" href="print.css">


<link rel="Start" href="Home">


</head>

<body lang="en" dir="ltr">

<table bgcolor = lightblue cellspacing = 0 style = "border: 0px;" width = 100%>
  <tr>
    <td style = "
		border: 0px;
		color: darkblue; 
		font-size: 150%;
		text-align: left;">
      <a class = mltona href="Home">MLton 20051202</a>
    <td style = "
		border: 0px;
		font-size: 150%;
		text-align: center;
		width: 50%;">
      AdmitsEquality
    <td style = "
		border: 0px;
		text-align: right;">
      <table cellspacing = 0 style = "border: 0px">
        <tr style = "vertical-align: middle;">
      </table>
  <tr style = "background-color: white;">
    <td colspan = 3
	style = "
		border: 0px;
		font-size:70%;
		text-align: right;">
      <a href = "Home">Home</a>
      &nbsp;<a href = "Index">Index</a>
      &nbsp;
</table>
<div id="content" lang="en" dir="ltr">
A <a href="TypeConstructor">TypeConstructor</a> admits equality if whenever it is applied to equality types, the result is an <a href="EqualityType">EqualityType</a>.  This notion enables one to determine whether a type constructor application yields an equality type solely from the application, without looking at the definition of the type constructor.  It helps to ensure that <a href="PolymorphicEquality">PolymorphicEquality</a> is only applied to sensible values. <p>
The definition of admits equality depends on whether the type constructor was declared by a <tt>type</tt> definition or a <tt>datatype</tt> declaration. 
</p>
<h2 id="head-67921ac307a0edfd915b53407b84c8c0457981a2">Type definitions</h2>
<p>
For type definition  
</p>

<pre class=code>
<B><FONT COLOR="#A020F0">type</FONT></B><FONT COLOR="#228B22"><B> ('a1, ..., 'an) t </FONT></B>=<FONT COLOR="#228B22"><B> </FONT></B>...
</PRE>
<p>
 
</p>
<p>
type constructor <tt>t</tt> admits equality if the right-hand side of the definition is an equality type after replacing <tt>'a1</tt>, ..., <tt>'an</tt> by equality types (it doesn't matter which equality types are chosen). 
</p>
<p>
For a nullary type definition, this amounts to the right-hand side being an equality type.  For example, after the definition 
</p>

<pre class=code>
<B><FONT COLOR="#A020F0">type</FONT></B><FONT COLOR="#228B22"><B> t </FONT></B>=<FONT COLOR="#228B22"><B> bool * int
</FONT></B></PRE>
<p>
 
</p>
<p>
type constructor <tt>t</tt> admits equality because <tt>bool&nbsp;*&nbsp;int</tt> is an equality type.   On the other hand, after the definition 
</p>

<pre class=code>
<B><FONT COLOR="#A020F0">type</FONT></B><FONT COLOR="#228B22"><B> t </FONT></B>=<FONT COLOR="#228B22"><B> bool * int * real
</FONT></B></PRE>
<p>
 
</p>
<p>
type constructor <tt>t</tt> does not admit equality, because <tt>real</tt> is not an equality type. 
</p>
<p>
For another example, after the definition 
</p>

<pre class=code>
<B><FONT COLOR="#A020F0">type</FONT></B><FONT COLOR="#228B22"><B> 'a t </FONT></B>=<FONT COLOR="#228B22"><B> bool * 'a
</FONT></B></PRE>
<p>
 
</p>
<p>
type constructor <tt>t</tt> admits equality because <tt>bool&nbsp;*&nbsp;int</tt> is an equality type (we could have chosen any equality type other than <tt>int</tt>). 
</p>
<p>
On the other hand, after the definition 
</p>

<pre class=code>
<B><FONT COLOR="#A020F0">type</FONT></B><FONT COLOR="#228B22"><B> 'a t </FONT></B>=<FONT COLOR="#228B22"><B> real * 'a
</FONT></B></PRE>
<p>
 
</p>
<p>
type constructor <tt>t</tt> does not admit equality because  <tt>real&nbsp;*&nbsp;int</tt> is not equality type. 
</p>
<p>
We can check that a type constructor admits equality using an <tt>eqtype</tt> specification. 
</p>

<pre class=code>
<B><FONT COLOR="#0000FF">structure</FONT></B> Ok: <B><FONT COLOR="#0000FF">sig</FONT></B> <B><FONT COLOR="#A020F0">eqtype</FONT></B><FONT COLOR="#228B22"><B> 'a t </FONT></B><B><FONT COLOR="#0000FF">end</FONT></B> = 
   <B><FONT COLOR="#0000FF">struct</FONT></B> 
      <B><FONT COLOR="#A020F0">type</FONT></B><FONT COLOR="#228B22"><B> 'a t </FONT></B>=<FONT COLOR="#228B22"><B> bool * 'a
   </FONT></B><B><FONT COLOR="#0000FF">end</FONT></B>
</PRE>
<p>
 
</p>

<pre class=code>
<B><FONT COLOR="#0000FF">structure</FONT></B> Bad: <B><FONT COLOR="#0000FF">sig</FONT></B> <B><FONT COLOR="#A020F0">eqtype</FONT></B><FONT COLOR="#228B22"><B> 'a t </FONT></B><B><FONT COLOR="#0000FF">end</FONT></B> = 
   <B><FONT COLOR="#0000FF">struct</FONT></B> 
      <B><FONT COLOR="#A020F0">type</FONT></B><FONT COLOR="#228B22"><B> 'a t </FONT></B>=<FONT COLOR="#228B22"><B> real * int * 'a
   </FONT></B><B><FONT COLOR="#0000FF">end</FONT></B>
</PRE>
<p>
 
</p>
<p>
On <tt>structure&nbsp;Bad</tt>, MLton reports the following error. 
<pre>Type t admits equality in signature but not in structure.
  not equality: [real] * _ * _
</pre>The <tt>not&nbsp;equality</tt> section provides an explanation of why the type did not admit equality, highlighting the problematic component (<tt>real</tt>). 
</p>
<h2 id="head-c494234542affd2943bc7247d524477b03bc18bc">Datatype declarations</h2>
<p>
For a type constructor declared by a datatype declaration to admit equality, every variant of the datatype must admit equality.  For example, the following datatype admits equality because <tt>bool</tt> and <tt>char&nbsp;*&nbsp;int</tt> are equality types. 
</p>

<pre class=code>
<B><FONT COLOR="#A020F0">datatype</FONT></B><FONT COLOR="#228B22"><B> t </FONT></B>=<FONT COLOR="#228B22"><B> <FONT COLOR="#B8860B">A</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> bool </FONT></B>|<FONT COLOR="#228B22"><B> <FONT COLOR="#B8860B">B</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> char * int
</FONT></B></PRE>
<p>
 
</p>
<p>
Nullary constructors trivially admit equality, so that the following datatype admits equality. 
<pre class=code>
<B><FONT COLOR="#A020F0">datatype</FONT></B><FONT COLOR="#228B22"><B> t </FONT></B>=<FONT COLOR="#228B22"><B> <FONT COLOR="#B8860B">A</FONT> </FONT></B>|<FONT COLOR="#228B22"><B> <FONT COLOR="#B8860B">B</FONT> </FONT></B>|<FONT COLOR="#228B22"><B> <FONT COLOR="#B8860B">C</FONT>
</FONT></B></PRE>
 
</p>
<p>
For a parameterized datatype constructor to admit equality, we consider each variant as a type definition, and require that the definition admit equality.  For example, for the datatype  
</p>

<pre class=code>
<B><FONT COLOR="#A020F0">datatype</FONT></B><FONT COLOR="#228B22"><B> 'a t </FONT></B>=<FONT COLOR="#228B22"><B> <FONT COLOR="#B8860B">A</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> bool * 'a </FONT></B>|<FONT COLOR="#228B22"><B> <FONT COLOR="#B8860B">B</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> 'a
</FONT></B></PRE>
<p>
 
</p>
<p>
the type definitions 
</p>

<pre class=code>
<B><FONT COLOR="#A020F0">type</FONT></B><FONT COLOR="#228B22"><B> 'a tA </FONT></B>=<FONT COLOR="#228B22"><B> bool * 'a
</FONT></B><B><FONT COLOR="#A020F0">type</FONT></B><FONT COLOR="#228B22"><B> 'a tB </FONT></B>=<FONT COLOR="#228B22"><B> 'a 
</FONT></B></PRE>
<p>
 
</p>
<p>
both admit equality.  Thus, type constructor <tt>t</tt> admits equality. 
</p>
<p>
On the other hand, the following datatype does not admit equality. 
</p>

<pre class=code>
<B><FONT COLOR="#A020F0">datatype</FONT></B><FONT COLOR="#228B22"><B> 'a t </FONT></B>=<FONT COLOR="#228B22"><B> <FONT COLOR="#B8860B">A</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> bool * 'a </FONT></B>|<FONT COLOR="#228B22"><B> <FONT COLOR="#B8860B">B</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> real * 'a
</FONT></B></PRE>
<p>
 
</p>
<p>
As with type definitions, we can check using an <tt>eqtype</tt> specification. 
</p>

<pre class=code>
<B><FONT COLOR="#0000FF">structure</FONT></B> Bad: <B><FONT COLOR="#0000FF">sig</FONT></B> <B><FONT COLOR="#A020F0">eqtype</FONT></B><FONT COLOR="#228B22"><B> 'a t </FONT></B><B><FONT COLOR="#0000FF">end</FONT></B> =
   <B><FONT COLOR="#0000FF">struct</FONT></B>
      <B><FONT COLOR="#A020F0">datatype</FONT></B><FONT COLOR="#228B22"><B> 'a t </FONT></B>=<FONT COLOR="#228B22"><B> <FONT COLOR="#B8860B">A</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> bool * 'a </FONT></B>|<FONT COLOR="#228B22"><B> <FONT COLOR="#B8860B">B</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> real * 'a
   </FONT></B><B><FONT COLOR="#0000FF">end</FONT></B>
</PRE>
<p>
 
</p>
<p>
MLton reports the following error. 
</p>

<pre>Type t admits equality in signature but not in structure.
  not equality: B of [real] * _
</pre><p>
MLton indicates the problematic constructor (<tt>B</tt>), as well as the problematic component of the constructor's argument. 
</p>
<h3 id="head-c549e40c38aec54d5abd4cedb1559a45a15f6a81">Recursive datatypes</h3>
<p>
A recursive datatype like 
</p>

<pre class=code>
<B><FONT COLOR="#A020F0">datatype</FONT></B><FONT COLOR="#228B22"><B> t </FONT></B>=<FONT COLOR="#228B22"><B> <FONT COLOR="#B8860B">A</FONT> </FONT></B>|<FONT COLOR="#228B22"><B> <FONT COLOR="#B8860B">B</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> int * t
</FONT></B></PRE>
<p>
 
</p>
<p>
introduces a new problem, since in order to decide whether <tt>t</tt> admits equality, we need to know for the <tt>B</tt> variant whether <tt>t</tt> admits equality.  The <a href="DefinitionOfStandardML">Definition</a> answers this question by requiring a type constructor to admit equality if it is consistent to do so.  So, in our above example, if we assume that <tt>t</tt> admits equality, then the variant  <tt>B&nbsp;of&nbsp;int&nbsp;*&nbsp;t</tt> admits equality.  Then, since the <tt>A</tt> variant trivially admits equality, so does the type constructor <tt>t</tt>. Thus, it was consistent to assume that <tt>t</tt> admits equality, and so, <tt>t</tt> does admit equality. 
</p>
<p>
On the other hand, in the following declaration 
<pre class=code>
<B><FONT COLOR="#A020F0">datatype</FONT></B><FONT COLOR="#228B22"><B> t </FONT></B>=<FONT COLOR="#228B22"><B> <FONT COLOR="#B8860B">A</FONT> </FONT></B>|<FONT COLOR="#228B22"><B> <FONT COLOR="#B8860B">B</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> real * t
</FONT></B></PRE>
 if we assume that <tt>t</tt> admits equality, then the <tt>B</tt> variant does not admit equality.  Hence, the type constructor <tt>t</tt> does not admit equality, and our assumption was inconsistent.  Hence, <tt>t</tt> does not admit equality. 
</p>
<p>
The same kind of reasoning applies to mutually recursive datatypes as well.  For example, the following defines both <tt>t</tt> and <tt>u</tt> to admit equality. 
<pre class=code>
<B><FONT COLOR="#A020F0">datatype</FONT></B><FONT COLOR="#228B22"><B> t </FONT></B>=<FONT COLOR="#228B22"><B> <FONT COLOR="#B8860B">A</FONT> </FONT></B>|<FONT COLOR="#228B22"><B> <FONT COLOR="#B8860B">B</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> u
</FONT></B><B><FONT COLOR="#A020F0">and</FONT></B><FONT COLOR="#228B22"><B> u </FONT></B>=<FONT COLOR="#228B22"><B> <FONT COLOR="#B8860B">C</FONT> </FONT></B>|<FONT COLOR="#228B22"><B> <FONT COLOR="#B8860B">D</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> t
</FONT></B></PRE>
 
</p>
<p>
But the following defines neither <tt>t</tt> nor <tt>u</tt> to admit equality. 
<pre class=code>
<B><FONT COLOR="#A020F0">datatype</FONT></B><FONT COLOR="#228B22"><B> t </FONT></B>=<FONT COLOR="#228B22"><B> <FONT COLOR="#B8860B">A</FONT> </FONT></B>|<FONT COLOR="#228B22"><B> <FONT COLOR="#B8860B">B</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> u * real
</FONT></B><B><FONT COLOR="#A020F0">and</FONT></B><FONT COLOR="#228B22"><B> u </FONT></B>=<FONT COLOR="#228B22"><B> <FONT COLOR="#B8860B">C</FONT> </FONT></B>|<FONT COLOR="#228B22"><B> <FONT COLOR="#B8860B">D</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> t
</FONT></B></PRE>
 
</p>
<p>
As always, we can check whether a type admits equality using an <tt>eqtype</tt> specification. 
</p>

<pre class=code>
<B><FONT COLOR="#0000FF">structure</FONT></B> Bad: <B><FONT COLOR="#0000FF">sig</FONT></B> <B><FONT COLOR="#A020F0">eqtype</FONT></B><FONT COLOR="#228B22"><B> t </FONT></B><B><FONT COLOR="#A020F0">eqtype</FONT></B><FONT COLOR="#228B22"><B> u </FONT></B><B><FONT COLOR="#0000FF">end</FONT></B> =
   <B><FONT COLOR="#0000FF">struct</FONT></B>
      <B><FONT COLOR="#A020F0">datatype</FONT></B><FONT COLOR="#228B22"><B> t </FONT></B>=<FONT COLOR="#228B22"><B> <FONT COLOR="#B8860B">A</FONT> </FONT></B>|<FONT COLOR="#228B22"><B> <FONT COLOR="#B8860B">B</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> u * real
      </FONT></B><B><FONT COLOR="#A020F0">and</FONT></B><FONT COLOR="#228B22"><B> u </FONT></B>=<FONT COLOR="#228B22"><B> <FONT COLOR="#B8860B">C</FONT> </FONT></B>|<FONT COLOR="#228B22"><B> <FONT COLOR="#B8860B">D</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> t
   </FONT></B><B><FONT COLOR="#0000FF">end</FONT></B>
</PRE>
<p>
 
</p>
<p>
MLton reports the following error. 
</p>

<pre>Error: z.sml 1.16.
  Type t admits equality in signature but not in structure.
    not equality: B of [u] * [real]
Error: z.sml 1.16.
  Type u admits equality in signature but not in structure.
    not equality: D of [t]
</pre></div>



<p>
<hr>
Last edited on 2005-12-02 06:44:43 by <span title="ppp-71-139-183-221.dsl.snfc21.pacbell.net"><a href="StephenWeeks">StephenWeeks</a></span>.
</body></html>
