doc/guide/localhost/ArrayLiteral

   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>ArrayLiteral</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>ArrayLiteral</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> does not have a syntax for array literals or
  32 vector literals.  The only way to write down an array is like</p></div>
  33 <div class="listingblock">
  34 <div class="content"><div class="highlight"><pre><span class="n">Array</span><span class="p">.</span><span class="n">fromList</span><span class="w"> </span><span class="p">[</span><span class="n">w</span><span class="p">,</span><span class="w"> </span><span class="n">x</span><span class="p">,</span><span class="w"> </span><span class="n">y</span><span class="p">,</span><span class="w"> </span><span class="n">z</span><span class="p">]</span><span class="w"></span>
  35 </pre></div></div></div>
  36 <div class="paragraph"><p>No SML compiler produces efficient code for the above expression.  The
  37 generated code allocates a list and then converts it to an array.  To
  38 alleviate this, one could write down the same array using
  39 <span class="monospaced">Array.tabulate</span>, or even using <span class="monospaced">Array.array</span> and <span class="monospaced">Array.update</span>, but
  40 that is syntactically unwieldy.</p></div>
  41 <div class="paragraph"><p>Fortunately, using <a href="Fold">Fold</a>, it is possible to define constants <span class="monospaced">A</span>,
  42 and <span class="monospaced">&grave;</span> so that one can write down an array like:</p></div>
  43 <div class="listingblock">
  44 <div class="content"><div class="highlight"><pre><span class="n">A</span><span class="w"> </span><span class="n">`w</span><span class="w"> </span><span class="n">`x</span><span class="w"> </span><span class="n">`y</span><span class="w"> </span><span class="n">`z</span><span class="w"> </span><span class="n">$</span><span class="w"></span>
  45 </pre></div></div></div>
  46 <div class="paragraph"><p>This is as syntactically concise as the <span class="monospaced">fromList</span> expression.
  47 Furthermore, MLton, at least, will generate the efficient code as if
  48 one had written down a use of <span class="monospaced">Array.array</span> followed by four uses of
  49 <span class="monospaced">Array.update</span>.</p></div>
  50 <div class="paragraph"><p>Along with <span class="monospaced">A</span> and <span class="monospaced">&grave;</span>, one can define a constant <span class="monospaced">V</span> that makes
  51 it possible to define vector literals with the same syntax, e.g.,</p></div>
  52 <div class="listingblock">
  53 <div class="content"><div class="highlight"><pre><span class="n">V</span><span class="w"> </span><span class="n">`w</span><span class="w"> </span><span class="n">`x</span><span class="w"> </span><span class="n">`y</span><span class="w"> </span><span class="n">`z</span><span class="w"> </span><span class="n">$</span><span class="w"></span>
  54 </pre></div></div></div>
  55 <div class="paragraph"><p>Note that the same element indicator, <span class="monospaced">&grave;</span>, serves for both array
  56 and vector literals.  Of course, the <span class="monospaced">$</span> is the end-of-arguments
  57 marker always used with <a href="Fold">Fold</a>.  The only difference between an
  58 array literal and vector literal is the <span class="monospaced">A</span> or <span class="monospaced">V</span> at the beginning.</p></div>
  59 <div class="paragraph"><p>Here is the implementation of <span class="monospaced">A</span>, <span class="monospaced">V</span>, and <span class="monospaced">&grave;</span>.  We place them
  60 in a structure and use signature abstraction to hide the type of the
  61 accumulator.  See <a href="Fold">Fold</a> for more on this technique.</p></div>
  62 <div class="listingblock">
  63 <div class="content"><div class="highlight"><pre><span class="k">structure</span><span class="w"> </span><span class="n">Literal</span><span class="p">:&gt;</span><span class="w"></span>
  64 <span class="w">   </span><span class="k">sig</span><span class="w"></span>
  65 <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">z</span><span class="w"></span>
  66 <span class="w">      </span><span class="k">val</span><span class="w"> </span><span class="n">A</span><span class="p">:</span><span class="w"> </span><span class="p">(</span><span class="n">&#39;a</span><span class="w"> </span><span class="n">z</span><span class="p">,</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">z</span><span class="p">,</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">array</span><span class="p">,</span><span class="w"> </span><span class="n">&#39;d</span><span class="p">)</span><span class="w"> </span><span class="n">Fold</span><span class="p">.</span><span class="n">t</span><span class="w"></span>
  67 <span class="w">      </span><span class="k">val</span><span class="w"> </span><span class="n">V</span><span class="p">:</span><span class="w"> </span><span class="p">(</span><span class="n">&#39;a</span><span class="w"> </span><span class="n">z</span><span class="p">,</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">z</span><span class="p">,</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">vector</span><span class="p">,</span><span class="w"> </span><span class="n">&#39;d</span><span class="p">)</span><span class="w"> </span><span class="n">Fold</span><span class="p">.</span><span class="n">t</span><span class="w"></span>
  68 <span class="w">      </span><span class="k">val</span><span class="w"> </span><span class="n">`</span><span class="w"> </span><span class="p">:</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;a</span><span class="w"> </span><span class="n">z</span><span class="p">,</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">z</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">&#39;c</span><span class="p">,</span><span class="w"> </span><span class="n">&#39;d</span><span class="p">)</span><span class="w"> </span><span class="n">Fold</span><span class="p">.</span><span class="n">step1</span><span class="w"></span>
  69 <span class="w">   </span><span class="k">end</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
  70 <span class="w">   </span><span class="k">struct</span><span class="w"></span>
  71 <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">z</span><span class="w"> </span><span class="p">=</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><span class="n">option</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="p">(</span><span class="n">&#39;a</span><span class="w"> </span><span class="n">array</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">unit</span><span class="p">)</span><span class="w"></span>
  72
  73 <span class="w">      </span><span class="k">val</span><span class="w"> </span><span class="n">A</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
  74 <span class="w">         </span><span class="k">fn</span><span class="w"> </span><span class="n">z</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"></span>
  75 <span class="w">         </span><span class="n">Fold</span><span class="p">.</span><span class="n">fold</span><span class="w"></span>
  76 <span class="w">         </span><span class="p">((</span><span class="mi">0</span><span class="p">,</span><span class="w"> </span><span class="n">NONE</span><span class="p">,</span><span class="w"> </span><span class="n">ignore</span><span class="p">),</span><span class="w"></span>
  77 <span class="w">          </span><span class="k">fn</span><span class="w"> </span><span class="p">(</span><span class="n">n</span><span class="p">,</span><span class="w"> </span><span class="n">opt</span><span class="p">,</span><span class="w"> </span><span class="n">fill</span><span class="p">)</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"></span>
  78 <span class="w">          </span><span class="k">case</span><span class="w"> </span><span class="n">opt</span><span class="w"> </span><span class="k">of</span><span class="w"></span>
  79 <span class="w">             </span><span class="n">NONE</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"></span>
  80 <span class="w">                </span><span class="n">Array</span><span class="p">.</span><span class="n">tabulate</span><span class="w"> </span><span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="w"> </span><span class="k">fn</span><span class="w"> </span><span class="p">_</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="k">raise</span><span class="w"> </span><span class="n">Fail</span><span class="w"> </span><span class="s">&quot;array0&quot;</span><span class="p">)</span><span class="w"></span>
  81 <span class="w">           </span><span class="p">|</span><span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"></span>
  82 <span class="w">                </span><span class="k">let</span><span class="w"></span>
  83 <span class="w">                   </span><span class="k">val</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">Array</span><span class="p">.</span><span class="n">array</span><span class="w"> </span><span class="p">(</span><span class="n">n</span><span class="p">,</span><span class="w"> </span><span class="n">x</span><span class="p">)</span><span class="w"></span>
  84 <span class="w">                   </span><span class="k">val</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">fill</span><span class="w"> </span><span class="n">a</span><span class="w"></span>
  85 <span class="w">                </span><span class="k">in</span><span class="w"></span>
  86 <span class="w">                   </span><span class="n">a</span><span class="w"></span>
  87 <span class="w">                </span><span class="k">end</span><span class="p">)</span><span class="w"></span>
  88 <span class="w">         </span><span class="n">z</span><span class="w"></span>
  89
  90 <span class="w">      </span><span class="k">val</span><span class="w"> </span><span class="n">V</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">fn</span><span class="w"> </span><span class="n">z</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">Fold</span><span class="p">.</span><span class="n">post</span><span class="w"> </span><span class="p">(</span><span class="n">A</span><span class="p">,</span><span class="w"> </span><span class="n">Array</span><span class="p">.</span><span class="n">vector</span><span class="p">)</span><span class="w"> </span><span class="n">z</span><span class="w"></span>
  91
  92 <span class="w">      </span><span class="k">val</span><span class="w"> </span><span class="n">`</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
  93 <span class="w">         </span><span class="k">fn</span><span class="w"> </span><span class="n">z</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"></span>
  94 <span class="w">         </span><span class="n">Fold</span><span class="p">.</span><span class="n">step1</span><span class="w"></span>
  95 <span class="w">         </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="w"> </span><span class="p">(</span><span class="n">i</span><span class="p">,</span><span class="w"> </span><span class="n">opt</span><span class="p">,</span><span class="w"> </span><span class="n">fill</span><span class="p">))</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"></span>
  96 <span class="w">          </span><span class="p">(</span><span class="n">i</span><span class="w"> </span><span class="n">+</span><span class="w"> </span><span class="mi">1</span><span class="p">,</span><span class="w"></span>
  97 <span class="w">           </span><span class="n">SOME</span><span class="w"> </span><span class="n">x</span><span class="p">,</span><span class="w"></span>
  98 <span class="w">           </span><span class="k">fn</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="p">(</span><span class="n">Array</span><span class="p">.</span><span class="n">update</span><span class="w"> </span><span class="p">(</span><span class="n">a</span><span class="p">,</span><span class="w"> </span><span class="n">i</span><span class="p">,</span><span class="w"> </span><span class="n">x</span><span class="p">);</span><span class="w"> </span><span class="n">fill</span><span class="w"> </span><span class="n">a</span><span class="p">)))</span><span class="w"></span>
  99 <span class="w">         </span><span class="n">z</span><span class="w"></span>
 100 <span class="w">   </span><span class="k">end</span><span class="w"></span>
 101 </pre></div></div></div>
 102 <div class="paragraph"><p>The idea of the code is for the fold to accumulate a count of the
 103 number of elements, a sample element, and a function that fills in all
 104 the elements.  When the fold is complete, the finishing function
 105 allocates the array, applies the fill function, and returns the array.
 106 The only difference between <span class="monospaced">A</span> and <span class="monospaced">V</span> is at the very end; <span class="monospaced">A</span> just
 107 returns the array, while <span class="monospaced">V</span> converts it to a vector using
 108 post-composition, which is further described on the <a href="Fold">Fold</a> page.</p></div>
 109 </div>
 110 </div>
 111 </div>
 112 <div id="footnotes"><hr></div>
 113 <div id="footer">
 114 <div id="footer-text">
 115 </div>
 116 <div id="footer-badges">
 117 </div>
 118 </div>
 119 </body>
 120 </html>