doc/guide/localhost/ProductType

   1 <!DOCTYPE html>
   2 <html lang="en">
   3 <head>
   4 <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
   5 <meta name="generator" content="AsciiDoc 8.6.9">
   6 <title>ProductType</title>
   7 <link rel="stylesheet" href="./asciidoc.css" type="text/css">
   8 <link rel="stylesheet" href="./pygments.css" type="text/css">
   9
  10
  11 <script type="text/javascript" src="./asciidoc.js"></script>
  12 <script type="text/javascript">
  13 /*<![CDATA[*/
  14 asciidoc.install();
  15 /*]]>*/
  16 </script>
  17 <link rel="stylesheet" href="./mlton.css" type="text/css">
  18 </head>
  19 <body class="article">
  20 <div id="banner">
  21 <div id="banner-home">
  22 <a href="./Home">MLton 20180207</a>
  23 </div>
  24 </div>
  25 <div id="header">
  26 <h1>ProductType</h1>
  27 </div>
  28 <div id="content">
  29 <div id="preamble">
  30 <div class="sectionbody">
  31 <div class="paragraph"><p><a href="StandardML">Standard ML</a> has special syntax for products (tuples). A
  32 product type is written as</p></div>
  33 <div class="listingblock">
  34 <div class="content"><div class="highlight"><pre><span class="n">t1</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">t2</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">tN</span><span class="w"></span>
  35 </pre></div></div></div>
  36 <div class="paragraph"><p>and a product pattern is written as</p></div>
  37 <div class="listingblock">
  38 <div class="content"><div class="highlight"><pre><span class="p">(</span><span class="n">p1</span><span class="p">,</span><span class="w"> </span><span class="n">p2</span><span class="p">,</span><span class="w"> </span><span class="p">...,</span><span class="w"> </span><span class="n">pN</span><span class="p">)</span><span class="w"></span>
  39 </pre></div></div></div>
  40 <div class="paragraph"><p>In most situations the syntax is quite convenient.  However, there are
  41 situations where the syntax is cumbersome.  There are also situations
  42 in which it is useful to construct and destruct n-ary products
  43 inductively, especially when using <a href="Fold">Fold</a>.</p></div>
  44 <div class="paragraph"><p>In such situations, it is useful to have a binary product datatype
  45 with an infix constructor defined as follows.</p></div>
  46 <div class="listingblock">
  47 <div class="content"><div class="highlight"><pre><span class="k">datatype</span><span class="w"> </span><span class="p">(</span><span class="n">&#39;a</span><span class="p">,</span><span class="w"> </span><span class="n">&#39;b</span><span class="p">)</span><span class="w"> </span><span class="n">product</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">&amp;</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">&#39;b</span><span class="w"></span>
  48 <span class="k">infix</span><span class="w"> </span><span class="n">&amp;</span><span class="w"></span>
  49 </pre></div></div></div>
  50 <div class="paragraph"><p>With these definitions, one can write an n-ary product as a nested
  51 binary product quite conveniently.</p></div>
  52 <div class="listingblock">
  53 <div class="content"><div class="highlight"><pre><span class="n">x1</span><span class="w"> </span><span class="n">&amp;</span><span class="w"> </span><span class="n">x2</span><span class="w"> </span><span class="n">&amp;</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="n">&amp;</span><span class="w"> </span><span class="n">xn</span><span class="w"></span>
  54 </pre></div></div></div>
  55 <div class="paragraph"><p>Because of left associativity, this is the same as</p></div>
  56 <div class="listingblock">
  57 <div class="content"><div class="highlight"><pre><span class="p">(((</span><span class="n">x1</span><span class="w"> </span><span class="n">&amp;</span><span class="w"> </span><span class="n">x2</span><span class="p">)</span><span class="w"> </span><span class="n">&amp;</span><span class="w"> </span><span class="p">...)</span><span class="w"> </span><span class="n">&amp;</span><span class="w"> </span><span class="n">xn</span><span class="p">)</span><span class="w"></span>
  58 </pre></div></div></div>
  59 <div class="paragraph"><p>Because <span class="monospaced">&amp;</span> is a constructor, the syntax can also be used for
  60 patterns.</p></div>
  61 <div class="paragraph"><p>The symbol <span class="monospaced">&amp;</span> is inspired by the Curry-Howard isomorphism: the proof
  62 of a conjunction <span class="monospaced">(A &amp; B)</span> is a pair of proofs <span class="monospaced">(a, b)</span>.</p></div>
  63 </div>
  64 </div>
  65 <div class="sect1">
  66 <h2 id="_example_parser_combinators">Example: parser combinators</h2>
  67 <div class="sectionbody">
  68 <div class="paragraph"><p>A typical parser combinator library provides a combinator that has a
  69 type of the form.</p></div>
  70 <div class="listingblock">
  71 <div class="content"><div class="highlight"><pre><span class="n">&#39;a</span><span class="w"> </span><span class="n">parser</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">&#39;b</span><span class="w"> </span><span class="n">parser</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="p">(</span><span class="n">&#39;a</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">&#39;b</span><span class="p">)</span><span class="w"> </span><span class="n">parser</span><span class="w"></span>
  72 </pre></div></div></div>
  73 <div class="paragraph"><p>and produces a parser for the concatenation of two parsers. When more
  74 than two parsers are concatenated, the result of the resulting parser
  75 is a nested structure of pairs</p></div>
  76 <div class="listingblock">
  77 <div class="content"><div class="highlight"><pre><span class="p">(...((</span><span class="n">p1</span><span class="p">,</span><span class="w"> </span><span class="n">p2</span><span class="p">),</span><span class="w"> </span><span class="n">p3</span><span class="p">)...,</span><span class="w"> </span><span class="n">pN</span><span class="p">)</span><span class="w"></span>
  78 </pre></div></div></div>
  79 <div class="paragraph"><p>which is somewhat cumbersome.</p></div>
  80 <div class="paragraph"><p>By using a product type, the type of the concatenation combinator then
  81 becomes</p></div>
  82 <div class="listingblock">
  83 <div class="content"><div class="highlight"><pre><span class="n">&#39;a</span><span class="w"> </span><span class="n">parser</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">&#39;b</span><span class="w"> </span><span class="n">parser</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="p">(</span><span class="n">&#39;a</span><span class="p">,</span><span class="w"> </span><span class="n">&#39;b</span><span class="p">)</span><span class="w"> </span><span class="n">product</span><span class="w"> </span><span class="n">parser</span><span class="w"></span>
  84 </pre></div></div></div>
  85 <div class="paragraph"><p>While this doesn&#8217;t stop the nesting, it makes the pattern significantly
  86 easier to write. Instead of</p></div>
  87 <div class="listingblock">
  88 <div class="content"><div class="highlight"><pre><span class="p">(...((</span><span class="n">p1</span><span class="p">,</span><span class="w"> </span><span class="n">p2</span><span class="p">),</span><span class="w"> </span><span class="n">p3</span><span class="p">)...,</span><span class="w"> </span><span class="n">pN</span><span class="p">)</span><span class="w"></span>
  89 </pre></div></div></div>
  90 <div class="paragraph"><p>the pattern is written as</p></div>
  91 <div class="listingblock">
  92 <div class="content"><div class="highlight"><pre><span class="n">p1</span><span class="w"> </span><span class="n">&amp;</span><span class="w"> </span><span class="n">p2</span><span class="w"> </span><span class="n">&amp;</span><span class="w"> </span><span class="n">p3</span><span class="w"> </span><span class="n">&amp;</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="n">&amp;</span><span class="w"> </span><span class="n">pN</span><span class="w"></span>
  93 </pre></div></div></div>
  94 <div class="paragraph"><p>which is considerably more concise.</p></div>
  95 </div>
  96 </div>
  97 <div class="sect1">
  98 <h2 id="_also_see">Also see</h2>
  99 <div class="sectionbody">
 100 <div class="ulist"><ul>
 101 <li>
 102 <p>
 103 <a href="VariableArityPolymorphism">VariableArityPolymorphism</a>
 104 </p>
 105 </li>
 106 <li>
 107 <p>
 108 <a href="Utilities">Utilities</a>
 109 </p>
 110 </li>
 111 </ul></div>
 112 </div>
 113 </div>
 114 </div>
 115 <div id="footnotes"><hr></div>
 116 <div id="footer">
 117 <div id="footer-text">
 118 </div>
 119 <div id="footer-badges">
 120 </div>
 121 </div>
 122 </body>
 123 </html>