1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
|
<!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>ProductType - 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%;">
ProductType
<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 href="StandardML">Standard ML</a> has special syntax for products (tuples). A product type is written as
<pre>t1 * t2 * ... * tN
</pre> and a product pattern is written as
<pre>(p1, p2, ..., pN)
</pre><p>
In most situations the syntax is quite convenient. However, there are situations where the syntax is cumbersome. There are also situations in which it is useful to construct and destruct n-ary products inductively, especially when using <a href="Fold">Fold</a>.
</p>
<p>
In such situations, it is useful to have a binary product datatype with an infix constructor defined as follows.
<pre class=code>
<B><FONT COLOR="#A020F0">datatype</FONT></B><B><FONT COLOR="#228B22"> ('a, 'b) product </FONT></B>=<B><FONT COLOR="#228B22"> <FONT COLOR="#B8860B">&</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> 'a * 'b
</FONT></B><B><FONT COLOR="#A020F0">infix</FONT></B> &
</PRE>
</p>
<p>
With these definitions, one can write an n-ary product as a nested binary product quite conveniently.
<pre>x1 & x2 & ... & xn
</pre>
</p>
<p>
Because of left associativity, this is the same as
<pre>(((x1 & x2) & ...) & xn)
</pre>
</p>
<p>
Because <tt>&</tt> is a constructor, the syntax can also be used for patterns.
</p>
<p>
The symbol <tt>&</tt> is inspired by the Curry-Howard isomorphism: the proof of a conjunction <tt>(A & B)</tt> is a pair of proofs <tt>(a, b)</tt>.
</p>
<h2 id="head-058073812447f89d85b57e47ba6958fee7a17440">Example: parser combinators</h2>
<p>
A typical parser combinator library provides a combinator that has a type of the form.
</p>
<pre>'a parser * 'b parser -> ('a * 'b) parser
</pre><p>
and produces a parser for the concatenation of two parsers. When more than two parsers are concatenated, the result of the resulting parser is a nested structure of pairs
</p>
<pre>(...((p1, p2), p3)..., pN)
</pre><p>
which is somewhat cumbersome.
</p>
<p>
By using a product type, the type of the concatenation combinator then becomes
</p>
<pre>'a parser * 'b parser -> ('a, 'b) product parser
</pre><p>
While this doesn't stop the nesting, it makes the pattern significantly easier to write. Instead of
</p>
<pre>(...((p1, p2), p3)..., pN)
</pre>the pattern is written as
<pre>p1 & p2 & p3 & ... & pN
</pre>which is considerably more concise. <h2 id="head-a4bc8bf5caf54b18cea9f58e83dd4acb488deb17">Also see</h2>
<ul>
<li>
<p>
<a href="VariableArityPolymorphism">VariableArityPolymorphism</a>
</p>
</li>
<li>
<p>
<a href="Utilities">Utilities</a>
</p>
</li>
</ul>
</div>
<p>
<hr>
Last edited on 2007-08-26 19:59:19 by <span title="c-71-57-91-146.hsd1.il.comcast.net"><a href="MatthewFluet">MatthewFluet</a></span>.
</body></html>
|
