[hcoop/debian/mlton.git] / doc / guide / localhost / ForLoops

<!DOCTYPE html>\r
<html lang="en">\r
<head>\r
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">\r
<meta name="generator" content="AsciiDoc 8.6.9">\r
<title>ForLoops</title>\r
<link rel="stylesheet" href="./asciidoc.css" type="text/css">\r
<link rel="stylesheet" href="./pygments.css" type="text/css">\r
\r
\r
<script type="text/javascript" src="./asciidoc.js"></script>\r
<script type="text/javascript">\r
/*<![CDATA[*/\r
asciidoc.install();\r
/*]]>*/\r
</script>\r
<link rel="stylesheet" href="./mlton.css" type="text/css">\r
</head>\r
<body class="article">\r
<div id="banner">\r
<div id="banner-home">\r
<a href="./Home">MLton 20180207</a>\r
</div>\r
</div>\r
<div id="header">\r
<h1>ForLoops</h1>\r
</div>\r
<div id="content">\r
<div id="preamble">\r
<div class="sectionbody">\r
<div class="paragraph"><p>A <span class="monospaced">for</span>-loop is typically used to iterate over a range of consecutive\r
integers that denote indices of some sort.  For example, in <a href="OCaml">OCaml</a>\r
a <span class="monospaced">for</span>-loop takes either the form</p></div>\r
<div class="listingblock">\r
<div class="content monospaced">\r
<pre>for &lt;name&gt; = &lt;lower&gt; to &lt;upper&gt; do &lt;body&gt; done</pre>\r
</div></div>\r
<div class="paragraph"><p>or the form</p></div>\r
<div class="listingblock">\r
<div class="content monospaced">\r
<pre>for &lt;name&gt; = &lt;upper&gt; downto &lt;lower&gt; do &lt;body&gt; done</pre>\r
</div></div>\r
<div class="paragraph"><p>Some languages provide considerably more flexible <span class="monospaced">for</span>-loop or\r
<span class="monospaced">foreach</span>-constructs.</p></div>\r
<div class="paragraph"><p>A bit surprisingly, <a href="StandardML">Standard ML</a> provides special syntax\r
for <span class="monospaced">while</span>-loops, but not for <span class="monospaced">for</span>-loops.  Indeed, in SML, many uses\r
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>,\r
<span class="monospaced">map</span> and many other higher-order functions provided by the\r
<a href="BasisLibrary">Basis Library</a> for manipulating lists, vectors and\r
arrays.  However, the Basis Library does not provide a function for\r
iterating over a range of integer values.  Fortunately, it is very\r
easy to write one.</p></div>\r
</div>\r
</div>\r
<div class="sect1">\r
<h2 id="_a_fairly_simple_design">A fairly simple design</h2>\r
<div class="sectionbody">\r
<div class="paragraph"><p>The following implementation imitates both the syntax and semantics of\r
the OCaml <span class="monospaced">for</span>-loop.</p></div>\r
<div class="listingblock">\r
<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>\r
<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>\r
\r
<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>\r
\r
<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>\r
<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>\r
<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>\r
<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>\r
<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>\r
<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>\r
<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>\r
<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>\r
<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>\r
</pre></div></div></div>\r
<div class="paragraph"><p>For example,</p></div>\r
<div class="listingblock">\r
<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>\r
<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>\r
</pre></div></div></div>\r
<div class="paragraph"><p>would print <span class="monospaced">123456789</span> and</p></div>\r
<div class="listingblock">\r
<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>\r
<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>\r
</pre></div></div></div>\r
<div class="paragraph"><p>would print <span class="monospaced">987654321</span>.</p></div>\r
<div class="paragraph"><p>Straightforward formatting of nested loops</p></div>\r
<div class="listingblock">\r
<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>\r
<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>\r
<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>\r
<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>\r
<span class="w">                </span><span class="p">...))</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="paragraph"><p>is fairly readable, but tends to cause the body of the loop to be\r
indented quite deeply.</p></div>\r
</div>\r
</div>\r
<div class="sect1">\r
<h2 id="_off_by_one">Off-by-one</h2>\r
<div class="sectionbody">\r
<div class="paragraph"><p>The above design has an annoying feature.  In practice, the upper\r
bound of the iterated range is almost always excluded and most loops\r
would subtract one from the upper bound:</p></div>\r
<div class="listingblock">\r
<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>\r
<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>\r
</pre></div></div></div>\r
<div class="paragraph"><p>It is probably better to break convention and exclude the upper bound\r
by default, because it leads to more concise code and becomes\r
idiomatic with very little practice.  The iterator combinators\r
described below exclude the upper bound by default.</p></div>\r
</div>\r
</div>\r
<div class="sect1">\r
<h2 id="_iterator_combinators">Iterator combinators</h2>\r
<div class="sectionbody">\r
<div class="paragraph"><p>While the simple <span class="monospaced">for</span>-function described in the previous section is\r
probably good enough for many uses, it is a bit cumbersome when one\r
needs to iterate over a Cartesian product.  One might also want to\r
iterate over more than just consecutive integers.  It turns out that\r
one can provide a library of iterator combinators that allow one to\r
implement iterators more flexibly.</p></div>\r
<div class="paragraph"><p>Since the types of the combinators may be a bit difficult to infer\r
from their implementations, let&#8217;s first take a look at a signature of\r
the iterator combinator library:</p></div>\r
<div class="listingblock">\r
<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>\r
<span class="w">  </span><span class="k">sig</span><span class="w"></span>\r
<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>\r
\r
<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>\r
<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>\r
\r
<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>\r
\r
<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>\r
<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>\r
\r
<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>\r
<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>\r
<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>\r
\r
<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>\r
\r
<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>\r
<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>\r
<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>\r
<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>\r
\r
<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>\r
<span class="w">  </span><span class="k">end</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="paragraph"><p>Several of the above combinators are meant to be used as infix\r
operators.  Here is a set of suitable infix declarations:</p></div>\r
<div class="listingblock">\r
<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>\r
<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>\r
<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>\r
</pre></div></div></div>\r
<div class="paragraph"><p>A few notes are in order:</p></div>\r
<div class="ulist"><ul>\r
<li>\r
<p>\r
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.\r
</p>\r
</li>\r
<li>\r
<p>\r
The <span class="monospaced">to</span> and <span class="monospaced">downto</span> combinators will omit the upper bound of the range.\r
</p>\r
</li>\r
<li>\r
<p>\r
<span class="monospaced">for</span> is the identity function.  It is purely for syntactic sugar and is not strictly required.\r
</p>\r
</li>\r
<li>\r
<p>\r
The <span class="monospaced">@@</span> combinator produces an iterator for the concatenation of the given iterators.\r
</p>\r
</li>\r
<li>\r
<p>\r
The <span class="monospaced">**</span> combinator produces an iterator for the Cartesian product of the given iterators.\r
</p>\r
<div class="ulist"><ul>\r
<li>\r
<p>\r
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>.\r
</p>\r
</li>\r
</ul></div>\r
</li>\r
<li>\r
<p>\r
The <span class="monospaced">using</span> combinator allows one to iterate over slices, streams and many other kinds of sequences.\r
</p>\r
</li>\r
<li>\r
<p>\r
<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.\r
</p>\r
</li>\r
<li>\r
<p>\r
<span class="monospaced">by</span> is the mapping combinator.\r
</p>\r
</li>\r
</ul></div>\r
<div class="paragraph"><p>The below implementation of the <span class="monospaced">ITER</span>-signature makes use of the\r
following basic combinators:</p></div>\r
<div class="listingblock">\r
<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>\r
<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>\r
<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>\r
<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>\r
<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>\r
</pre></div></div></div>\r
<div class="paragraph"><p>Here is an implementation the <span class="monospaced">ITER</span>-signature:</p></div>\r
<div class="listingblock">\r
<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>\r
<span class="w">  </span><span class="k">struct</span><span class="w"></span>\r
<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>\r
\r
<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>\r
<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>\r
\r
<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>\r
\r
<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>\r
<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>\r
\r
<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>\r
<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>\r
<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>\r
\r
<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>\r
\r
<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>\r
<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>\r
<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>\r
<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>\r
\r
<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>\r
<span class="w">  </span><span class="k">end</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="paragraph"><p>Note that some of the above combinators (e.g. <span class="monospaced">**</span>) could be expressed\r
in terms of the other combinators, most notably <span class="monospaced">return</span> and <span class="monospaced">&gt;&gt;=</span>.\r
Another implementation issue worth mentioning is that <span class="monospaced">downto</span> is\r
written specifically to avoid computing <span class="monospaced">l-1</span>, which could cause an\r
<span class="monospaced">Overflow</span>.</p></div>\r
<div class="paragraph"><p>To use the above combinators the <span class="monospaced">Iter</span>-structure needs to be opened</p></div>\r
<div class="listingblock">\r
<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>\r
</pre></div></div></div>\r
<div class="paragraph"><p>and one usually also wants to declare the infix status of the\r
operators as shown earlier.</p></div>\r
<div class="paragraph"><p>Here is an example that illustrates some of the features:</p></div>\r
<div class="listingblock">\r
<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>\r
<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>\r
<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>\r
</pre></div></div></div>\r
<div class="paragraph"><p>Using the <span class="monospaced">Iter</span> combinators one can easily produce more complicated\r
iterators.  For example, here is an iterator over a "triangle":</p></div>\r
<div class="listingblock">\r
<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>\r
</pre></div></div></div>\r
</div>\r
</div>\r
</div>\r
<div id="footnotes"><hr></div>\r
<div id="footer">\r
<div id="footer-text">\r
</div>\r
<div id="footer-badges">\r
</div>\r
</div>\r
</body>\r
</html>\r