<!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">
<script src="http://www.google-analytics.com/urchin.js" type="text/javascript">
</script>
<script type="text/javascript">
_uacct = "UA-833377-1";
urchinTracker();
</script>
<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 MLTONWIKIVERSION</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>
<a href = "TitleIndex">Index</a>
</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><B><FONT COLOR="#228B22"> ('a1, ..., 'an) t </FONT></B>=<B><FONT COLOR="#228B22"> </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><B><FONT COLOR="#228B22"> t </FONT></B>=<B><FONT COLOR="#228B22"> bool * int
</FONT></B></PRE>
<p>
</p>
<p>
type constructor <tt>t</tt> admits equality because <tt>bool * int</tt> is an equality type. On the other hand, after the definition
</p>
<pre class=code>
<B><FONT COLOR="#A020F0">type</FONT></B><B><FONT COLOR="#228B22"> t </FONT></B>=<B><FONT COLOR="#228B22"> 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><B><FONT COLOR="#228B22"> 'a t </FONT></B>=<B><FONT COLOR="#228B22"> bool * 'a
</FONT></B></PRE>
<p>
</p>
<p>
type constructor <tt>t</tt> admits equality because <tt>bool * 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><B><FONT COLOR="#228B22"> 'a t </FONT></B>=<B><FONT COLOR="#228B22"> real * 'a
</FONT></B></PRE>
<p>
</p>
<p>
type constructor <tt>t</tt> does not admit equality because <tt>real * 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><B><FONT COLOR="#228B22"> '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><B><FONT COLOR="#228B22"> 'a t </FONT></B>=<B><FONT COLOR="#228B22"> 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><B><FONT COLOR="#228B22"> '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><B><FONT COLOR="#228B22"> 'a t </FONT></B>=<B><FONT COLOR="#228B22"> real * int * 'a
</FONT></B><B><FONT COLOR="#0000FF">end</FONT></B>
</PRE>
<p>
</p>
<p>
On <tt>structure 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 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 <a href="Variant">variant</a> of the datatype must admit equality. For example, the following datatype admits equality because <tt>bool</tt> and <tt>char * int</tt> are equality types.
</p>
<pre class=code>
<B><FONT COLOR="#A020F0">datatype</FONT></B><B><FONT COLOR="#228B22"> t </FONT></B>=<B><FONT COLOR="#228B22"> <FONT COLOR="#B8860B">A</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> bool </FONT></B>|<B><FONT COLOR="#228B22"> <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><B><FONT COLOR="#228B22"> t </FONT></B>=<B><FONT COLOR="#228B22"> <FONT COLOR="#B8860B">A</FONT> </FONT></B>|<B><FONT COLOR="#228B22"> <FONT COLOR="#B8860B">B</FONT> </FONT></B>|<B><FONT COLOR="#228B22"> <FONT COLOR="#B8860B">C</FONT>
</FONT></B></PRE>
</p>
<p>
For a parameterized datatype constructor to admit equality, we consider each <a href="Variant">variant</a> 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><B><FONT COLOR="#228B22"> 'a t </FONT></B>=<B><FONT COLOR="#228B22"> <FONT COLOR="#B8860B">A</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> bool * 'a </FONT></B>|<B><FONT COLOR="#228B22"> <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><B><FONT COLOR="#228B22"> 'a tA </FONT></B>=<B><FONT COLOR="#228B22"> bool * 'a
</FONT></B><B><FONT COLOR="#A020F0">type</FONT></B><B><FONT COLOR="#228B22"> 'a tB </FONT></B>=<B><FONT COLOR="#228B22"> '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><B><FONT COLOR="#228B22"> 'a t </FONT></B>=<B><FONT COLOR="#228B22"> <FONT COLOR="#B8860B">A</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> bool * 'a </FONT></B>|<B><FONT COLOR="#228B22"> <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><B><FONT COLOR="#228B22"> '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><B><FONT COLOR="#228B22"> 'a t </FONT></B>=<B><FONT COLOR="#228B22"> <FONT COLOR="#B8860B">A</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> bool * 'a </FONT></B>|<B><FONT COLOR="#228B22"> <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><B><FONT COLOR="#228B22"> t </FONT></B>=<B><FONT COLOR="#228B22"> <FONT COLOR="#B8860B">A</FONT> </FONT></B>|<B><FONT COLOR="#228B22"> <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> <a href="Variant">variant</a> 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 <a href="Variant">variant</a> <tt>B of int * t</tt> admits equality. Then, since the <tt>A</tt> <a href="Variant">variant</a> 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><B><FONT COLOR="#228B22"> t </FONT></B>=<B><FONT COLOR="#228B22"> <FONT COLOR="#B8860B">A</FONT> </FONT></B>|<B><FONT COLOR="#228B22"> <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> <a href="Variant">variant</a> 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><B><FONT COLOR="#228B22"> t </FONT></B>=<B><FONT COLOR="#228B22"> <FONT COLOR="#B8860B">A</FONT> </FONT></B>|<B><FONT COLOR="#228B22"> <FONT COLOR="#B8860B">B</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> u
</FONT></B><B><FONT COLOR="#A020F0">and</FONT></B><B><FONT COLOR="#228B22"> u </FONT></B>=<B><FONT COLOR="#228B22"> <FONT COLOR="#B8860B">C</FONT> </FONT></B>|<B><FONT COLOR="#228B22"> <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><B><FONT COLOR="#228B22"> t </FONT></B>=<B><FONT COLOR="#228B22"> <FONT COLOR="#B8860B">A</FONT> </FONT></B>|<B><FONT COLOR="#228B22"> <FONT COLOR="#B8860B">B</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> u * real
</FONT></B><B><FONT COLOR="#A020F0">and</FONT></B><B><FONT COLOR="#228B22"> u </FONT></B>=<B><FONT COLOR="#228B22"> <FONT COLOR="#B8860B">C</FONT> </FONT></B>|<B><FONT COLOR="#228B22"> <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><B><FONT COLOR="#228B22"> t </FONT></B><B><FONT COLOR="#A020F0">eqtype</FONT></B><B><FONT COLOR="#228B22"> u </FONT></B><B><FONT COLOR="#0000FF">end</FONT></B> =
<B><FONT COLOR="#0000FF">struct</FONT></B>
<B><FONT COLOR="#A020F0">datatype</FONT></B><B><FONT COLOR="#228B22"> t </FONT></B>=<B><FONT COLOR="#228B22"> <FONT COLOR="#B8860B">A</FONT> </FONT></B>|<B><FONT COLOR="#228B22"> <FONT COLOR="#B8860B">B</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> u * real
</FONT></B><B><FONT COLOR="#A020F0">and</FONT></B><B><FONT COLOR="#228B22"> u </FONT></B>=<B><FONT COLOR="#228B22"> <FONT COLOR="#B8860B">C</FONT> </FONT></B>|<B><FONT COLOR="#228B22"> <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 2007-07-08 22:57:33 by <span title="c-71-57-91-146.hsd1.il.comcast.net"><a href="MatthewFluet">MatthewFluet</a></span>.
</body></html>
