doc/guide/localhost/ForLoops

   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>ForLoops</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>ForLoops</h1>
  27 </div>
  28 <div id="content">
  29 <div id="preamble">
  30 <div class="sectionbody">
  31 <div class="paragraph"><p>A <span class="monospaced">for</span>-loop is typically used to iterate over a range of consecutive
  32 integers that denote indices of some sort.  For example, in <a href="OCaml">OCaml</a>
  33 a <span class="monospaced">for</span>-loop takes either the form</p></div>
  34 <div class="listingblock">
  35 <div class="content monospaced">
  36 <pre>for &lt;name&gt; = &lt;lower&gt; to &lt;upper&gt; do &lt;body&gt; done</pre>
  37 </div></div>
  38 <div class="paragraph"><p>or the form</p></div>
  39 <div class="listingblock">
  40 <div class="content monospaced">
  41 <pre>for &lt;name&gt; = &lt;upper&gt; downto &lt;lower&gt; do &lt;body&gt; done</pre>
  42 </div></div>
  43 <div class="paragraph"><p>Some languages provide considerably more flexible <span class="monospaced">for</span>-loop or
  44 <span class="monospaced">foreach</span>-constructs.</p></div>
  45 <div class="paragraph"><p>A bit surprisingly, <a href="StandardML">Standard ML</a> provides special syntax
  46 for <span class="monospaced">while</span>-loops, but not for <span class="monospaced">for</span>-loops.  Indeed, in SML, many uses
  47 of <span class="monospaced">for</span>-loops are better expressed using <span class="monospaced">app</span>, <span class="monospaced">foldl</span>/<span class="monospaced">foldr</span>,
  48 <span class="monospaced">map</span> and many other higher-order functions provided by the
  49 <a href="BasisLibrary">Basis Library</a> for manipulating lists, vectors and
  50 arrays.  However, the Basis Library does not provide a function for
  51 iterating over a range of integer values.  Fortunately, it is very
  52 easy to write one.</p></div>
  53 </div>
  54 </div>
  55 <div class="sect1">
  56 <h2 id="_a_fairly_simple_design">A fairly simple design</h2>
  57 <div class="sectionbody">
  58 <div class="paragraph"><p>The following implementation imitates both the syntax and semantics of
  59 the OCaml <span class="monospaced">for</span>-loop.</p></div>
  60 <div class="listingblock">
  61 <div class="content"><div class="highlight"><pre><span class="k">datatype</span><span class="w"> </span><span class="n">for</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">to</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">int</span><span class="w"></span>
  62 <span class="w">             </span><span class="p">|</span><span class="w"> </span><span class="n">downto</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">int</span><span class="w"></span>
  63
  64 <span class="k">infix</span><span class="w"> </span><span class="n">to</span><span class="w"> </span><span class="n">downto</span><span class="w"></span>
  65
  66 <span class="k">val</span><span class="w"> </span><span class="n">for</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
  67 <span class="w">    </span><span class="k">fn</span><span class="w"> </span><span class="n">lo</span><span class="w"> </span><span class="n">to</span><span class="w"> </span><span class="n">up</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"></span>
  68 <span class="w">       </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="k">let</span><span class="w"> </span><span class="k">fun</span><span class="w"> </span><span class="n">loop</span><span class="w"> </span><span class="n">lo</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="n">lo</span><span class="w"> </span><span class="n">&gt;</span><span class="w"> </span><span class="n">up</span><span class="w"> </span><span class="k">then</span><span class="w"> </span><span class="p">()</span><span class="w"></span>
  69 <span class="w">                                  </span><span class="k">else</span><span class="w"> </span><span class="p">(</span><span class="n">f</span><span class="w"> </span><span class="n">lo</span><span class="p">;</span><span class="w"> </span><span class="n">loop</span><span class="w"> </span><span class="p">(</span><span class="n">lo+</span><span class="mi">1</span><span class="p">))</span><span class="w"></span>
  70 <span class="w">                </span><span class="k">in</span><span class="w"> </span><span class="n">loop</span><span class="w"> </span><span class="n">lo</span><span class="w"> </span><span class="k">end</span><span class="p">)</span><span class="w"></span>
  71 <span class="w">     </span><span class="p">|</span><span class="w"> </span><span class="n">up</span><span class="w"> </span><span class="n">downto</span><span class="w"> </span><span class="n">lo</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"></span>
  72 <span class="w">       </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="k">let</span><span class="w"> </span><span class="k">fun</span><span class="w"> </span><span class="n">loop</span><span class="w"> </span><span class="n">up</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="n">up</span><span class="w"> </span><span class="n">&lt;</span><span class="w"> </span><span class="n">lo</span><span class="w"> </span><span class="k">then</span><span class="w"> </span><span class="p">()</span><span class="w"></span>
  73 <span class="w">                                  </span><span class="k">else</span><span class="w"> </span><span class="p">(</span><span class="n">f</span><span class="w"> </span><span class="n">up</span><span class="p">;</span><span class="w"> </span><span class="n">loop</span><span class="w"> </span><span class="p">(</span><span class="n">up-</span><span class="mi">1</span><span class="p">))</span><span class="w"></span>
  74 <span class="w">                </span><span class="k">in</span><span class="w"> </span><span class="n">loop</span><span class="w"> </span><span class="n">up</span><span class="w"> </span><span class="k">end</span><span class="p">)</span><span class="w"></span>
  75 </pre></div></div></div>
  76 <div class="paragraph"><p>For example,</p></div>
  77 <div class="listingblock">
  78 <div class="content"><div class="highlight"><pre><span class="n">for</span><span class="w"> </span><span class="p">(</span><span class="mi">1</span><span class="w"> </span><span class="n">to</span><span class="w"> </span><span class="mi">9</span><span class="p">)</span><span class="w"></span>
  79 <span class="w">    </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">i</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">print</span><span class="w"> </span><span class="p">(</span><span class="n">Int</span><span class="p">.</span><span class="n">toString</span><span class="w"> </span><span class="n">i</span><span class="p">))</span><span class="w"></span>
  80 </pre></div></div></div>
  81 <div class="paragraph"><p>would print <span class="monospaced">123456789</span> and</p></div>
  82 <div class="listingblock">
  83 <div class="content"><div class="highlight"><pre><span class="n">for</span><span class="w"> </span><span class="p">(</span><span class="mi">9</span><span class="w"> </span><span class="n">downto</span><span class="w"> </span><span class="mi">1</span><span class="p">)</span><span class="w"></span>
  84 <span class="w">    </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">i</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">print</span><span class="w"> </span><span class="p">(</span><span class="n">Int</span><span class="p">.</span><span class="n">toString</span><span class="w"> </span><span class="n">i</span><span class="p">))</span><span class="w"></span>
  85 </pre></div></div></div>
  86 <div class="paragraph"><p>would print <span class="monospaced">987654321</span>.</p></div>
  87 <div class="paragraph"><p>Straightforward formatting of nested loops</p></div>
  88 <div class="listingblock">
  89 <div class="content"><div class="highlight"><pre><span class="n">for</span><span class="w"> </span><span class="p">(</span><span class="n">a</span><span class="w"> </span><span class="n">to</span><span class="w"> </span><span class="n">b</span><span class="p">)</span><span class="w"></span>
  90 <span class="w">    </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">i</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"></span>
  91 <span class="w">        </span><span class="n">for</span><span class="w"> </span><span class="p">(</span><span class="n">c</span><span class="w"> </span><span class="n">to</span><span class="w"> </span><span class="n">d</span><span class="p">)</span><span class="w"></span>
  92 <span class="w">            </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">j</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"></span>
  93 <span class="w">                </span><span class="p">...))</span><span class="w"></span>
  94 </pre></div></div></div>
  95 <div class="paragraph"><p>is fairly readable, but tends to cause the body of the loop to be
  96 indented quite deeply.</p></div>
  97 </div>
  98 </div>
  99 <div class="sect1">
 100 <h2 id="_off_by_one">Off-by-one</h2>
 101 <div class="sectionbody">
 102 <div class="paragraph"><p>The above design has an annoying feature.  In practice, the upper
 103 bound of the iterated range is almost always excluded and most loops
 104 would subtract one from the upper bound:</p></div>
 105 <div class="listingblock">
 106 <div class="content"><div class="highlight"><pre><span class="n">for</span><span class="w"> </span><span class="p">(</span><span class="mi">0</span><span class="w"> </span><span class="n">to</span><span class="w"> </span><span class="n">n-</span><span class="mi">1</span><span class="p">)</span><span class="w"> </span><span class="p">...</span><span class="w"></span>
 107 <span class="n">for</span><span class="w"> </span><span class="p">(</span><span class="n">n-</span><span class="mi">1</span><span class="w"> </span><span class="n">downto</span><span class="w"> </span><span class="mi">0</span><span class="p">)</span><span class="w"> </span><span class="p">...</span><span class="w"></span>
 108 </pre></div></div></div>
 109 <div class="paragraph"><p>It is probably better to break convention and exclude the upper bound
 110 by default, because it leads to more concise code and becomes
 111 idiomatic with very little practice.  The iterator combinators
 112 described below exclude the upper bound by default.</p></div>
 113 </div>
 114 </div>
 115 <div class="sect1">
 116 <h2 id="_iterator_combinators">Iterator combinators</h2>
 117 <div class="sectionbody">
 118 <div class="paragraph"><p>While the simple <span class="monospaced">for</span>-function described in the previous section is
 119 probably good enough for many uses, it is a bit cumbersome when one
 120 needs to iterate over a Cartesian product.  One might also want to
 121 iterate over more than just consecutive integers.  It turns out that
 122 one can provide a library of iterator combinators that allow one to
 123 implement iterators more flexibly.</p></div>
 124 <div class="paragraph"><p>Since the types of the combinators may be a bit difficult to infer
 125 from their implementations, let&#8217;s first take a look at a signature of
 126 the iterator combinator library:</p></div>
 127 <div class="listingblock">
 128 <div class="content"><div class="highlight"><pre><span class="k">signature</span><span class="w"> </span><span class="n">ITER</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
 129 <span class="w">  </span><span class="k">sig</span><span class="w"></span>
 130 <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="p">(</span><span class="n">&#39;a</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><span class="p">-&gt;</span><span class="w"> </span><span class="n">unit</span><span class="w"></span>
 131
 132 <span class="w">    </span><span class="k">val</span><span class="w"> </span><span class="n">return</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 133 <span class="w">    </span><span class="k">val</span><span class="w"> </span><span class="n">&gt;&gt;=</span><span class="w"> </span><span class="p">:</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="n">*</span><span class="w"> </span><span class="p">(</span><span class="n">&#39;a</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;b</span><span class="w"> </span><span class="n">t</span><span class="p">)</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;b</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 134
 135 <span class="w">    </span><span class="k">val</span><span class="w"> </span><span class="n">none</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 136
 137 <span class="w">    </span><span class="k">val</span><span class="w"> </span><span class="n">to</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">int</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">int</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 138 <span class="w">    </span><span class="k">val</span><span class="w"> </span><span class="n">downto</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">int</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">int</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 139
 140 <span class="w">    </span><span class="k">val</span><span class="w"> </span><span class="n">inList</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">list</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 141 <span class="w">    </span><span class="k">val</span><span class="w"> </span><span class="n">inVector</span><span class="w"> </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="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 142 <span class="w">    </span><span class="k">val</span><span class="w"> </span><span class="n">inArray</span><span class="w"> </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="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 143
 144 <span class="w">    </span><span class="k">val</span><span class="w"> </span><span class="n">using</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;b</span><span class="p">)</span><span class="w"> </span><span class="n">StringCvt</span><span class="p">.</span><span class="n">reader</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;b</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 145
 146 <span class="w">    </span><span class="k">val</span><span class="w"> </span><span class="n">when</span><span class="w"> </span><span class="p">:</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="n">*</span><span class="w"> </span><span class="p">(</span><span class="n">&#39;a</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">bool</span><span class="p">)</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 147 <span class="w">    </span><span class="k">val</span><span class="w"> </span><span class="n">by</span><span class="w"> </span><span class="p">:</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="n">*</span><span class="w"> </span><span class="p">(</span><span class="n">&#39;a</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;b</span><span class="p">)</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;b</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 148 <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="n">&#39;a</span><span class="w"> </span><span class="n">t</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">t</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 149 <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="n">&#39;a</span><span class="w"> </span><span class="n">t</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">t</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">t</span><span class="w"></span>
 150
 151 <span class="w">    </span><span class="k">val</span><span class="w"> </span><span class="n">for</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"></span>
 152 <span class="w">  </span><span class="k">end</span><span class="w"></span>
 153 </pre></div></div></div>
 154 <div class="paragraph"><p>Several of the above combinators are meant to be used as infix
 155 operators.  Here is a set of suitable infix declarations:</p></div>
 156 <div class="listingblock">
 157 <div class="content"><div class="highlight"><pre><span class="k">infix</span><span class="w"> </span><span class="mi">2</span><span class="w"> </span><span class="n">to</span><span class="w"> </span><span class="n">downto</span><span class="w"></span>
 158 <span class="k">infix</span><span class="w"> </span><span class="mi">1</span><span class="w"> </span><span class="n">@@</span><span class="w"> </span><span class="n">when</span><span class="w"> </span><span class="n">by</span><span class="w"></span>
 159 <span class="k">infix</span><span class="w"> </span><span class="mi">0</span><span class="w"> </span><span class="n">&gt;&gt;=</span><span class="w"> </span><span class="n">**</span><span class="w"></span>
 160 </pre></div></div></div>
 161 <div class="paragraph"><p>A few notes are in order:</p></div>
 162 <div class="ulist"><ul>
 163 <li>
 164 <p>
 165 The <span class="monospaced">'a t</span> type constructor with the <span class="monospaced">return</span> and <span class="monospaced">&gt;&gt;=</span> operators forms a monad.
 166 </p>
 167 </li>
 168 <li>
 169 <p>
 170 The <span class="monospaced">to</span> and <span class="monospaced">downto</span> combinators will omit the upper bound of the range.
 171 </p>
 172 </li>
 173 <li>
 174 <p>
 175 <span class="monospaced">for</span> is the identity function.  It is purely for syntactic sugar and is not strictly required.
 176 </p>
 177 </li>
 178 <li>
 179 <p>
 180 The <span class="monospaced">@@</span> combinator produces an iterator for the concatenation of the given iterators.
 181 </p>
 182 </li>
 183 <li>
 184 <p>
 185 The <span class="monospaced">**</span> combinator produces an iterator for the Cartesian product of the given iterators.
 186 </p>
 187 <div class="ulist"><ul>
 188 <li>
 189 <p>
 190 See <a href="ProductType">ProductType</a> for the type constructor <span class="monospaced">('a, 'b) product</span> used in the type of the iterator produced by <span class="monospaced">**</span>.
 191 </p>
 192 </li>
 193 </ul></div>
 194 </li>
 195 <li>
 196 <p>
 197 The <span class="monospaced">using</span> combinator allows one to iterate over slices, streams and many other kinds of sequences.
 198 </p>
 199 </li>
 200 <li>
 201 <p>
 202 <span class="monospaced">when</span> is the filtering combinator.  The name <span class="monospaced">when</span> is   inspired by <a href="OCaml">OCaml</a>'s guard clauses.
 203 </p>
 204 </li>
 205 <li>
 206 <p>
 207 <span class="monospaced">by</span> is the mapping combinator.
 208 </p>
 209 </li>
 210 </ul></div>
 211 <div class="paragraph"><p>The below implementation of the <span class="monospaced">ITER</span>-signature makes use of the
 212 following basic combinators:</p></div>
 213 <div class="listingblock">
 214 <div class="content"><div class="highlight"><pre><span class="k">fun</span><span class="w"> </span><span class="n">const</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="p">_</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">x</span><span class="w"></span>
 215 <span class="k">fun</span><span class="w"> </span><span class="n">flip</span><span class="w"> </span><span class="n">f</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="p">=</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="n">y</span><span class="w"> </span><span class="n">x</span><span class="w"></span>
 216 <span class="k">fun</span><span class="w"> </span><span class="n">id</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">x</span><span class="w"></span>
 217 <span class="k">fun</span><span class="w"> </span><span class="n">opt</span><span class="w"> </span><span class="n">fno</span><span class="w"> </span><span class="n">fso</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">NONE</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">fno</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="n">?</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">fso</span><span class="w"> </span><span class="n">?</span><span class="w"></span>
 218 <span class="k">fun</span><span class="w"> </span><span class="n">pass</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="n">x</span><span class="w"></span>
 219 </pre></div></div></div>
 220 <div class="paragraph"><p>Here is an implementation the <span class="monospaced">ITER</span>-signature:</p></div>
 221 <div class="listingblock">
 222 <div class="content"><div class="highlight"><pre><span class="k">structure</span><span class="w"> </span><span class="n">Iter</span><span class="w"> </span><span class="p">:&gt;</span><span class="w"> </span><span class="n">ITER</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
 223 <span class="w">  </span><span class="k">struct</span><span class="w"></span>
 224 <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="p">(</span><span class="n">&#39;a</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><span class="p">-&gt;</span><span class="w"> </span><span class="n">unit</span><span class="w"></span>
 225
 226 <span class="w">    </span><span class="k">val</span><span class="w"> </span><span class="n">return</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">pass</span><span class="w"></span>
 227 <span class="w">    </span><span class="k">fun</span><span class="w"> </span><span class="p">(</span><span class="n">iA</span><span class="w"> </span><span class="n">&gt;&gt;=</span><span class="w"> </span><span class="n">a2iB</span><span class="p">)</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">iA</span><span class="w"> </span><span class="p">(</span><span class="n">flip</span><span class="w"> </span><span class="n">a2iB</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"></span>
 228
 229 <span class="w">    </span><span class="k">val</span><span class="w"> </span><span class="n">none</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">ignore</span><span class="w"></span>
 230
 231 <span class="w">    </span><span class="k">fun</span><span class="w"> </span><span class="p">(</span><span class="n">l</span><span class="w"> </span><span class="n">to</span><span class="w"> </span><span class="n">u</span><span class="p">)</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">let</span><span class="w"> </span><span class="k">fun</span><span class="w"> </span><span class="n">`l</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="n">l&lt;u</span><span class="w"> </span><span class="k">then</span><span class="w"> </span><span class="p">(</span><span class="n">f</span><span class="w"> </span><span class="n">l</span><span class="p">;</span><span class="w"> </span><span class="n">`</span><span class="p">(</span><span class="n">l+</span><span class="mi">1</span><span class="p">))</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">`l</span><span class="w"> </span><span class="k">end</span><span class="w"></span>
 232 <span class="w">    </span><span class="k">fun</span><span class="w"> </span><span class="p">(</span><span class="n">u</span><span class="w"> </span><span class="n">downto</span><span class="w"> </span><span class="n">l</span><span class="p">)</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">let</span><span class="w"> </span><span class="k">fun</span><span class="w"> </span><span class="n">`u</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="n">u&gt;l</span><span class="w"> </span><span class="k">then</span><span class="w"> </span><span class="p">(</span><span class="n">f</span><span class="w"> </span><span class="p">(</span><span class="n">u-</span><span class="mi">1</span><span class="p">);</span><span class="w"> </span><span class="n">`</span><span class="p">(</span><span class="n">u-</span><span class="mi">1</span><span class="p">))</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">`u</span><span class="w"> </span><span class="k">end</span><span class="w"></span>
 233
 234 <span class="w">    </span><span class="k">fun</span><span class="w"> </span><span class="n">inList</span><span class="w"> </span><span class="n">?</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">flip</span><span class="w"> </span><span class="n">List</span><span class="p">.</span><span class="n">app</span><span class="w"> </span><span class="n">?</span><span class="w"></span>
 235 <span class="w">    </span><span class="k">fun</span><span class="w"> </span><span class="n">inVector</span><span class="w"> </span><span class="n">?</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">flip</span><span class="w"> </span><span class="n">Vector</span><span class="p">.</span><span class="n">app</span><span class="w"> </span><span class="n">?</span><span class="w"></span>
 236 <span class="w">    </span><span class="k">fun</span><span class="w"> </span><span class="n">inArray</span><span class="w"> </span><span class="n">?</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">flip</span><span class="w"> </span><span class="n">Array</span><span class="p">.</span><span class="n">app</span><span class="w"> </span><span class="n">?</span><span class="w"></span>
 237
 238 <span class="w">    </span><span class="k">fun</span><span class="w"> </span><span class="n">using</span><span class="w"> </span><span class="n">get</span><span class="w"> </span><span class="n">s</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">let</span><span class="w"> </span><span class="k">fun</span><span class="w"> </span><span class="n">`s</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">opt</span><span class="w"> </span><span class="p">(</span><span class="n">const</span><span class="w"> </span><span class="p">())</span><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="n">s</span><span class="p">)</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="p">(</span><span class="n">f</span><span class="w"> </span><span class="n">x</span><span class="p">;</span><span class="w"> </span><span class="n">`s</span><span class="p">))</span><span class="w"> </span><span class="p">(</span><span class="n">get</span><span class="w"> </span><span class="n">s</span><span class="p">)</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">`s</span><span class="w"> </span><span class="k">end</span><span class="w"></span>
 239
 240 <span class="w">    </span><span class="k">fun</span><span class="w"> </span><span class="p">(</span><span class="n">iA</span><span class="w"> </span><span class="n">when</span><span class="w"> </span><span class="n">p</span><span class="p">)</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">iA</span><span class="w"> </span><span class="p">(</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="k">if</span><span class="w"> </span><span class="n">p</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="k">then</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="p">())</span><span class="w"></span>
 241 <span class="w">    </span><span class="k">fun</span><span class="w"> </span><span class="p">(</span><span class="n">iA</span><span class="w"> </span><span class="n">by</span><span class="w"> </span><span class="n">g</span><span class="p">)</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">iA</span><span class="w"> </span><span class="p">(</span><span class="n">f</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">g</span><span class="p">)</span><span class="w"></span>
 242 <span class="w">    </span><span class="k">fun</span><span class="w"> </span><span class="p">(</span><span class="n">iA</span><span class="w"> </span><span class="n">@@</span><span class="w"> </span><span class="n">iB</span><span class="p">)</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="p">(</span><span class="n">iA</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">unit</span><span class="p">;</span><span class="w"> </span><span class="n">iB</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"></span>
 243 <span class="w">    </span><span class="k">fun</span><span class="w"> </span><span class="p">(</span><span class="n">iA</span><span class="w"> </span><span class="n">**</span><span class="w"> </span><span class="n">iB</span><span class="p">)</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">iA</span><span class="w"> </span><span class="p">(</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="n">iB</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">b</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">(</span><span class="n">a</span><span class="w"> </span><span class="n">&amp;</span><span class="w"> </span><span class="n">b</span><span class="p">)))</span><span class="w"></span>
 244
 245 <span class="w">    </span><span class="k">val</span><span class="w"> </span><span class="n">for</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">id</span><span class="w"></span>
 246 <span class="w">  </span><span class="k">end</span><span class="w"></span>
 247 </pre></div></div></div>
 248 <div class="paragraph"><p>Note that some of the above combinators (e.g. <span class="monospaced">**</span>) could be expressed
 249 in terms of the other combinators, most notably <span class="monospaced">return</span> and <span class="monospaced">&gt;&gt;=</span>.
 250 Another implementation issue worth mentioning is that <span class="monospaced">downto</span> is
 251 written specifically to avoid computing <span class="monospaced">l-1</span>, which could cause an
 252 <span class="monospaced">Overflow</span>.</p></div>
 253 <div class="paragraph"><p>To use the above combinators the <span class="monospaced">Iter</span>-structure needs to be opened</p></div>
 254 <div class="listingblock">
 255 <div class="content"><div class="highlight"><pre><span class="k">open</span><span class="w"> </span><span class="n">Iter</span><span class="w"></span>
 256 </pre></div></div></div>
 257 <div class="paragraph"><p>and one usually also wants to declare the infix status of the
 258 operators as shown earlier.</p></div>
 259 <div class="paragraph"><p>Here is an example that illustrates some of the features:</p></div>
 260 <div class="listingblock">
 261 <div class="content"><div class="highlight"><pre><span class="n">for</span><span class="w"> </span><span class="p">(</span><span class="mi">0</span><span class="w"> </span><span class="n">to</span><span class="w"> </span><span class="mi">10</span><span class="w"> </span><span class="n">when</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="n">mod</span><span class="w"> </span><span class="mi">3</span><span class="w"> </span><span class="n">&lt;&gt;</span><span class="w"> </span><span class="mi">0</span><span class="p">)</span><span class="w"> </span><span class="n">**</span><span class="w"> </span><span class="n">inList</span><span class="w"> </span><span class="p">[</span><span class="s">&quot;a&quot;</span><span class="p">,</span><span class="w"> </span><span class="s">&quot;b&quot;</span><span class="p">]</span><span class="w"> </span><span class="n">**</span><span class="w"> </span><span class="mi">2</span><span class="w"> </span><span class="n">downto</span><span class="w"> </span><span class="mi">1</span><span class="w"> </span><span class="n">by</span><span class="w"> </span><span class="n">real</span><span class="p">)</span><span class="w"></span>
 262 <span class="w">    </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="n">&amp;</span><span class="w"> </span><span class="n">y</span><span class="w"> </span><span class="n">&amp;</span><span class="w"> </span><span class="n">z</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"></span>
 263 <span class="w">       </span><span class="n">print</span><span class="w"> </span><span class="p">(</span><span class="s">&quot;(&quot;</span><span class="n">^Int</span><span class="p">.</span><span class="n">toString</span><span class="w"> </span><span class="n">x^</span><span class="s">&quot;, </span><span class="se">\&quot;</span><span class="s">&quot;</span><span class="n">^y^</span><span class="s">&quot;</span><span class="se">\&quot;</span><span class="s">, &quot;</span><span class="n">^Real</span><span class="p">.</span><span class="n">toString</span><span class="w"> </span><span class="n">z^</span><span class="s">&quot;)</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">))</span><span class="w"></span>
 264 </pre></div></div></div>
 265 <div class="paragraph"><p>Using the <span class="monospaced">Iter</span> combinators one can easily produce more complicated
 266 iterators.  For example, here is an iterator over a "triangle":</p></div>
 267 <div class="listingblock">
 268 <div class="content"><div class="highlight"><pre><span class="k">fun</span><span class="w"> </span><span class="n">triangle</span><span class="w"> </span><span class="p">(</span><span class="n">l</span><span class="p">,</span><span class="w"> </span><span class="n">u</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">l</span><span class="w"> </span><span class="n">to</span><span class="w"> </span><span class="n">u</span><span class="w"> </span><span class="n">&gt;&gt;=</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">i</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">i</span><span class="w"> </span><span class="n">to</span><span class="w"> </span><span class="n">u</span><span class="w"> </span><span class="n">&gt;&gt;=</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">j</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">return</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">j</span><span class="p">)))</span><span class="w"></span>
 269 </pre></div></div></div>
 270 </div>
 271 </div>
 272 </div>
 273 <div id="footnotes"><hr></div>
 274 <div id="footer">
 275 <div id="footer-text">
 276 </div>
 277 <div id="footer-badges">
 278 </div>
 279 </div>
 280 </body>
 281 </html>