Backport from sid to buster
[hcoop/debian/mlton.git] / doc / guide / localhost / AdmitsEquality
CommitLineData
7f918cf1
CE
1<!DOCTYPE html>\r
2<html lang="en">\r
3<head>\r
4<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">\r
5<meta name="generator" content="AsciiDoc 8.6.9">\r
6<title>AdmitsEquality</title>\r
7<link rel="stylesheet" href="./asciidoc.css" type="text/css">\r
8<link rel="stylesheet" href="./pygments.css" type="text/css">\r
9\r
10\r
11<script type="text/javascript" src="./asciidoc.js"></script>\r
12<script type="text/javascript">\r
13/*<![CDATA[*/\r
14asciidoc.install();\r
15/*]]>*/\r
16</script>\r
17<link rel="stylesheet" href="./mlton.css" type="text/css">\r
18</head>\r
19<body class="article">\r
20<div id="banner">\r
21<div id="banner-home">\r
22<a href="./Home">MLton 20180207</a>\r
23</div>\r
24</div>\r
25<div id="header">\r
26<h1>AdmitsEquality</h1>\r
27</div>\r
28<div id="content">\r
29<div id="preamble">\r
30<div class="sectionbody">\r
31<div class="paragraph"><p>A <a href="TypeConstructor">TypeConstructor</a> admits equality if whenever it is applied to\r
32equality types, the result is an <a href="EqualityType">EqualityType</a>. This notion enables\r
33one to determine whether a type constructor application yields an\r
34equality type solely from the application, without looking at the\r
35definition of the type constructor. It helps to ensure that\r
36<a href="PolymorphicEquality">PolymorphicEquality</a> is only applied to sensible values.</p></div>\r
37<div class="paragraph"><p>The definition of admits equality depends on whether the type\r
38constructor was declared by a <span class="monospaced">type</span> definition or a\r
39<span class="monospaced">datatype</span> declaration.</p></div>\r
40</div>\r
41</div>\r
42<div class="sect1">\r
43<h2 id="_type_definitions">Type definitions</h2>\r
44<div class="sectionbody">\r
45<div class="paragraph"><p>For type definition</p></div>\r
46<div class="listingblock">\r
47<div class="content"><div class="highlight"><pre><span class="k">type</span><span class="w"> </span><span class="p">(</span><span class="n">&#39;a1</span><span class="p">,</span><span class="w"> </span><span class="p">...,</span><span class="w"> </span><span class="n">&#39;an</span><span class="p">)</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="p">...</span><span class="w"></span>\r
48</pre></div></div></div>\r
49<div class="paragraph"><p>type constructor <span class="monospaced">t</span> admits equality if the right-hand side of the\r
50definition is an equality type after replacing <span class="monospaced">'a1</span>, &#8230;,\r
51<span class="monospaced">'an</span> by equality types (it doesn&#8217;t matter which equality types\r
52are chosen).</p></div>\r
53<div class="paragraph"><p>For a nullary type definition, this amounts to the right-hand side\r
54being an equality type. For example, after the definition</p></div>\r
55<div class="listingblock">\r
56<div class="content"><div class="highlight"><pre><span class="k">type</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">bool</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">int</span><span class="w"></span>\r
57</pre></div></div></div>\r
58<div class="paragraph"><p>type constructor <span class="monospaced">t</span> admits equality because <span class="monospaced">bool * int</span> is\r
59an equality type. On the other hand, after the definition</p></div>\r
60<div class="listingblock">\r
61<div class="content"><div class="highlight"><pre><span class="k">type</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">bool</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">int</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">real</span><span class="w"></span>\r
62</pre></div></div></div>\r
63<div class="paragraph"><p>type constructor <span class="monospaced">t</span> does not admit equality, because <span class="monospaced">real</span>\r
64is not an equality type.</p></div>\r
65<div class="paragraph"><p>For another example, after the definition</p></div>\r
66<div class="listingblock">\r
67<div class="content"><div class="highlight"><pre><span class="k">type</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">bool</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"></span>\r
68</pre></div></div></div>\r
69<div class="paragraph"><p>type constructor <span class="monospaced">t</span> admits equality because <span class="monospaced">bool * int</span>\r
70is an equality type (we could have chosen any equality type other than\r
71<span class="monospaced">int</span>).</p></div>\r
72<div class="paragraph"><p>On the other hand, after the definition</p></div>\r
73<div class="listingblock">\r
74<div class="content"><div class="highlight"><pre><span class="k">type</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">real</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"></span>\r
75</pre></div></div></div>\r
76<div class="paragraph"><p>type constructor <span class="monospaced">t</span> does not admit equality because\r
77<span class="monospaced">real * int</span> is not equality type.</p></div>\r
78<div class="paragraph"><p>We can check that a type constructor admits equality using an\r
79<span class="monospaced">eqtype</span> specification.</p></div>\r
80<div class="listingblock">\r
81<div class="content"><div class="highlight"><pre><span class="k">structure</span><span class="w"> </span><span class="n">Ok</span><span class="p">:</span><span class="w"> </span><span class="k">sig</span><span class="w"> </span><span class="k">eqtype</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="k">end</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r
82<span class="w"> </span><span class="k">struct</span><span class="w"></span>\r
83<span class="w"> </span><span class="k">type</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">bool</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"></span>\r
84<span class="w"> </span><span class="k">end</span><span class="w"></span>\r
85</pre></div></div></div>\r
86<div class="listingblock">\r
87<div class="content"><div class="highlight"><pre><span class="k">structure</span><span class="w"> </span><span class="n">Bad</span><span class="p">:</span><span class="w"> </span><span class="k">sig</span><span class="w"> </span><span class="k">eqtype</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="k">end</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r
88<span class="w"> </span><span class="k">struct</span><span class="w"></span>\r
89<span class="w"> </span><span class="k">type</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">real</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">int</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"></span>\r
90<span class="w"> </span><span class="k">end</span><span class="w"></span>\r
91</pre></div></div></div>\r
92<div class="paragraph"><p>On <span class="monospaced">structure Bad</span>, MLton reports the following error.</p></div>\r
93<div class="listingblock">\r
94<div class="content monospaced">\r
95<pre>Error: z.sml 1.16-1.34.\r
96 Type in structure disagrees with signature (admits equality): t.\r
97 structure: type 'a t = [real] * _ * _\r
98 defn at: z.sml 3.15-3.15\r
99 signature: [eqtype] 'a t\r
100 spec at: z.sml 1.30-1.30</pre>\r
101</div></div>\r
102<div class="paragraph"><p>The <span class="monospaced">structure:</span> section provides an explanation of why the type\r
103did not admit equality, highlighting the problematic component\r
104(<span class="monospaced">real</span>).</p></div>\r
105</div>\r
106</div>\r
107<div class="sect1">\r
108<h2 id="_datatype_declarations">Datatype declarations</h2>\r
109<div class="sectionbody">\r
110<div class="paragraph"><p>For a type constructor declared by a datatype declaration to admit\r
111equality, every <a href="Variant">variant</a> of the datatype must admit equality. For\r
112example, the following datatype admits equality because <span class="monospaced">bool</span> and\r
113<span class="monospaced">char * int</span> are equality types.</p></div>\r
114<div class="listingblock">\r
115<div class="content"><div class="highlight"><pre><span class="k">datatype</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">A</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">bool</span><span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">B</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">char</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">int</span><span class="w"></span>\r
116</pre></div></div></div>\r
117<div class="paragraph"><p>Nullary constructors trivially admit equality, so that the following\r
118datatype admits equality.</p></div>\r
119<div class="listingblock">\r
120<div class="content"><div class="highlight"><pre><span class="k">datatype</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">A</span><span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">B</span><span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">C</span><span class="w"></span>\r
121</pre></div></div></div>\r
122<div class="paragraph"><p>For a parameterized datatype constructor to admit equality, we\r
123consider each <a href="Variant">variant</a> as a type definition, and require that the\r
124definition admit equality. For example, for the datatype</p></div>\r
125<div class="listingblock">\r
126<div class="content"><div class="highlight"><pre><span class="k">datatype</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">A</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">bool</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">B</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"></span>\r
127</pre></div></div></div>\r
128<div class="paragraph"><p>the type definitions</p></div>\r
129<div class="listingblock">\r
130<div class="content"><div class="highlight"><pre><span class="k">type</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">tA</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">bool</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"></span>\r
131<span class="k">type</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">tB</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"></span>\r
132</pre></div></div></div>\r
133<div class="paragraph"><p>both admit equality. Thus, type constructor <span class="monospaced">t</span> admits equality.</p></div>\r
134<div class="paragraph"><p>On the other hand, the following datatype does not admit equality.</p></div>\r
135<div class="listingblock">\r
136<div class="content"><div class="highlight"><pre><span class="k">datatype</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">A</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">bool</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">B</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">real</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"></span>\r
137</pre></div></div></div>\r
138<div class="paragraph"><p>As with type definitions, we can check using an <span class="monospaced">eqtype</span>\r
139specification.</p></div>\r
140<div class="listingblock">\r
141<div class="content"><div class="highlight"><pre><span class="k">structure</span><span class="w"> </span><span class="n">Bad</span><span class="p">:</span><span class="w"> </span><span class="k">sig</span><span class="w"> </span><span class="k">eqtype</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="k">end</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r
142<span class="w"> </span><span class="k">struct</span><span class="w"></span>\r
143<span class="w"> </span><span class="k">datatype</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">A</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">bool</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">B</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">real</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"></span>\r
144<span class="w"> </span><span class="k">end</span><span class="w"></span>\r
145</pre></div></div></div>\r
146<div class="paragraph"><p>MLton reports the following error.</p></div>\r
147<div class="listingblock">\r
148<div class="content monospaced">\r
149<pre>Error: z.sml 1.16-1.34.\r
150 Type in structure disagrees with signature (admits equality): t.\r
151 structure: datatype 'a t = B of [real] * _ | ...\r
152 defn at: z.sml 3.19-3.19\r
153 signature: [eqtype] 'a t\r
154 spec at: z.sml 1.30-1.30</pre>\r
155</div></div>\r
156<div class="paragraph"><p>MLton indicates the problematic constructor (<span class="monospaced">B</span>), as well as\r
157the problematic component of the constructor&#8217;s argument.</p></div>\r
158<div class="sect2">\r
159<h3 id="_recursive_datatypes">Recursive datatypes</h3>\r
160<div class="paragraph"><p>A recursive datatype like</p></div>\r
161<div class="listingblock">\r
162<div class="content"><div class="highlight"><pre><span class="k">datatype</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">A</span><span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">B</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">int</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">t</span><span class="w"></span>\r
163</pre></div></div></div>\r
164<div class="paragraph"><p>introduces a new problem, since in order to decide whether <span class="monospaced">t</span>\r
165admits equality, we need to know for the <span class="monospaced">B</span> <a href="Variant">variant</a> whether\r
166<span class="monospaced">t</span> admits equality. The <a href="DefinitionOfStandardML">Definition</a>\r
167answers this question by requiring a type constructor to admit\r
168equality if it is consistent to do so. So, in our above example, if\r
169we assume that <span class="monospaced">t</span> admits equality, then the <a href="Variant">variant</a>\r
170<span class="monospaced">B of int * t</span> admits equality. Then, since the <span class="monospaced">A</span> <a href="Variant">variant</a>\r
171trivially admits equality, so does the type constructor <span class="monospaced">t</span>.\r
172Thus, it was consistent to assume that <span class="monospaced">t</span> admits equality, and\r
173so, <span class="monospaced">t</span> does admit equality.</p></div>\r
174<div class="paragraph"><p>On the other hand, in the following declaration</p></div>\r
175<div class="listingblock">\r
176<div class="content"><div class="highlight"><pre><span class="k">datatype</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">A</span><span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">B</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">real</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">t</span><span class="w"></span>\r
177</pre></div></div></div>\r
178<div class="paragraph"><p>if we assume that <span class="monospaced">t</span> admits equality, then the <span class="monospaced">B</span> <a href="Variant">variant</a>\r
179does not admit equality. Hence, the type constructor <span class="monospaced">t</span> does not\r
180admit equality, and our assumption was inconsistent. Hence, <span class="monospaced">t</span>\r
181does not admit equality.</p></div>\r
182<div class="paragraph"><p>The same kind of reasoning applies to mutually recursive datatypes as\r
183well. For example, the following defines both <span class="monospaced">t</span> and <span class="monospaced">u</span> to\r
184admit equality.</p></div>\r
185<div class="listingblock">\r
186<div class="content"><div class="highlight"><pre><span class="k">datatype</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">A</span><span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">B</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">u</span><span class="w"></span>\r
187<span class="k">and</span><span class="w"> </span><span class="n">u</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">C</span><span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">D</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">t</span><span class="w"></span>\r
188</pre></div></div></div>\r
189<div class="paragraph"><p>But the following defines neither <span class="monospaced">t</span> nor <span class="monospaced">u</span> to admit\r
190equality.</p></div>\r
191<div class="listingblock">\r
192<div class="content"><div class="highlight"><pre><span class="k">datatype</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">A</span><span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">B</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">u</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">real</span><span class="w"></span>\r
193<span class="k">and</span><span class="w"> </span><span class="n">u</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">C</span><span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">D</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">t</span><span class="w"></span>\r
194</pre></div></div></div>\r
195<div class="paragraph"><p>As always, we can check whether a type admits equality using an\r
196<span class="monospaced">eqtype</span> specification.</p></div>\r
197<div class="listingblock">\r
198<div class="content"><div class="highlight"><pre><span class="k">structure</span><span class="w"> </span><span class="n">Bad</span><span class="p">:</span><span class="w"> </span><span class="k">sig</span><span class="w"> </span><span class="k">eqtype</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="k">eqtype</span><span class="w"> </span><span class="n">u</span><span class="w"> </span><span class="k">end</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r
199<span class="w"> </span><span class="k">struct</span><span class="w"></span>\r
200<span class="w"> </span><span class="k">datatype</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">A</span><span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">B</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">u</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">real</span><span class="w"></span>\r
201<span class="w"> </span><span class="k">and</span><span class="w"> </span><span class="n">u</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">C</span><span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">D</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">t</span><span class="w"></span>\r
202<span class="w"> </span><span class="k">end</span><span class="w"></span>\r
203</pre></div></div></div>\r
204<div class="paragraph"><p>MLton reports the following error.</p></div>\r
205<div class="listingblock">\r
206<div class="content monospaced">\r
207<pre>Error: z.sml 1.16-1.40.\r
208 Type in structure disagrees with signature (admits equality): t.\r
209 structure: datatype t = B of [_str.u] * [real] | ...\r
210 defn at: z.sml 3.16-3.16\r
211 signature: [eqtype] t\r
212 spec at: z.sml 1.27-1.27\r
213Error: z.sml 1.16-1.40.\r
214 Type in structure disagrees with signature (admits equality): u.\r
215 structure: datatype u = D of [_str.t] | ...\r
216 defn at: z.sml 4.11-4.11\r
217 signature: [eqtype] u\r
218 spec at: z.sml 1.36-1.36</pre>\r
219</div></div>\r
220</div>\r
221</div>\r
222</div>\r
223</div>\r
224<div id="footnotes"><hr></div>\r
225<div id="footer">\r
226<div id="footer-text">\r
227</div>\r
228<div id="footer-badges">\r
229</div>\r
230</div>\r
231</body>\r
232</html>\r