HCoop / hcoop / debian / mlton.git / blame
| Commit | Line | Data |
|---|---|---|
| 7f918cf1 CE |
1 | <!DOCTYPE html>\r |
| 2 | <html lang="en">\r | |
| 3 | <head>\r | |
| 4 | <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">\r | |
| 5 | <meta name="generator" content="AsciiDoc 8.6.9">\r | |
| 6 | <title>Fold</title>\r | |
| 7 | <link rel="stylesheet" href="./asciidoc.css" type="text/css">\r | |
| 8 | <link rel="stylesheet" href="./pygments.css" type="text/css">\r | |
| 9 | \r | |
| 10 | \r | |
| 11 | <script type="text/javascript" src="./asciidoc.js"></script>\r | |
| 12 | <script type="text/javascript">\r | |
| 13 | /*<![CDATA[*/\r | |
| 14 | asciidoc.install();\r | |
| 15 | /*]]>*/\r | |
| 16 | </script>\r | |
| 17 | <link rel="stylesheet" href="./mlton.css" type="text/css">\r | |
| 18 | </head>\r | |
| 19 | <body class="article">\r | |
| 20 | <div id="banner">\r | |
| 21 | <div id="banner-home">\r | |
| 22 | <a href="./Home">MLton 20180207</a>\r | |
| 23 | </div>\r | |
| 24 | </div>\r | |
| 25 | <div id="header">\r | |
| 26 | <h1>Fold</h1>\r | |
| 27 | </div>\r | |
| 28 | <div id="content">\r | |
| 29 | <div id="preamble">\r | |
| 30 | <div class="sectionbody">\r | |
| 31 | <div class="paragraph"><p>This page describes a technique that enables convenient syntax for a\r | |
| 32 | number of language features that are not explicitly supported by\r | |
| 33 | <a href="StandardML">Standard ML</a>, including: variable number of arguments,\r | |
| 34 | <a href="OptionalArguments">optional arguments and labeled arguments</a>,\r | |
| 35 | <a href="ArrayLiteral">array and vector literals</a>,\r | |
| 36 | <a href="FunctionalRecordUpdate">functional record update</a>,\r | |
| 37 | and (seemingly) dependently typed functions like <a href="Printf">printf</a> and scanf.</p></div>\r | |
| 38 | <div class="paragraph"><p>The key idea to <em>fold</em> is to define functions <span class="monospaced">fold</span>, <span class="monospaced">step0</span>,\r | |
| 39 | and <span class="monospaced">$</span> such that the following equation holds.</p></div>\r | |
| 40 | <div class="listingblock">\r | |
| 41 | <div class="content"><div class="highlight"><pre><span class="n">fold</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">f</span><span class="p">)</span><span class="w"> </span><span class="p">(</span><span class="n">step0</span><span class="w"> </span><span class="n">h1</span><span class="p">)</span><span class="w"> </span><span class="p">(</span><span class="n">step0</span><span class="w"> </span><span class="n">h2</span><span class="p">)</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="p">(</span><span class="n">step0</span><span class="w"> </span><span class="n">hn</span><span class="p">)</span><span class="w"> </span><span class="n">$</span><span class="w"></span>\r | |
| 42 | <span class="p">=</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">(</span><span class="n">hn</span><span class="w"> </span><span class="p">(...</span><span class="w"> </span><span class="p">(</span><span class="n">h2</span><span class="w"> </span><span class="p">(</span><span class="n">h1</span><span class="w"> </span><span class="n">a</span><span class="p">))))</span><span class="w"></span>\r | |
| 43 | </pre></div></div></div>\r | |
| 44 | <div class="paragraph"><p>The name <span class="monospaced">fold</span> comes because this is like a traditional list fold,\r | |
| 45 | where <span class="monospaced">a</span> is the <em>base element</em>, and each <em>step function</em>,\r | |
| 46 | <span class="monospaced">step0 hi</span>, corresponds to one element of the list and does one\r | |
| 47 | step of the fold. The name <span class="monospaced">$</span> is chosen to mean "end of\r | |
| 48 | arguments" from its common use in regular-expression syntax.</p></div>\r | |
| 49 | <div class="paragraph"><p>Unlike the usual list fold in which the same function is used to step\r | |
| 50 | over each element in the list, this fold allows the step functions to\r | |
| 51 | be different from each other, and even to be of different types. Also\r | |
| 52 | unlike the usual list fold, this fold includes a "finishing\r | |
| 53 | function", <span class="monospaced">f</span>, that is applied to the result of the fold. The\r | |
| 54 | presence of the finishing function may seem odd because there is no\r | |
| 55 | analogy in list fold. However, the finishing function is essential;\r | |
| 56 | without it, there would be no way for the folder to perform an\r | |
| 57 | arbitrary computation after processing all the arguments. The\r | |
| 58 | examples below will make this clear.</p></div>\r | |
| 59 | <div class="paragraph"><p>The functions <span class="monospaced">fold</span>, <span class="monospaced">step0</span>, and <span class="monospaced">$</span> are easy to\r | |
| 60 | define.</p></div>\r | |
| 61 | <div class="listingblock">\r | |
| 62 | <div class="content"><div class="highlight"><pre><span class="k">fun</span><span class="w"> </span><span class="n">$</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">f</span><span class="p">)</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">a</span><span class="w"></span>\r | |
| 63 | <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 | |
| 64 | <span class="k">structure</span><span class="w"> </span><span class="n">Fold</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
| 65 | <span class="w"> </span><span class="k">struct</span><span class="w"></span>\r | |
| 66 | <span class="w"> </span><span class="k">fun</span><span class="w"> </span><span class="n">fold</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">f</span><span class="p">)</span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">g</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">f</span><span class="p">)</span><span class="w"></span>\r | |
| 67 | <span class="w"> </span><span class="k">fun</span><span class="w"> </span><span class="n">step0</span><span class="w"> </span><span class="n">h</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">f</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="p">(</span><span class="n">h</span><span class="w"> </span><span class="n">a</span><span class="p">,</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"></span>\r | |
| 68 | <span class="w"> </span><span class="k">end</span><span class="w"></span>\r | |
| 69 | </pre></div></div></div>\r | |
| 70 | <div class="paragraph"><p>We’ve placed <span class="monospaced">fold</span> and <span class="monospaced">step0</span> in the <span class="monospaced">Fold</span> structure\r | |
| 71 | but left <span class="monospaced">$</span> at the toplevel because it is convenient in code to\r | |
| 72 | always have <span class="monospaced">$</span> in scope. We’ve also defined the identity\r | |
| 73 | function, <span class="monospaced">id</span>, at the toplevel since we use it so frequently.</p></div>\r | |
| 74 | <div class="paragraph"><p>Plugging in the definitions, it is easy to verify the equation from\r | |
| 75 | above.</p></div>\r | |
| 76 | <div class="listingblock">\r | |
| 77 | <div class="content"><div class="highlight"><pre><span class="n">fold</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">f</span><span class="p">)</span><span class="w"> </span><span class="p">(</span><span class="n">step0</span><span class="w"> </span><span class="n">h1</span><span class="p">)</span><span class="w"> </span><span class="p">(</span><span class="n">step0</span><span class="w"> </span><span class="n">h2</span><span class="p">)</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="p">(</span><span class="n">step0</span><span class="w"> </span><span class="n">hn</span><span class="p">)</span><span class="w"> </span><span class="n">$</span><span class="w"></span>\r | |
| 78 | <span class="p">=</span><span class="w"> </span><span class="n">step0</span><span class="w"> </span><span class="n">h1</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">f</span><span class="p">)</span><span class="w"> </span><span class="p">(</span><span class="n">step0</span><span class="w"> </span><span class="n">h2</span><span class="p">)</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="p">(</span><span class="n">step0</span><span class="w"> </span><span class="n">hn</span><span class="p">)</span><span class="w"> </span><span class="n">$</span><span class="w"></span>\r | |
| 79 | <span class="p">=</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="p">(</span><span class="n">h1</span><span class="w"> </span><span class="n">a</span><span class="p">,</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"> </span><span class="p">(</span><span class="n">step0</span><span class="w"> </span><span class="n">h2</span><span class="p">)</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="p">(</span><span class="n">step0</span><span class="w"> </span><span class="n">hn</span><span class="p">)</span><span class="w"> </span><span class="n">$</span><span class="w"></span>\r | |
| 80 | <span class="p">=</span><span class="w"> </span><span class="n">step0</span><span class="w"> </span><span class="n">h2</span><span class="w"> </span><span class="p">(</span><span class="n">h1</span><span class="w"> </span><span class="n">a</span><span class="p">,</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="p">(</span><span class="n">step0</span><span class="w"> </span><span class="n">hn</span><span class="p">)</span><span class="w"> </span><span class="n">$</span><span class="w"></span>\r | |
| 81 | <span class="p">=</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="p">(</span><span class="n">h2</span><span class="w"> </span><span class="p">(</span><span class="n">h1</span><span class="w"> </span><span class="n">a</span><span class="p">),</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="p">(</span><span class="n">step0</span><span class="w"> </span><span class="n">hn</span><span class="p">)</span><span class="w"> </span><span class="n">$</span><span class="w"></span>\r | |
| 82 | <span class="p">...</span><span class="w"></span>\r | |
| 83 | <span class="p">=</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="p">(</span><span class="n">hn</span><span class="w"> </span><span class="p">(...</span><span class="w"> </span><span class="p">(</span><span class="n">h2</span><span class="w"> </span><span class="p">(</span><span class="n">h1</span><span class="w"> </span><span class="n">a</span><span class="p">))),</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"> </span><span class="n">$</span><span class="w"></span>\r | |
| 84 | <span class="p">=</span><span class="w"> </span><span class="n">$</span><span class="w"> </span><span class="p">(</span><span class="n">hn</span><span class="w"> </span><span class="p">(...</span><span class="w"> </span><span class="p">(</span><span class="n">h2</span><span class="w"> </span><span class="p">(</span><span class="n">h1</span><span class="w"> </span><span class="n">a</span><span class="p">))),</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"></span>\r | |
| 85 | <span class="p">=</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">(</span><span class="n">hn</span><span class="w"> </span><span class="p">(...</span><span class="w"> </span><span class="p">(</span><span class="n">h2</span><span class="w"> </span><span class="p">(</span><span class="n">h1</span><span class="w"> </span><span class="n">a</span><span class="p">))))</span><span class="w"></span>\r | |
| 86 | </pre></div></div></div>\r | |
| 87 | </div>\r | |
| 88 | </div>\r | |
| 89 | <div class="sect1">\r | |
| 90 | <h2 id="_example_variable_number_of_arguments">Example: variable number of arguments</h2>\r | |
| 91 | <div class="sectionbody">\r | |
| 92 | <div class="paragraph"><p>The simplest example of fold is accepting a variable number of\r | |
| 93 | (curried) arguments. We’ll define a function <span class="monospaced">f</span> and argument\r | |
| 94 | <span class="monospaced">a</span> such that all of the following expressions are valid.</p></div>\r | |
| 95 | <div class="listingblock">\r | |
| 96 | <div class="content"><div class="highlight"><pre><span class="n">f</span><span class="w"> </span><span class="n">$</span><span class="w"></span>\r | |
| 97 | <span class="n">f</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">$</span><span class="w"></span>\r | |
| 98 | <span class="n">f</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">$</span><span class="w"></span>\r | |
| 99 | <span class="n">f</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">$</span><span class="w"></span>\r | |
| 100 | <span class="n">f</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">a</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">a</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">$</span><span class="w"> </span><span class="cm">(* as many a's as we want *)</span><span class="w"></span>\r | |
| 101 | </pre></div></div></div>\r | |
| 102 | <div class="paragraph"><p>Off-hand it may appear impossible that all of the above expressions\r | |
| 103 | are type correct SML — how can a function <span class="monospaced">f</span> accept a variable\r | |
| 104 | number of curried arguments? What could the type of <span class="monospaced">f</span> be?\r | |
| 105 | We’ll have more to say later on how type checking works. For now,\r | |
| 106 | once we have supplied the definitions below, you can check that the\r | |
| 107 | expressions are type correct by feeding them to your favorite SML\r | |
| 108 | implementation.</p></div>\r | |
| 109 | <div class="paragraph"><p>It is simple to define <span class="monospaced">f</span> and <span class="monospaced">a</span>. We define <span class="monospaced">f</span> as a\r | |
| 110 | folder whose base element is <span class="monospaced">()</span> and whose finish function does\r | |
| 111 | nothing. We define <span class="monospaced">a</span> as the step function that does nothing.\r | |
| 112 | The only trickiness is that we must <a href="EtaExpansion">eta expand</a> the\r | |
| 113 | definition of <span class="monospaced">f</span> and <span class="monospaced">a</span> to work around the ValueRestriction;\r | |
| 114 | we frequently use eta expansion for this purpose without mention.</p></div>\r | |
| 115 | <div class="listingblock">\r | |
| 116 | <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">base</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="p">()</span><span class="w"></span>\r | |
| 117 | <span class="k">fun</span><span class="w"> </span><span class="n">finish</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="p">()</span><span class="w"></span>\r | |
| 118 | <span class="k">fun</span><span class="w"> </span><span class="n">step</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="p">()</span><span class="w"></span>\r | |
| 119 | <span class="k">val</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">fn</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">Fold</span><span class="p">.</span><span class="n">fold</span><span class="w"> </span><span class="p">(</span><span class="n">base</span><span class="p">,</span><span class="w"> </span><span class="n">finish</span><span class="p">)</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 120 | <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="k">fn</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">Fold</span><span class="p">.</span><span class="n">step0</span><span class="w"> </span><span class="n">step</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 121 | </pre></div></div></div>\r | |
| 122 | <div class="paragraph"><p>One can easily apply the fold equation to verify by hand that <span class="monospaced">f</span>\r | |
| 123 | applied to any number of <span class="monospaced">a</span>'s evaluates to <span class="monospaced">()</span>.</p></div>\r | |
| 124 | <div class="listingblock">\r | |
| 125 | <div class="content"><div class="highlight"><pre><span class="n">f</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">a</span><span class="w"> </span><span class="n">$</span><span class="w"></span>\r | |
| 126 | <span class="p">=</span><span class="w"> </span><span class="n">finish</span><span class="w"> </span><span class="p">(</span><span class="n">step</span><span class="w"> </span><span class="p">(...</span><span class="w"> </span><span class="p">(</span><span class="n">step</span><span class="w"> </span><span class="n">base</span><span class="p">)))</span><span class="w"></span>\r | |
| 127 | <span class="p">=</span><span class="w"> </span><span class="n">finish</span><span class="w"> </span><span class="p">(</span><span class="n">step</span><span class="w"> </span><span class="p">(...</span><span class="w"> </span><span class="p">()))</span><span class="w"></span>\r | |
| 128 | <span class="p">...</span><span class="w"></span>\r | |
| 129 | <span class="p">=</span><span class="w"> </span><span class="n">finish</span><span class="w"> </span><span class="p">()</span><span class="w"></span>\r | |
| 130 | <span class="p">=</span><span class="w"> </span><span class="p">()</span><span class="w"></span>\r | |
| 131 | </pre></div></div></div>\r | |
| 132 | </div>\r | |
| 133 | </div>\r | |
| 134 | <div class="sect1">\r | |
| 135 | <h2 id="_example_variable_argument_sum">Example: variable-argument sum</h2>\r | |
| 136 | <div class="sectionbody">\r | |
| 137 | <div class="paragraph"><p>Let’s look at an example that computes something: a variable-argument\r | |
| 138 | function <span class="monospaced">sum</span> and a stepper <span class="monospaced">a</span> such that</p></div>\r | |
| 139 | <div class="listingblock">\r | |
| 140 | <div class="content"><div class="highlight"><pre><span class="n">sum</span><span class="w"> </span><span class="p">(</span><span class="n">a</span><span class="w"> </span><span class="n">i1</span><span class="p">)</span><span class="w"> </span><span class="p">(</span><span class="n">a</span><span class="w"> </span><span class="n">i2</span><span class="p">)</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="p">(</span><span class="n">a</span><span class="w"> </span><span class="n">im</span><span class="p">)</span><span class="w"> </span><span class="n">$</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">i1</span><span class="w"> </span><span class="n">+</span><span class="w"> </span><span class="n">i2</span><span class="w"> </span><span class="n">+</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="n">+</span><span class="w"> </span><span class="n">im</span><span class="w"></span>\r | |
| 141 | </pre></div></div></div>\r | |
| 142 | <div class="paragraph"><p>The idea is simple — the folder starts with a base accumulator of\r | |
| 143 | <span class="monospaced">0</span> and the stepper adds each element to the accumulator, <span class="monospaced">s</span>,\r | |
| 144 | which the folder simply returns at the end.</p></div>\r | |
| 145 | <div class="listingblock">\r | |
| 146 | <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">sum</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">=></span><span class="w"> </span><span class="n">Fold</span><span class="p">.</span><span class="n">fold</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="n">s</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">s</span><span class="p">)</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 147 | <span class="k">fun</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">i</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">Fold</span><span class="p">.</span><span class="n">step0</span><span class="w"> </span><span class="p">(</span><span class="k">fn</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">i</span><span class="w"> </span><span class="n">+</span><span class="w"> </span><span class="n">s</span><span class="p">)</span><span class="w"></span>\r | |
| 148 | </pre></div></div></div>\r | |
| 149 | <div class="paragraph"><p>Using the fold equation, one can verify the following.</p></div>\r | |
| 150 | <div class="listingblock">\r | |
| 151 | <div class="content"><div class="highlight"><pre><span class="n">sum</span><span class="w"> </span><span class="p">(</span><span class="n">a</span><span class="w"> </span><span class="mi">1</span><span class="p">)</span><span class="w"> </span><span class="p">(</span><span class="n">a</span><span class="w"> </span><span class="mi">2</span><span class="p">)</span><span class="w"> </span><span class="p">(</span><span class="n">a</span><span class="w"> </span><span class="mi">3</span><span class="p">)</span><span class="w"> </span><span class="n">$</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mi">6</span><span class="w"></span>\r | |
| 152 | </pre></div></div></div>\r | |
| 153 | </div>\r | |
| 154 | </div>\r | |
| 155 | <div class="sect1">\r | |
| 156 | <h2 id="_step1">Step1</h2>\r | |
| 157 | <div class="sectionbody">\r | |
| 158 | <div class="paragraph"><p>It is sometimes syntactically convenient to omit the parentheses\r | |
| 159 | around the steps in a fold. This is easily done by defining a new\r | |
| 160 | function, <span class="monospaced">step1</span>, as follows.</p></div>\r | |
| 161 | <div class="listingblock">\r | |
| 162 | <div class="content"><div class="highlight"><pre><span class="k">structure</span><span class="w"> </span><span class="n">Fold</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
| 163 | <span class="w"> </span><span class="k">struct</span><span class="w"></span>\r | |
| 164 | <span class="w"> </span><span class="k">open</span><span class="w"> </span><span class="n">Fold</span><span class="w"></span>\r | |
| 165 | <span class="w"> </span><span class="k">fun</span><span class="w"> </span><span class="n">step1</span><span class="w"> </span><span class="n">h</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">f</span><span class="p">)</span><span class="w"> </span><span class="n">b</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="p">(</span><span class="n">h</span><span class="w"> </span><span class="p">(</span><span class="n">b</span><span class="p">,</span><span class="w"> </span><span class="n">a</span><span class="p">),</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"></span>\r | |
| 166 | <span class="w"> </span><span class="k">end</span><span class="w"></span>\r | |
| 167 | </pre></div></div></div>\r | |
| 168 | <div class="paragraph"><p>From the definition of <span class="monospaced">step1</span>, we have the following\r | |
| 169 | equivalence.</p></div>\r | |
| 170 | <div class="listingblock">\r | |
| 171 | <div class="content"><div class="highlight"><pre><span class="n">fold</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">f</span><span class="p">)</span><span class="w"> </span><span class="p">(</span><span class="n">step1</span><span class="w"> </span><span class="n">h</span><span class="p">)</span><span class="w"> </span><span class="n">b</span><span class="w"></span>\r | |
| 172 | <span class="p">=</span><span class="w"> </span><span class="n">step1</span><span class="w"> </span><span class="n">h</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">f</span><span class="p">)</span><span class="w"> </span><span class="n">b</span><span class="w"></span>\r | |
| 173 | <span class="p">=</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="p">(</span><span class="n">h</span><span class="w"> </span><span class="p">(</span><span class="n">b</span><span class="p">,</span><span class="w"> </span><span class="n">a</span><span class="p">),</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"></span>\r | |
| 174 | </pre></div></div></div>\r | |
| 175 | <div class="paragraph"><p>Using the above equivalence, we can compute the following equation for\r | |
| 176 | <span class="monospaced">step1</span>.</p></div>\r | |
| 177 | <div class="listingblock">\r | |
| 178 | <div class="content"><div class="highlight"><pre><span class="n">fold</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">f</span><span class="p">)</span><span class="w"> </span><span class="p">(</span><span class="n">step1</span><span class="w"> </span><span class="n">h1</span><span class="p">)</span><span class="w"> </span><span class="n">b1</span><span class="w"> </span><span class="p">(</span><span class="n">step1</span><span class="w"> </span><span class="n">h2</span><span class="p">)</span><span class="w"> </span><span class="n">b2</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="p">(</span><span class="n">step1</span><span class="w"> </span><span class="n">hn</span><span class="p">)</span><span class="w"> </span><span class="n">bn</span><span class="w"> </span><span class="n">$</span><span class="w"></span>\r | |
| 179 | <span class="p">=</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="p">(</span><span class="n">h1</span><span class="w"> </span><span class="p">(</span><span class="n">b1</span><span class="p">,</span><span class="w"> </span><span class="n">a</span><span class="p">),</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"> </span><span class="p">(</span><span class="n">step1</span><span class="w"> </span><span class="n">h2</span><span class="p">)</span><span class="w"> </span><span class="n">b2</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="p">(</span><span class="n">step1</span><span class="w"> </span><span class="n">hn</span><span class="p">)</span><span class="w"> </span><span class="n">bn</span><span class="w"> </span><span class="n">$</span><span class="w"></span>\r | |
| 180 | <span class="p">=</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="p">(</span><span class="n">h2</span><span class="w"> </span><span class="p">(</span><span class="n">b2</span><span class="p">,</span><span class="w"> </span><span class="n">h1</span><span class="w"> </span><span class="p">(</span><span class="n">b1</span><span class="p">,</span><span class="w"> </span><span class="n">a</span><span class="p">)),</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="p">(</span><span class="n">step1</span><span class="w"> </span><span class="n">hn</span><span class="p">)</span><span class="w"> </span><span class="n">bn</span><span class="w"> </span><span class="n">$</span><span class="w"></span>\r | |
| 181 | <span class="p">=</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="p">(</span><span class="n">hn</span><span class="w"> </span><span class="p">(</span><span class="n">bn</span><span class="p">,</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="p">(</span><span class="n">h2</span><span class="w"> </span><span class="p">(</span><span class="n">b2</span><span class="p">,</span><span class="w"> </span><span class="n">h1</span><span class="w"> </span><span class="p">(</span><span class="n">b1</span><span class="p">,</span><span class="w"> </span><span class="n">a</span><span class="p">)))),</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"> </span><span class="n">$</span><span class="w"></span>\r | |
| 182 | <span class="p">=</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">(</span><span class="n">hn</span><span class="w"> </span><span class="p">(</span><span class="n">bn</span><span class="p">,</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="p">(</span><span class="n">h2</span><span class="w"> </span><span class="p">(</span><span class="n">b2</span><span class="p">,</span><span class="w"> </span><span class="n">h1</span><span class="w"> </span><span class="p">(</span><span class="n">b1</span><span class="p">,</span><span class="w"> </span><span class="n">a</span><span class="p">)))))</span><span class="w"></span>\r | |
| 183 | </pre></div></div></div>\r | |
| 184 | <div class="paragraph"><p>Here is an example using <span class="monospaced">step1</span> to define a variable-argument\r | |
| 185 | product function, <span class="monospaced">prod</span>, with a convenient syntax.</p></div>\r | |
| 186 | <div class="listingblock">\r | |
| 187 | <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">prod</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">=></span><span class="w"> </span><span class="n">Fold</span><span class="p">.</span><span class="n">fold</span><span class="w"> </span><span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="k">fn</span><span class="w"> </span><span class="n">p</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">p</span><span class="p">)</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 188 | <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="k">fn</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">Fold</span><span class="p">.</span><span class="n">step1</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">i</span><span class="p">,</span><span class="w"> </span><span class="n">p</span><span class="p">)</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">i</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">p</span><span class="p">)</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 189 | </pre></div></div></div>\r | |
| 190 | <div class="paragraph"><p>The functions <span class="monospaced">prod</span> and <span class="monospaced">`</span> satisfy the following equation.</p></div>\r | |
| 191 | <div class="listingblock">\r | |
| 192 | <div class="content"><div class="highlight"><pre><span class="n">prod</span><span class="w"> </span><span class="n">`i1</span><span class="w"> </span><span class="n">`i2</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="n">`im</span><span class="w"> </span><span class="n">$</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">i1</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">i2</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">im</span><span class="w"></span>\r | |
| 193 | </pre></div></div></div>\r | |
| 194 | <div class="paragraph"><p>Note that in SML, <span class="monospaced">`i1</span> is two different tokens, <span class="monospaced">`</span> and\r | |
| 195 | <span class="monospaced">i1</span>. We often use <span class="monospaced">`</span> for an instance of a <span class="monospaced">step1</span> function\r | |
| 196 | because of its syntactic unobtrusiveness and because no space is\r | |
| 197 | required to separate it from an alphanumeric token.</p></div>\r | |
| 198 | <div class="paragraph"><p>Also note that there are no parenthesis around the steps. That is,\r | |
| 199 | the following expression is not the same as the above one (in fact, it\r | |
| 200 | is not type correct).</p></div>\r | |
| 201 | <div class="listingblock">\r | |
| 202 | <div class="content"><div class="highlight"><pre><span class="n">prod</span><span class="w"> </span><span class="p">(</span><span class="n">`i1</span><span class="p">)</span><span class="w"> </span><span class="p">(</span><span class="n">`i2</span><span class="p">)</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="p">(</span><span class="n">`im</span><span class="p">)</span><span class="w"> </span><span class="n">$</span><span class="w"></span>\r | |
| 203 | </pre></div></div></div>\r | |
| 204 | </div>\r | |
| 205 | </div>\r | |
| 206 | <div class="sect1">\r | |
| 207 | <h2 id="_example_list_literals">Example: list literals</h2>\r | |
| 208 | <div class="sectionbody">\r | |
| 209 | <div class="paragraph"><p>SML already has a syntax for list literals, e.g. <span class="monospaced">[w, x, y, z]</span>.\r | |
| 210 | However, using fold, we can define our own syntax.</p></div>\r | |
| 211 | <div class="listingblock">\r | |
| 212 | <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">list</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">=></span><span class="w"> </span><span class="n">Fold</span><span class="p">.</span><span class="n">fold</span><span class="w"> </span><span class="p">([],</span><span class="w"> </span><span class="n">rev</span><span class="p">)</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 213 | <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="k">fn</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">Fold</span><span class="p">.</span><span class="n">step1</span><span class="w"> </span><span class="p">(</span><span class="k">op</span><span class="w"> </span><span class="n">::</span><span class="p">)</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 214 | </pre></div></div></div>\r | |
| 215 | <div class="paragraph"><p>The idea is that the folder starts out with the empty list, the steps\r | |
| 216 | accumulate the elements into a list, and then the finishing function\r | |
| 217 | reverses the list at the end.</p></div>\r | |
| 218 | <div class="paragraph"><p>With these definitions one can write a list like:</p></div>\r | |
| 219 | <div class="listingblock">\r | |
| 220 | <div class="content"><div class="highlight"><pre><span class="n">list</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>\r | |
| 221 | </pre></div></div></div>\r | |
| 222 | <div class="paragraph"><p>While the example is not practically useful, it does demonstrate the\r | |
| 223 | need for the finishing function to be incorporated in <span class="monospaced">fold</span>.\r | |
| 224 | Without a finishing function, every use of <span class="monospaced">list</span> would need to be\r | |
| 225 | wrapped in <span class="monospaced">rev</span>, as follows.</p></div>\r | |
| 226 | <div class="listingblock">\r | |
| 227 | <div class="content"><div class="highlight"><pre><span class="n">rev</span><span class="w"> </span><span class="p">(</span><span class="n">list</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="p">)</span><span class="w"></span>\r | |
| 228 | </pre></div></div></div>\r | |
| 229 | <div class="paragraph"><p>The finishing function allows us to incorporate the reversal into the\r | |
| 230 | definition of <span class="monospaced">list</span>, and to treat <span class="monospaced">list</span> as a truly variable\r | |
| 231 | argument function, performing an arbitrary computation after receiving\r | |
| 232 | all of its arguments.</p></div>\r | |
| 233 | <div class="paragraph"><p>See <a href="ArrayLiteral">ArrayLiteral</a> for a similar use of <span class="monospaced">fold</span> that provides a\r | |
| 234 | syntax for array and vector literals, which are not built in to SML.</p></div>\r | |
| 235 | </div>\r | |
| 236 | </div>\r | |
| 237 | <div class="sect1">\r | |
| 238 | <h2 id="_fold_right">Fold right</h2>\r | |
| 239 | <div class="sectionbody">\r | |
| 240 | <div class="paragraph"><p>Just as <span class="monospaced">fold</span> is analogous to a fold left, in which the functions\r | |
| 241 | are applied to the accumulator left-to-right, we can define a variant\r | |
| 242 | of <span class="monospaced">fold</span> that is analogous to a fold right, in which the\r | |
| 243 | functions are applied to the accumulator right-to-left. That is, we\r | |
| 244 | can define functions <span class="monospaced">foldr</span> and <span class="monospaced">step0</span> such that the\r | |
| 245 | following equation holds.</p></div>\r | |
| 246 | <div class="listingblock">\r | |
| 247 | <div class="content"><div class="highlight"><pre><span class="n">foldr</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">f</span><span class="p">)</span><span class="w"> </span><span class="p">(</span><span class="n">step0</span><span class="w"> </span><span class="n">h1</span><span class="p">)</span><span class="w"> </span><span class="p">(</span><span class="n">step0</span><span class="w"> </span><span class="n">h2</span><span class="p">)</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="p">(</span><span class="n">step0</span><span class="w"> </span><span class="n">hn</span><span class="p">)</span><span class="w"> </span><span class="n">$</span><span class="w"></span>\r | |
| 248 | <span class="p">=</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">(</span><span class="n">h1</span><span class="w"> </span><span class="p">(</span><span class="n">h2</span><span class="w"> </span><span class="p">(...</span><span class="w"> </span><span class="p">(</span><span class="n">hn</span><span class="w"> </span><span class="n">a</span><span class="p">))))</span><span class="w"></span>\r | |
| 249 | </pre></div></div></div>\r | |
| 250 | <div class="paragraph"><p>The implementation of fold right is easy, using fold. The idea is for\r | |
| 251 | the fold to start with <span class="monospaced">f</span> and for each step to precompose the\r | |
| 252 | next <span class="monospaced">hi</span>. Then, the finisher applies the composed function to\r | |
| 253 | the base value, <span class="monospaced">a</span>. Here is the code.</p></div>\r | |
| 254 | <div class="listingblock">\r | |
| 255 | <div class="content"><div class="highlight"><pre><span class="k">structure</span><span class="w"> </span><span class="n">Foldr</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
| 256 | <span class="w"> </span><span class="k">struct</span><span class="w"></span>\r | |
| 257 | <span class="w"> </span><span class="k">fun</span><span class="w"> </span><span class="n">foldr</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">f</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">Fold</span><span class="p">.</span><span class="n">fold</span><span class="w"> </span><span class="p">(</span><span class="n">f</span><span class="p">,</span><span class="w"> </span><span class="k">fn</span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="n">a</span><span class="p">)</span><span class="w"></span>\r | |
| 258 | <span class="w"> </span><span class="k">fun</span><span class="w"> </span><span class="n">step0</span><span class="w"> </span><span class="n">h</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">Fold</span><span class="p">.</span><span class="n">step0</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">h</span><span class="p">)</span><span class="w"></span>\r | |
| 259 | <span class="w"> </span><span class="k">end</span><span class="w"></span>\r | |
| 260 | </pre></div></div></div>\r | |
| 261 | <div class="paragraph"><p>Verifying the fold-right equation is straightforward, using the\r | |
| 262 | fold-left equation.</p></div>\r | |
| 263 | <div class="listingblock">\r | |
| 264 | <div class="content"><div class="highlight"><pre><span class="n">foldr</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">f</span><span class="p">)</span><span class="w"> </span><span class="p">(</span><span class="n">Foldr</span><span class="p">.</span><span class="n">step0</span><span class="w"> </span><span class="n">h1</span><span class="p">)</span><span class="w"> </span><span class="p">(</span><span class="n">Foldr</span><span class="p">.</span><span class="n">step0</span><span class="w"> </span><span class="n">h2</span><span class="p">)</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="p">(</span><span class="n">Foldr</span><span class="p">.</span><span class="n">step0</span><span class="w"> </span><span class="n">hn</span><span class="p">)</span><span class="w"> </span><span class="n">$</span><span class="w"></span>\r | |
| 265 | <span class="p">=</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="p">(</span><span class="n">f</span><span class="p">,</span><span class="w"> </span><span class="k">fn</span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="n">a</span><span class="p">)</span><span class="w"></span>\r | |
| 266 | <span class="w"> </span><span class="p">(</span><span class="n">Fold</span><span class="p">.</span><span class="n">step0</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">h1</span><span class="p">))</span><span class="w"></span>\r | |
| 267 | <span class="w"> </span><span class="p">(</span><span class="n">Fold</span><span class="p">.</span><span class="n">step0</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">h2</span><span class="p">))</span><span class="w"></span>\r | |
| 268 | <span class="w"> </span><span class="p">...</span><span class="w"></span>\r | |
| 269 | <span class="w"> </span><span class="p">(</span><span class="n">Fold</span><span class="p">.</span><span class="n">step0</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">hn</span><span class="p">))</span><span class="w"> </span><span class="n">$</span><span class="w"></span>\r | |
| 270 | <span class="p">=</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="n">a</span><span class="p">)</span><span class="w"></span>\r | |
| 271 | <span class="w"> </span><span class="p">((</span><span class="k">fn</span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">hn</span><span class="p">)</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="n">g</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">h2</span><span class="p">)</span><span class="w"> </span><span class="p">((</span><span class="k">fn</span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">h1</span><span class="p">)</span><span class="w"> </span><span class="n">f</span><span class="p">))))</span><span class="w"></span>\r | |
| 272 | <span class="p">=</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="n">a</span><span class="p">)</span><span class="w"></span>\r | |
| 273 | <span class="w"> </span><span class="p">((</span><span class="k">fn</span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">hn</span><span class="p">)</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="n">g</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">h2</span><span class="p">)</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">h1</span><span class="p">))))</span><span class="w"></span>\r | |
| 274 | <span class="p">=</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="n">a</span><span class="p">)</span><span class="w"> </span><span class="p">((</span><span class="k">fn</span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">hn</span><span class="p">)</span><span class="w"> </span><span class="p">(...</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">h1</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">h2</span><span class="p">)))</span><span class="w"></span>\r | |
| 275 | <span class="p">=</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">g</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">f</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">h1</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">h2</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">hn</span><span class="p">)</span><span class="w"></span>\r | |
| 276 | <span class="p">=</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">h1</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">h2</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">hn</span><span class="p">)</span><span class="w"> </span><span class="n">a</span><span class="w"></span>\r | |
| 277 | <span class="p">=</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">(</span><span class="n">h1</span><span class="w"> </span><span class="p">(</span><span class="n">h2</span><span class="w"> </span><span class="p">(...</span><span class="w"> </span><span class="p">(</span><span class="n">hn</span><span class="w"> </span><span class="n">a</span><span class="p">))))</span><span class="w"></span>\r | |
| 278 | </pre></div></div></div>\r | |
| 279 | <div class="paragraph"><p>One can also define the fold-right analogue of <span class="monospaced">step1</span>.</p></div>\r | |
| 280 | <div class="listingblock">\r | |
| 281 | <div class="content"><div class="highlight"><pre><span class="k">structure</span><span class="w"> </span><span class="n">Foldr</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
| 282 | <span class="w"> </span><span class="k">struct</span><span class="w"></span>\r | |
| 283 | <span class="w"> </span><span class="k">open</span><span class="w"> </span><span class="n">Foldr</span><span class="w"></span>\r | |
| 284 | <span class="w"> </span><span class="k">fun</span><span class="w"> </span><span class="n">step1</span><span class="w"> </span><span class="n">h</span><span class="w"> </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><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="p">(</span><span class="n">b</span><span class="p">,</span><span class="w"> </span><span class="n">g</span><span class="p">)</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="n">o</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">=></span><span class="w"> </span><span class="n">h</span><span class="w"> </span><span class="p">(</span><span class="n">b</span><span class="p">,</span><span class="w"> </span><span class="n">a</span><span class="p">)))</span><span class="w"></span>\r | |
| 285 | <span class="w"> </span><span class="k">end</span><span class="w"></span>\r | |
| 286 | </pre></div></div></div>\r | |
| 287 | </div>\r | |
| 288 | </div>\r | |
| 289 | <div class="sect1">\r | |
| 290 | <h2 id="_example_list_literals_via_fold_right">Example: list literals via fold right</h2>\r | |
| 291 | <div class="sectionbody">\r | |
| 292 | <div class="paragraph"><p>Revisiting the list literal example from earlier, we can use fold\r | |
| 293 | right to define a syntax for list literals that doesn’t do a reversal.</p></div>\r | |
| 294 | <div class="listingblock">\r | |
| 295 | <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">list</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">=></span><span class="w"> </span><span class="n">Foldr</span><span class="p">.</span><span class="n">foldr</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">l</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">l</span><span class="p">)</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 296 | <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="k">fn</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">Foldr</span><span class="p">.</span><span class="n">step1</span><span class="w"> </span><span class="p">(</span><span class="k">op</span><span class="w"> </span><span class="n">::</span><span class="p">)</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 297 | </pre></div></div></div>\r | |
| 298 | <div class="paragraph"><p>As before, with these definitions, one can write a list like:</p></div>\r | |
| 299 | <div class="listingblock">\r | |
| 300 | <div class="content"><div class="highlight"><pre><span class="n">list</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>\r | |
| 301 | </pre></div></div></div>\r | |
| 302 | <div class="paragraph"><p>The difference between the fold-left and fold-right approaches is that\r | |
| 303 | the fold-right approach does not have to reverse the list at the end,\r | |
| 304 | since it accumulates the elements in the correct order. In practice,\r | |
| 305 | MLton will simplify away all of the intermediate function composition,\r | |
| 306 | so the the fold-right approach will be more efficient.</p></div>\r | |
| 307 | </div>\r | |
| 308 | </div>\r | |
| 309 | <div class="sect1">\r | |
| 310 | <h2 id="_mixing_steppers">Mixing steppers</h2>\r | |
| 311 | <div class="sectionbody">\r | |
| 312 | <div class="paragraph"><p>All of the examples so far have used the same step function throughout\r | |
| 313 | a fold. This need not be the case. For example, consider the\r | |
| 314 | following.</p></div>\r | |
| 315 | <div class="listingblock">\r | |
| 316 | <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">n</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">=></span><span class="w"> </span><span class="n">Fold</span><span class="p">.</span><span class="n">fold</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="n">i</span><span class="w"> </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">z</span><span class="w"></span>\r | |
| 317 | <span class="k">val</span><span class="w"> </span><span class="n">I</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">=></span><span class="w"> </span><span class="n">Fold</span><span class="p">.</span><span class="n">step0</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">=></span><span class="w"> </span><span class="n">i</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="mi">2</span><span class="p">)</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 318 | <span class="k">val</span><span class="w"> </span><span class="n">O</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">=></span><span class="w"> </span><span class="n">Fold</span><span class="p">.</span><span class="n">step0</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">=></span><span class="w"> </span><span class="n">i</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">+</span><span class="w"> </span><span class="mi">1</span><span class="p">)</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 319 | </pre></div></div></div>\r | |
| 320 | <div class="paragraph"><p>Here we have one folder, <span class="monospaced">n</span>, that can be used with two different\r | |
| 321 | steppers, <span class="monospaced">I</span> and <span class="monospaced">O</span>. By using the fold equation, one can\r | |
| 322 | verify the following equations.</p></div>\r | |
| 323 | <div class="listingblock">\r | |
| 324 | <div class="content"><div class="highlight"><pre><span class="n">n</span><span class="w"> </span><span class="n">O</span><span class="w"> </span><span class="n">$</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mi">0</span><span class="w"></span>\r | |
| 325 | <span class="n">n</span><span class="w"> </span><span class="n">I</span><span class="w"> </span><span class="n">$</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mi">1</span><span class="w"></span>\r | |
| 326 | <span class="n">n</span><span class="w"> </span><span class="n">I</span><span class="w"> </span><span class="n">O</span><span class="w"> </span><span class="n">$</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mi">2</span><span class="w"></span>\r | |
| 327 | <span class="n">n</span><span class="w"> </span><span class="n">I</span><span class="w"> </span><span class="n">O</span><span class="w"> </span><span class="n">I</span><span class="w"> </span><span class="n">$</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mi">5</span><span class="w"></span>\r | |
| 328 | <span class="n">n</span><span class="w"> </span><span class="n">I</span><span class="w"> </span><span class="n">I</span><span class="w"> </span><span class="n">I</span><span class="w"> </span><span class="n">O</span><span class="w"> </span><span class="n">$</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mi">14</span><span class="w"></span>\r | |
| 329 | </pre></div></div></div>\r | |
| 330 | <div class="paragraph"><p>That is, we’ve defined a syntax for writing binary integer constants.</p></div>\r | |
| 331 | <div class="paragraph"><p>Not only can one use different instances of <span class="monospaced">step0</span> in the same\r | |
| 332 | fold, one can also intermix uses of <span class="monospaced">step0</span> and <span class="monospaced">step1</span>. For\r | |
| 333 | example, consider the following.</p></div>\r | |
| 334 | <div class="listingblock">\r | |
| 335 | <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">n</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">=></span><span class="w"> </span><span class="n">Fold</span><span class="p">.</span><span class="n">fold</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="n">i</span><span class="w"> </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">z</span><span class="w"></span>\r | |
| 336 | <span class="k">val</span><span class="w"> </span><span class="n">O</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">=></span><span class="w"> </span><span class="n">Fold</span><span class="p">.</span><span class="n">step0</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">=></span><span class="w"> </span><span class="n">n</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="mi">8</span><span class="p">)</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 337 | <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="k">fn</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">Fold</span><span class="p">.</span><span class="n">step1</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">i</span><span class="p">,</span><span class="w"> </span><span class="n">n</span><span class="p">)</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">n</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="mi">8</span><span class="w"> </span><span class="n">+</span><span class="w"> </span><span class="n">i</span><span class="p">)</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 338 | </pre></div></div></div>\r | |
| 339 | <div class="paragraph"><p>Using the straightforward generalization of the fold equation to mixed\r | |
| 340 | steppers, one can verify the following equations.</p></div>\r | |
| 341 | <div class="listingblock">\r | |
| 342 | <div class="content"><div class="highlight"><pre><span class="n">n</span><span class="w"> </span><span class="mi">0</span><span class="w"> </span><span class="n">$</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mi">0</span><span class="w"></span>\r | |
| 343 | <span class="n">n</span><span class="w"> </span><span class="n">`</span><span class="mi">3</span><span class="w"> </span><span class="n">O</span><span class="w"> </span><span class="n">$</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mi">24</span><span class="w"></span>\r | |
| 344 | <span class="n">n</span><span class="w"> </span><span class="n">`</span><span class="mi">1</span><span class="w"> </span><span class="n">O</span><span class="w"> </span><span class="n">`</span><span class="mi">7</span><span class="w"> </span><span class="n">$</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mi">71</span><span class="w"></span>\r | |
| 345 | </pre></div></div></div>\r | |
| 346 | <div class="paragraph"><p>That is, we’ve defined a syntax for writing octal integer constants,\r | |
| 347 | with a special syntax, <span class="monospaced">O</span>, for the zero digit (admittedly\r | |
| 348 | contrived, since one could just write <span class="monospaced">`0</span> instead of <span class="monospaced">O</span>).</p></div>\r | |
| 349 | <div class="paragraph"><p>See <a href="NumericLiteral">NumericLiteral</a> for a practical extension of this approach that\r | |
| 350 | supports numeric constants in any base and of any type.</p></div>\r | |
| 351 | </div>\r | |
| 352 | </div>\r | |
| 353 | <div class="sect1">\r | |
| 354 | <h2 id="_seemingly_dependent_types">(Seemingly) dependent types</h2>\r | |
| 355 | <div class="sectionbody">\r | |
| 356 | <div class="paragraph"><p>A normal list fold always returns the same type no matter what\r | |
| 357 | elements are in the list or how long the list is. Variable-argument\r | |
| 358 | fold is more powerful, because the result type can vary based both on\r | |
| 359 | the arguments that are passed and on their number. This can provide\r | |
| 360 | the illusion of dependent types.</p></div>\r | |
| 361 | <div class="paragraph"><p>For example, consider the following.</p></div>\r | |
| 362 | <div class="listingblock">\r | |
| 363 | <div class="content"><div class="highlight"><pre><span class="k">val</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">fn</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">Fold</span><span class="p">.</span><span class="n">fold</span><span class="w"> </span><span class="p">((),</span><span class="w"> </span><span class="n">id</span><span class="p">)</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 364 | <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="k">fn</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">Fold</span><span class="p">.</span><span class="n">step0</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="s">"hello"</span><span class="p">)</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 365 | <span class="k">val</span><span class="w"> </span><span class="n">b</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">=></span><span class="w"> </span><span class="n">Fold</span><span class="p">.</span><span class="n">step0</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="mi">13</span><span class="p">)</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 366 | <span class="k">val</span><span class="w"> </span><span class="n">c</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">=></span><span class="w"> </span><span class="n">Fold</span><span class="p">.</span><span class="n">step0</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="mi">2</span><span class="p">))</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 367 | </pre></div></div></div>\r | |
| 368 | <div class="paragraph"><p>Using the fold equation, one can verify the following equations.</p></div>\r | |
| 369 | <div class="listingblock">\r | |
| 370 | <div class="content"><div class="highlight"><pre><span class="n">f</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">$</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="s">"hello"</span><span class="p">:</span><span class="w"> </span><span class="n">string</span><span class="w"></span>\r | |
| 371 | <span class="n">f</span><span class="w"> </span><span class="n">b</span><span class="w"> </span><span class="n">$</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mi">13</span><span class="p">:</span><span class="w"> </span><span class="n">int</span><span class="w"></span>\r | |
| 372 | <span class="n">f</span><span class="w"> </span><span class="n">c</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="mi">1</span><span class="p">,</span><span class="w"> </span><span class="mi">2</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>\r | |
| 373 | </pre></div></div></div>\r | |
| 374 | <div class="paragraph"><p>That is, <span class="monospaced">f</span> returns a value of a different type depending on\r | |
| 375 | whether it is applied to argument <span class="monospaced">a</span>, argument <span class="monospaced">b</span>, or\r | |
| 376 | argument <span class="monospaced">c</span>.</p></div>\r | |
| 377 | <div class="paragraph"><p>The following example shows how the type of a fold can depend on the\r | |
| 378 | number of arguments.</p></div>\r | |
| 379 | <div class="listingblock">\r | |
| 380 | <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">grow</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">=></span><span class="w"> </span><span class="n">Fold</span><span class="p">.</span><span class="n">fold</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">l</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">l</span><span class="p">)</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 381 | <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="k">fn</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">Fold</span><span class="p">.</span><span class="n">step0</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">=></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">z</span><span class="w"></span>\r | |
| 382 | </pre></div></div></div>\r | |
| 383 | <div class="paragraph"><p>Using the fold equation, one can verify the following equations.</p></div>\r | |
| 384 | <div class="listingblock">\r | |
| 385 | <div class="content"><div class="highlight"><pre><span class="n">grow</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="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">list</span><span class="w"></span>\r | |
| 386 | <span class="n">grow</span><span class="w"> </span><span class="n">a</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="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">list</span><span class="w"> </span><span class="n">list</span><span class="w"></span>\r | |
| 387 | <span class="n">grow</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">a</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="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">list</span><span class="w"> </span><span class="n">list</span><span class="w"> </span><span class="n">list</span><span class="w"></span>\r | |
| 388 | </pre></div></div></div>\r | |
| 389 | <div class="paragraph"><p>Clearly, the result type of a call to the variable argument <span class="monospaced">grow</span>\r | |
| 390 | function depends on the number of arguments that are passed.</p></div>\r | |
| 391 | <div class="paragraph"><p>As a reminder, this is well-typed SML. You can check it out in any\r | |
| 392 | implementation.</p></div>\r | |
| 393 | </div>\r | |
| 394 | </div>\r | |
| 395 | <div class="sect1">\r | |
| 396 | <h2 id="_seemingly_dependently_typed_functional_results">(Seemingly) dependently-typed functional results</h2>\r | |
| 397 | <div class="sectionbody">\r | |
| 398 | <div class="paragraph"><p>Fold is especially useful when it returns a curried function whose\r | |
| 399 | arity depends on the number of arguments. For example, consider the\r | |
| 400 | following.</p></div>\r | |
| 401 | <div class="listingblock">\r | |
| 402 | <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">makeSum</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">=></span><span class="w"> </span><span class="n">Fold</span><span class="p">.</span><span class="n">fold</span><span class="w"> </span><span class="p">(</span><span class="n">id</span><span class="p">,</span><span class="w"> </span><span class="k">fn</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="mi">0</span><span class="p">)</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 403 | <span class="k">val</span><span class="w"> </span><span class="n">I</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">=></span><span class="w"> </span><span class="n">Fold</span><span class="p">.</span><span class="n">step0</span><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">=></span><span class="w"> </span><span class="k">fn</span><span class="w"> </span><span class="n">i</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">x</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">(</span><span class="n">x</span><span class="w"> </span><span class="n">+</span><span class="w"> </span><span class="n">i</span><span class="p">))</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 404 | </pre></div></div></div>\r | |
| 405 | <div class="paragraph"><p>The <span class="monospaced">makeSum</span> folder constructs a function whose arity depends on\r | |
| 406 | the number of <span class="monospaced">I</span> arguments and that adds together all of its\r | |
| 407 | arguments. For example,\r | |
| 408 | <span class="monospaced">makeSum I $</span> is of type <span class="monospaced">int -> int</span> and\r | |
| 409 | <span class="monospaced">makeSum I I $</span> is of type <span class="monospaced">int -> int -> int</span>.</p></div>\r | |
| 410 | <div class="paragraph"><p>One can use the fold equation to verify that the <span class="monospaced">makeSum</span> works\r | |
| 411 | correctly. For example, one can easily check by hand the following\r | |
| 412 | equations.</p></div>\r | |
| 413 | <div class="listingblock">\r | |
| 414 | <div class="content"><div class="highlight"><pre><span class="n">makeSum</span><span class="w"> </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="w"> </span><span class="p">=</span><span class="w"> </span><span class="mi">1</span><span class="w"></span>\r | |
| 415 | <span class="n">makeSum</span><span class="w"> </span><span class="n">I</span><span class="w"> </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="w"> </span><span class="mi">2</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mi">3</span><span class="w"></span>\r | |
| 416 | <span class="n">makeSum</span><span class="w"> </span><span class="n">I</span><span class="w"> </span><span class="n">I</span><span class="w"> </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="w"> </span><span class="mi">2</span><span class="w"> </span><span class="mi">3</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mi">6</span><span class="w"></span>\r | |
| 417 | </pre></div></div></div>\r | |
| 418 | <div class="paragraph"><p>Returning a function becomes especially interesting when there are\r | |
| 419 | steppers of different types. For example, the following <span class="monospaced">makeSum</span>\r | |
| 420 | folder constructs functions that sum integers and reals.</p></div>\r | |
| 421 | <div class="listingblock">\r | |
| 422 | <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">makeSum</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">=></span><span class="w"> </span><span class="n">Foldr</span><span class="p">.</span><span class="n">foldr</span><span class="w"> </span><span class="p">(</span><span class="n">id</span><span class="p">,</span><span class="w"> </span><span class="k">fn</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="mf">0.0</span><span class="p">)</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 423 | <span class="k">val</span><span class="w"> </span><span class="n">I</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">=></span><span class="w"> </span><span class="n">Foldr</span><span class="p">.</span><span class="n">step0</span><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">=></span><span class="w"> </span><span class="k">fn</span><span class="w"> </span><span class="n">x</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">i</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">(</span><span class="n">x</span><span class="w"> </span><span class="n">+</span><span class="w"> </span><span class="n">real</span><span class="w"> </span><span class="n">i</span><span class="p">))</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 424 | <span class="k">val</span><span class="w"> </span><span class="n">R</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">=></span><span class="w"> </span><span class="n">Foldr</span><span class="p">.</span><span class="n">step0</span><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">=></span><span class="w"> </span><span class="k">fn</span><span class="w"> </span><span class="n">x</span><span class="p">:</span><span class="w"> </span><span class="n">real</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">r</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">(</span><span class="n">x</span><span class="w"> </span><span class="n">+</span><span class="w"> </span><span class="n">r</span><span class="p">))</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 425 | </pre></div></div></div>\r | |
| 426 | <div class="paragraph"><p>With these definitions, <span class="monospaced">makeSum I R $</span> is of type\r | |
| 427 | <span class="monospaced">int -> real -> real</span> and <span class="monospaced">makeSum R I I $</span> is of type\r | |
| 428 | <span class="monospaced">real -> int -> int -> real</span>. One can use the foldr equation to\r | |
| 429 | check the following equations.</p></div>\r | |
| 430 | <div class="listingblock">\r | |
| 431 | <div class="content"><div class="highlight"><pre><span class="n">makeSum</span><span class="w"> </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="w"> </span><span class="p">=</span><span class="w"> </span><span class="mf">1.0</span><span class="w"></span>\r | |
| 432 | <span class="n">makeSum</span><span class="w"> </span><span class="n">I</span><span class="w"> </span><span class="n">R</span><span class="w"> </span><span class="n">$</span><span class="w"> </span><span class="mi">1</span><span class="w"> </span><span class="mf">2.5</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mf">3.5</span><span class="w"></span>\r | |
| 433 | <span class="n">makeSum</span><span class="w"> </span><span class="n">R</span><span class="w"> </span><span class="n">I</span><span class="w"> </span><span class="n">I</span><span class="w"> </span><span class="n">$</span><span class="w"> </span><span class="mf">1.5</span><span class="w"> </span><span class="mi">2</span><span class="w"> </span><span class="mi">3</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mf">6.5</span><span class="w"></span>\r | |
| 434 | </pre></div></div></div>\r | |
| 435 | <div class="paragraph"><p>We used <span class="monospaced">foldr</span> instead of <span class="monospaced">fold</span> for this so that the order\r | |
| 436 | in which the specifiers <span class="monospaced">I</span> and <span class="monospaced">R</span> appear is the same as the\r | |
| 437 | order in which the arguments appear. Had we used <span class="monospaced">fold</span>, things\r | |
| 438 | would have been reversed.</p></div>\r | |
| 439 | <div class="paragraph"><p>An extension of this idea is sufficient to define <a href="Printf">Printf</a>-like\r | |
| 440 | functions in SML.</p></div>\r | |
| 441 | </div>\r | |
| 442 | </div>\r | |
| 443 | <div class="sect1">\r | |
| 444 | <h2 id="_an_idiom_for_combining_steps">An idiom for combining steps</h2>\r | |
| 445 | <div class="sectionbody">\r | |
| 446 | <div class="paragraph"><p>It is sometimes useful to combine a number of steps together and name\r | |
| 447 | them as a single step. As a simple example, suppose that one often\r | |
| 448 | sees an integer follower by a real in the <span class="monospaced">makeSum</span> example above.\r | |
| 449 | One can define a new <em>compound step</em> <span class="monospaced">IR</span> as follows.</p></div>\r | |
| 450 | <div class="listingblock">\r | |
| 451 | <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">IR</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">u</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">Fold</span><span class="p">.</span><span class="n">fold</span><span class="w"> </span><span class="n">u</span><span class="w"> </span><span class="n">I</span><span class="w"> </span><span class="n">R</span><span class="w"></span>\r | |
| 452 | </pre></div></div></div>\r | |
| 453 | <div class="paragraph"><p>With this definition in place, one can verify the following.</p></div>\r | |
| 454 | <div class="listingblock">\r | |
| 455 | <div class="content"><div class="highlight"><pre><span class="n">makeSum</span><span class="w"> </span><span class="n">IR</span><span class="w"> </span><span class="n">IR</span><span class="w"> </span><span class="n">$</span><span class="w"> </span><span class="mi">1</span><span class="w"> </span><span class="mf">2.2</span><span class="w"> </span><span class="mi">3</span><span class="w"> </span><span class="mf">4.4</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mf">10.6</span><span class="w"></span>\r | |
| 456 | </pre></div></div></div>\r | |
| 457 | <div class="paragraph"><p>In general, one can combine steps <span class="monospaced">s1</span>, <span class="monospaced">s2</span>, … <span class="monospaced">sn</span> as</p></div>\r | |
| 458 | <div class="listingblock">\r | |
| 459 | <div class="content"><div class="highlight"><pre><span class="k">fn</span><span class="w"> </span><span class="n">u</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">Fold</span><span class="p">.</span><span class="n">fold</span><span class="w"> </span><span class="n">u</span><span class="w"> </span><span class="n">s1</span><span class="w"> </span><span class="n">s2</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="n">sn</span><span class="w"></span>\r | |
| 460 | </pre></div></div></div>\r | |
| 461 | <div class="paragraph"><p>The following calculation shows why a compound step behaves as the\r | |
| 462 | composition of its constituent steps.</p></div>\r | |
| 463 | <div class="listingblock">\r | |
| 464 | <div class="content"><div class="highlight"><pre><span class="n">fold</span><span class="w"> </span><span class="n">u</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">u</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="n">u</span><span class="w"> </span><span class="n">s1</span><span class="w"> </span><span class="n">s2</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="n">sn</span><span class="p">)</span><span class="w"></span>\r | |
| 465 | <span class="p">=</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">u</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="n">u</span><span class="w"> </span><span class="n">s1</span><span class="w"> </span><span class="n">s2</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="n">sn</span><span class="p">)</span><span class="w"> </span><span class="n">u</span><span class="w"></span>\r | |
| 466 | <span class="p">=</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="n">u</span><span class="w"> </span><span class="n">s1</span><span class="w"> </span><span class="n">s2</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="n">sn</span><span class="w"></span>\r | |
| 467 | </pre></div></div></div>\r | |
| 468 | </div>\r | |
| 469 | </div>\r | |
| 470 | <div class="sect1">\r | |
| 471 | <h2 id="_post_composition">Post composition</h2>\r | |
| 472 | <div class="sectionbody">\r | |
| 473 | <div class="paragraph"><p>Suppose we already have a function defined via fold,\r | |
| 474 | <span class="monospaced">w = fold (a, f)</span>, and we would like to construct a new fold\r | |
| 475 | function that is like <span class="monospaced">w</span>, but applies <span class="monospaced">g</span> to the result\r | |
| 476 | produced by <span class="monospaced">w</span>. This is similar to function composition, but we\r | |
| 477 | can’t just do <span class="monospaced">g o w</span>, because we don’t want to use <span class="monospaced">g</span> until\r | |
| 478 | <span class="monospaced">w</span> has been applied to all of its arguments and received the\r | |
| 479 | end-of-arguments terminator <span class="monospaced">$</span>.</p></div>\r | |
| 480 | <div class="paragraph"><p>More precisely, we want to define a post-composition function\r | |
| 481 | <span class="monospaced">post</span> that satisfies the following equation.</p></div>\r | |
| 482 | <div class="listingblock">\r | |
| 483 | <div class="content"><div class="highlight"><pre><span class="n">post</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">g</span><span class="p">)</span><span class="w"> </span><span class="n">s1</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="n">sn</span><span class="w"> </span><span class="n">$</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="p">(</span><span class="n">w</span><span class="w"> </span><span class="n">s1</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="n">sn</span><span class="w"> </span><span class="n">$</span><span class="p">)</span><span class="w"></span>\r | |
| 484 | </pre></div></div></div>\r | |
| 485 | <div class="paragraph"><p>Here is the definition of <span class="monospaced">post</span>.</p></div>\r | |
| 486 | <div class="listingblock">\r | |
| 487 | <div class="content"><div class="highlight"><pre><span class="k">structure</span><span class="w"> </span><span class="n">Fold</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
| 488 | <span class="w"> </span><span class="k">struct</span><span class="w"></span>\r | |
| 489 | <span class="w"> </span><span class="k">open</span><span class="w"> </span><span class="n">Fold</span><span class="w"></span>\r | |
| 490 | <span class="w"> </span><span class="k">fun</span><span class="w"> </span><span class="n">post</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">g</span><span class="p">)</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">w</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">a</span><span class="p">,</span><span class="w"> </span><span class="n">h</span><span class="p">)</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">s</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">g</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">h</span><span class="p">))</span><span class="w"></span>\r | |
| 491 | <span class="w"> </span><span class="k">end</span><span class="w"></span>\r | |
| 492 | </pre></div></div></div>\r | |
| 493 | <div class="paragraph"><p>The following calculations show that <span class="monospaced">post</span> satisfies the desired\r | |
| 494 | equation, where <span class="monospaced">w = fold (a, f)</span>.</p></div>\r | |
| 495 | <div class="listingblock">\r | |
| 496 | <div class="content"><div class="highlight"><pre><span class="n">post</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">g</span><span class="p">)</span><span class="w"> </span><span class="n">s</span><span class="w"></span>\r | |
| 497 | <span class="p">=</span><span class="w"> </span><span class="n">w</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">a</span><span class="p">,</span><span class="w"> </span><span class="n">h</span><span class="p">)</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">s</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">g</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">h</span><span class="p">))</span><span class="w"></span>\r | |
| 498 | <span class="p">=</span><span class="w"> </span><span class="n">fold</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">f</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">a</span><span class="p">,</span><span class="w"> </span><span class="n">h</span><span class="p">)</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">s</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">g</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">h</span><span class="p">))</span><span class="w"></span>\r | |
| 499 | <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">a</span><span class="p">,</span><span class="w"> </span><span class="n">h</span><span class="p">)</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">s</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">g</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">h</span><span class="p">))</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">f</span><span class="p">)</span><span class="w"></span>\r | |
| 500 | <span class="p">=</span><span class="w"> </span><span class="n">s</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">g</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"></span>\r | |
| 501 | <span class="p">=</span><span class="w"> </span><span class="n">fold</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">g</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"> </span><span class="n">s</span><span class="w"></span>\r | |
| 502 | </pre></div></div></div>\r | |
| 503 | <div class="paragraph"><p>Now, suppose <span class="monospaced">si = step0 hi</span> for <span class="monospaced">i</span> from <span class="monospaced">1</span> to <span class="monospaced">n</span>.</p></div>\r | |
| 504 | <div class="listingblock">\r | |
| 505 | <div class="content"><div class="highlight"><pre><span class="n">post</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">g</span><span class="p">)</span><span class="w"> </span><span class="n">s1</span><span class="w"> </span><span class="n">s2</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="n">sn</span><span class="w"> </span><span class="n">$</span><span class="w"></span>\r | |
| 506 | <span class="p">=</span><span class="w"> </span><span class="n">fold</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">g</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"> </span><span class="n">s1</span><span class="w"> </span><span class="n">s2</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="n">sn</span><span class="w"> </span><span class="n">$</span><span class="w"></span>\r | |
| 507 | <span class="p">=</span><span class="w"> </span><span class="p">(</span><span class="n">g</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"> </span><span class="p">(</span><span class="n">hn</span><span class="w"> </span><span class="p">(...</span><span class="w"> </span><span class="p">(</span><span class="n">h1</span><span class="w"> </span><span class="n">a</span><span class="p">)))</span><span class="w"></span>\r | |
| 508 | <span class="p">=</span><span class="w"> </span><span class="n">g</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">hn</span><span class="w"> </span><span class="p">(...</span><span class="w"> </span><span class="p">(</span><span class="n">h1</span><span class="w"> </span><span class="n">a</span><span class="p">))))</span><span class="w"></span>\r | |
| 509 | <span class="p">=</span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="p">(</span><span class="n">fold</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">f</span><span class="p">)</span><span class="w"> </span><span class="n">s1</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="n">sn</span><span class="w"> </span><span class="n">$</span><span class="p">)</span><span class="w"></span>\r | |
| 510 | <span class="p">=</span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="p">(</span><span class="n">w</span><span class="w"> </span><span class="n">s1</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="n">sn</span><span class="w"> </span><span class="n">$</span><span class="p">)</span><span class="w"></span>\r | |
| 511 | </pre></div></div></div>\r | |
| 512 | <div class="paragraph"><p>For a practical example of post composition, see <a href="ArrayLiteral">ArrayLiteral</a>.</p></div>\r | |
| 513 | </div>\r | |
| 514 | </div>\r | |
| 515 | <div class="sect1">\r | |
| 516 | <h2 id="_lift">Lift</h2>\r | |
| 517 | <div class="sectionbody">\r | |
| 518 | <div class="paragraph"><p>We now define a peculiar-looking function, <span class="monospaced">lift0</span>, that is,\r | |
| 519 | equationally speaking, equivalent to the identity function on a step\r | |
| 520 | function.</p></div>\r | |
| 521 | <div class="listingblock">\r | |
| 522 | <div class="content"><div class="highlight"><pre><span class="k">fun</span><span class="w"> </span><span class="n">lift0</span><span class="w"> </span><span class="n">s</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">f</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="p">(</span><span class="n">fold</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">id</span><span class="p">)</span><span class="w"> </span><span class="n">s</span><span class="w"> </span><span class="n">$</span><span class="p">,</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"></span>\r | |
| 523 | </pre></div></div></div>\r | |
| 524 | <div class="paragraph"><p>Using the definitions, we can prove the following equation.</p></div>\r | |
| 525 | <div class="listingblock">\r | |
| 526 | <div class="content"><div class="highlight"><pre><span class="n">fold</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">f</span><span class="p">)</span><span class="w"> </span><span class="p">(</span><span class="n">lift0</span><span class="w"> </span><span class="p">(</span><span class="n">step0</span><span class="w"> </span><span class="n">h</span><span class="p">))</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">fold</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">f</span><span class="p">)</span><span class="w"> </span><span class="p">(</span><span class="n">step0</span><span class="w"> </span><span class="n">h</span><span class="p">)</span><span class="w"></span>\r | |
| 527 | </pre></div></div></div>\r | |
| 528 | <div class="paragraph"><p>Here is the proof.</p></div>\r | |
| 529 | <div class="listingblock">\r | |
| 530 | <div class="content"><div class="highlight"><pre><span class="n">fold</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">f</span><span class="p">)</span><span class="w"> </span><span class="p">(</span><span class="n">lift0</span><span class="w"> </span><span class="p">(</span><span class="n">step0</span><span class="w"> </span><span class="n">h</span><span class="p">))</span><span class="w"></span>\r | |
| 531 | <span class="p">=</span><span class="w"> </span><span class="n">lift0</span><span class="w"> </span><span class="p">(</span><span class="n">step0</span><span class="w"> </span><span class="n">h</span><span class="p">)</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">f</span><span class="p">)</span><span class="w"></span>\r | |
| 532 | <span class="p">=</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="p">(</span><span class="n">fold</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">id</span><span class="p">)</span><span class="w"> </span><span class="p">(</span><span class="n">step0</span><span class="w"> </span><span class="n">h</span><span class="p">)</span><span class="w"> </span><span class="n">$</span><span class="p">,</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"></span>\r | |
| 533 | <span class="p">=</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="p">(</span><span class="n">step0</span><span class="w"> </span><span class="n">h</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">id</span><span class="p">)</span><span class="w"> </span><span class="n">$</span><span class="p">,</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"></span>\r | |
| 534 | <span class="p">=</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="p">(</span><span class="n">fold</span><span class="w"> </span><span class="p">(</span><span class="n">h</span><span class="w"> </span><span class="n">a</span><span class="p">,</span><span class="w"> </span><span class="n">id</span><span class="p">)</span><span class="w"> </span><span class="n">$</span><span class="p">,</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"></span>\r | |
| 535 | <span class="p">=</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="p">(</span><span class="n">$</span><span class="w"> </span><span class="p">(</span><span class="n">h</span><span class="w"> </span><span class="n">a</span><span class="p">,</span><span class="w"> </span><span class="n">id</span><span class="p">),</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"></span>\r | |
| 536 | <span class="p">=</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="p">(</span><span class="n">id</span><span class="w"> </span><span class="p">(</span><span class="n">h</span><span class="w"> </span><span class="n">a</span><span class="p">),</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"></span>\r | |
| 537 | <span class="p">=</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="p">(</span><span class="n">h</span><span class="w"> </span><span class="n">a</span><span class="p">,</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"></span>\r | |
| 538 | <span class="p">=</span><span class="w"> </span><span class="n">step0</span><span class="w"> </span><span class="n">h</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">f</span><span class="p">)</span><span class="w"></span>\r | |
| 539 | <span class="p">=</span><span class="w"> </span><span class="n">fold</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">f</span><span class="p">)</span><span class="w"> </span><span class="p">(</span><span class="n">step0</span><span class="w"> </span><span class="n">h</span><span class="p">)</span><span class="w"></span>\r | |
| 540 | </pre></div></div></div>\r | |
| 541 | <div class="paragraph"><p>If <span class="monospaced">lift0</span> is the identity, then why even define it? The answer\r | |
| 542 | lies in the typing of fold expressions, which we have, until now, left\r | |
| 543 | unexplained.</p></div>\r | |
| 544 | </div>\r | |
| 545 | </div>\r | |
| 546 | <div class="sect1">\r | |
| 547 | <h2 id="_typing">Typing</h2>\r | |
| 548 | <div class="sectionbody">\r | |
| 549 | <div class="paragraph"><p>Perhaps the most surprising aspect of fold is that it can be checked\r | |
| 550 | by the SML type system. The types involved in fold expressions are\r | |
| 551 | complex; fortunately type inference is able to deduce them.\r | |
| 552 | Nevertheless, it is instructive to study the types of fold functions\r | |
| 553 | and steppers. More importantly, it is essential to understand the\r | |
| 554 | typing aspects of fold in order to write down signatures of functions\r | |
| 555 | defined using fold and step.</p></div>\r | |
| 556 | <div class="paragraph"><p>Here is the <span class="monospaced">FOLD</span> signature, and a recapitulation of the entire\r | |
| 557 | <span class="monospaced">Fold</span> structure, with additional type annotations.</p></div>\r | |
| 558 | <div class="listingblock">\r | |
| 559 | <div class="content"><div class="highlight"><pre><span class="k">signature</span><span class="w"> </span><span class="n">FOLD</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
| 560 | <span class="w"> </span><span class="k">sig</span><span class="w"></span>\r | |
| 561 | <span class="w"> </span><span class="k">type</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">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">step</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="p">(</span><span class="n">'b</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'c</span><span class="p">)</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'d</span><span class="w"></span>\r | |
| 562 | <span class="w"> </span><span class="k">type</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">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</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">'a</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">step</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'d</span><span class="w"></span>\r | |
| 563 | <span class="w"> </span><span class="k">type</span><span class="w"> </span><span class="p">(</span><span class="n">'a1</span><span class="p">,</span><span class="w"> </span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">step0</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
| 564 | <span class="w"> </span><span class="p">(</span><span class="n">'a1</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="p">(</span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">t</span><span class="p">)</span><span class="w"> </span><span class="n">step</span><span class="w"></span>\r | |
| 565 | <span class="w"> </span><span class="k">type</span><span class="w"> </span><span class="p">(</span><span class="n">'a11</span><span class="p">,</span><span class="w"> </span><span class="n">'a12</span><span class="p">,</span><span class="w"> </span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">step1</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
| 566 | <span class="w"> </span><span class="p">(</span><span class="n">'a12</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'a11</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="p">(</span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">t</span><span class="p">)</span><span class="w"> </span><span class="n">step</span><span class="w"></span>\r | |
| 567 | \r | |
| 568 | <span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">fold</span><span class="p">:</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="p">(</span><span class="n">'b</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'c</span><span class="p">)</span><span class="w"> </span><span class="p">-></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">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">t</span><span class="w"></span>\r | |
| 569 | <span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">lift0</span><span class="p">:</span><span class="w"> </span><span class="p">(</span><span class="n">'a1</span><span class="p">,</span><span class="w"> </span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'a2</span><span class="p">)</span><span class="w"> </span><span class="n">step0</span><span class="w"></span>\r | |
| 570 | <span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="p">(</span><span class="n">'a1</span><span class="p">,</span><span class="w"> </span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">step0</span><span class="w"></span>\r | |
| 571 | <span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">post</span><span class="p">:</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">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c1</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</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">'c1</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'c2</span><span class="p">)</span><span class="w"></span>\r | |
| 572 | <span class="w"> </span><span class="p">-></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">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c2</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">t</span><span class="w"></span>\r | |
| 573 | <span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">step0</span><span class="p">:</span><span class="w"> </span><span class="p">(</span><span class="n">'a1</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'a2</span><span class="p">)</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="p">(</span><span class="n">'a1</span><span class="p">,</span><span class="w"> </span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">step0</span><span class="w"></span>\r | |
| 574 | <span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">step1</span><span class="p">:</span><span class="w"> </span><span class="p">(</span><span class="n">'a11</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">'a12</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'a2</span><span class="p">)</span><span class="w"></span>\r | |
| 575 | <span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="p">(</span><span class="n">'a11</span><span class="p">,</span><span class="w"> </span><span class="n">'a12</span><span class="p">,</span><span class="w"> </span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">step1</span><span class="w"></span>\r | |
| 576 | <span class="w"> </span><span class="k">end</span><span class="w"></span>\r | |
| 577 | \r | |
| 578 | <span class="k">structure</span><span class="w"> </span><span class="n">Fold</span><span class="p">:></span><span class="w"> </span><span class="n">FOLD</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
| 579 | <span class="w"> </span><span class="k">struct</span><span class="w"></span>\r | |
| 580 | <span class="w"> </span><span class="k">type</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">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">step</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="p">(</span><span class="n">'b</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'c</span><span class="p">)</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'d</span><span class="w"></span>\r | |
| 581 | \r | |
| 582 | <span class="w"> </span><span class="k">type</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">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</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">'a</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">step</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'d</span><span class="w"></span>\r | |
| 583 | \r | |
| 584 | <span class="w"> </span><span class="k">type</span><span class="w"> </span><span class="p">(</span><span class="n">'a1</span><span class="p">,</span><span class="w"> </span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">step0</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
| 585 | <span class="w"> </span><span class="p">(</span><span class="n">'a1</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="p">(</span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">t</span><span class="p">)</span><span class="w"> </span><span class="n">step</span><span class="w"></span>\r | |
| 586 | \r | |
| 587 | <span class="w"> </span><span class="k">type</span><span class="w"> </span><span class="p">(</span><span class="n">'a11</span><span class="p">,</span><span class="w"> </span><span class="n">'a12</span><span class="p">,</span><span class="w"> </span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">step1</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
| 588 | <span class="w"> </span><span class="p">(</span><span class="n">'a12</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'a11</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="p">(</span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">t</span><span class="p">)</span><span class="w"> </span><span class="n">step</span><span class="w"></span>\r | |
| 589 | \r | |
| 590 | <span class="w"> </span><span class="k">fun</span><span class="w"> </span><span class="n">fold</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">'a</span><span class="p">,</span><span class="w"> </span><span class="n">f</span><span class="p">:</span><span class="w"> </span><span class="n">'b</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'c</span><span class="p">)</span><span class="w"></span>\r | |
| 591 | <span class="w"> </span><span class="p">(</span><span class="n">g</span><span class="p">:</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">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">step</span><span class="p">):</span><span class="w"> </span><span class="n">'d</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
| 592 | <span class="w"> </span><span class="n">g</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">f</span><span class="p">)</span><span class="w"></span>\r | |
| 593 | \r | |
| 594 | <span class="w"> </span><span class="k">fun</span><span class="w"> </span><span class="n">step0</span><span class="w"> </span><span class="p">(</span><span class="n">h</span><span class="p">:</span><span class="w"> </span><span class="n">'a1</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'a2</span><span class="p">)</span><span class="w"></span>\r | |
| 595 | <span class="w"> </span><span class="p">(</span><span class="n">a1</span><span class="p">:</span><span class="w"> </span><span class="n">'a1</span><span class="p">,</span><span class="w"> </span><span class="n">f</span><span class="p">:</span><span class="w"> </span><span class="n">'b</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'c</span><span class="p">):</span><span class="w"> </span><span class="p">(</span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
| 596 | <span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="p">(</span><span class="n">h</span><span class="w"> </span><span class="n">a1</span><span class="p">,</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"></span>\r | |
| 597 | \r | |
| 598 | <span class="w"> </span><span class="k">fun</span><span class="w"> </span><span class="n">step1</span><span class="w"> </span><span class="p">(</span><span class="n">h</span><span class="p">:</span><span class="w"> </span><span class="n">'a11</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">'a12</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'a2</span><span class="p">)</span><span class="w"></span>\r | |
| 599 | <span class="w"> </span><span class="p">(</span><span class="n">a12</span><span class="p">:</span><span class="w"> </span><span class="n">'a12</span><span class="p">,</span><span class="w"> </span><span class="n">f</span><span class="p">:</span><span class="w"> </span><span class="n">'b</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'c</span><span class="p">)</span><span class="w"></span>\r | |
| 600 | <span class="w"> </span><span class="p">(</span><span class="n">a11</span><span class="p">:</span><span class="w"> </span><span class="n">'a11</span><span class="p">):</span><span class="w"> </span><span class="p">(</span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
| 601 | <span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="p">(</span><span class="n">h</span><span class="w"> </span><span class="p">(</span><span class="n">a11</span><span class="p">,</span><span class="w"> </span><span class="n">a12</span><span class="p">),</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"></span>\r | |
| 602 | \r | |
| 603 | <span class="w"> </span><span class="k">fun</span><span class="w"> </span><span class="n">lift0</span><span class="w"> </span><span class="p">(</span><span class="n">s</span><span class="p">:</span><span class="w"> </span><span class="p">(</span><span class="n">'a1</span><span class="p">,</span><span class="w"> </span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'a2</span><span class="p">)</span><span class="w"> </span><span class="n">step0</span><span class="p">)</span><span class="w"></span>\r | |
| 604 | <span class="w"> </span><span class="p">(</span><span class="n">a</span><span class="p">:</span><span class="w"> </span><span class="n">'a1</span><span class="p">,</span><span class="w"> </span><span class="n">f</span><span class="p">:</span><span class="w"> </span><span class="n">'b</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'c</span><span class="p">):</span><span class="w"> </span><span class="p">(</span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
| 605 | <span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="p">(</span><span class="n">fold</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">id</span><span class="p">)</span><span class="w"> </span><span class="n">s</span><span class="w"> </span><span class="n">$</span><span class="p">,</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"></span>\r | |
| 606 | \r | |
| 607 | <span class="w"> </span><span class="k">fun</span><span class="w"> </span><span class="n">post</span><span class="w"> </span><span class="p">(</span><span class="n">w</span><span class="p">:</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">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c1</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">t</span><span class="p">,</span><span class="w"></span>\r | |
| 608 | <span class="w"> </span><span class="n">g</span><span class="p">:</span><span class="w"> </span><span class="n">'c1</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'c2</span><span class="p">)</span><span class="w"></span>\r | |
| 609 | <span class="w"> </span><span class="p">(</span><span class="n">s</span><span class="p">:</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">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c2</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">step</span><span class="p">):</span><span class="w"> </span><span class="n">'d</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
| 610 | <span class="w"> </span><span class="n">w</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">a</span><span class="p">,</span><span class="w"> </span><span class="n">h</span><span class="p">)</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">s</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">g</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">h</span><span class="p">))</span><span class="w"></span>\r | |
| 611 | <span class="w"> </span><span class="k">end</span><span class="w"></span>\r | |
| 612 | </pre></div></div></div>\r | |
| 613 | <div class="paragraph"><p>That’s a lot to swallow, so let’s walk through it one step at a time.\r | |
| 614 | First, we have the definition of type <span class="monospaced">Fold.step</span>.</p></div>\r | |
| 615 | <div class="listingblock">\r | |
| 616 | <div class="content"><div class="highlight"><pre><span class="k">type</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">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">step</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="p">(</span><span class="n">'b</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'c</span><span class="p">)</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'d</span><span class="w"></span>\r | |
| 617 | </pre></div></div></div>\r | |
| 618 | <div class="paragraph"><p>As a fold proceeds over its arguments, it maintains two things: the\r | |
| 619 | accumulator, of type <span class="monospaced">'a</span>, and the finishing function, of type\r | |
| 620 | <span class="monospaced">'b -> 'c</span>. Each step in the fold is a function that takes those\r | |
| 621 | two pieces (i.e. <span class="monospaced">'a * ('b -> 'c)</span> and does something to them\r | |
| 622 | (i.e. produces <span class="monospaced">'d</span>). The result type of the step is completely\r | |
| 623 | left open to be filled in by type inference, as it is an arrow type\r | |
| 624 | that is capable of consuming the rest of the arguments to the fold.</p></div>\r | |
| 625 | <div class="paragraph"><p>A folder, of type <span class="monospaced">Fold.t</span>, is a function that consumes a single\r | |
| 626 | step.</p></div>\r | |
| 627 | <div class="listingblock">\r | |
| 628 | <div class="content"><div class="highlight"><pre><span class="k">type</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">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</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">'a</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">step</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'d</span><span class="w"></span>\r | |
| 629 | </pre></div></div></div>\r | |
| 630 | <div class="paragraph"><p>Expanding out the type, we have:</p></div>\r | |
| 631 | <div class="listingblock">\r | |
| 632 | <div class="content"><div class="highlight"><pre><span class="k">type</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">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</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">'a</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="p">(</span><span class="n">'b</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'c</span><span class="p">)</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'d</span><span class="w"></span>\r | |
| 633 | </pre></div></div></div>\r | |
| 634 | <div class="paragraph"><p>This shows that the only thing a folder does is to hand its\r | |
| 635 | accumulator (<span class="monospaced">'a</span>) and finisher (<span class="monospaced">'b -> 'c</span>) to the next step\r | |
| 636 | (<span class="monospaced">'a * ('b -> 'c) -> 'd</span>). If SML had <a href="FirstClassPolymorphism">first-class polymorphism</a>,\r | |
| 637 | we would write the fold type as follows.</p></div>\r | |
| 638 | <div class="listingblock">\r | |
| 639 | <div class="content"><div class="highlight"><pre><span class="k">type</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">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">)</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">Forall</span><span class="w"> </span><span class="n">'d</span><span class="w"> </span><span class="err">. ('a, 'b, 'c, 'd) step -> 'd</span>\r | |
| 640 | </pre></div></div></div>\r | |
| 641 | <div class="paragraph"><p>This type definition shows that a folder had nothing to do with\r | |
| 642 | the rest of the fold, it only deals with the next step.</p></div>\r | |
| 643 | <div class="paragraph"><p>We now can understand the type of <span class="monospaced">fold</span>, which takes the initial\r | |
| 644 | value of the accumulator and the finishing function, and constructs a\r | |
| 645 | folder, i.e. a function awaiting the next step.</p></div>\r | |
| 646 | <div class="listingblock">\r | |
| 647 | <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">fold</span><span class="p">:</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="p">(</span><span class="n">'b</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'c</span><span class="p">)</span><span class="w"> </span><span class="p">-></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">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">t</span><span class="w"></span>\r | |
| 648 | <span class="k">fun</span><span class="w"> </span><span class="n">fold</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">'a</span><span class="p">,</span><span class="w"> </span><span class="n">f</span><span class="p">:</span><span class="w"> </span><span class="n">'b</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'c</span><span class="p">)</span><span class="w"></span>\r | |
| 649 | <span class="w"> </span><span class="p">(</span><span class="n">g</span><span class="p">:</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">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">step</span><span class="p">):</span><span class="w"> </span><span class="n">'d</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
| 650 | <span class="w"> </span><span class="n">g</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">f</span><span class="p">)</span><span class="w"></span>\r | |
| 651 | </pre></div></div></div>\r | |
| 652 | <div class="paragraph"><p>Continuing on, we have the type of step functions.</p></div>\r | |
| 653 | <div class="listingblock">\r | |
| 654 | <div class="content"><div class="highlight"><pre><span class="k">type</span><span class="w"> </span><span class="p">(</span><span class="n">'a1</span><span class="p">,</span><span class="w"> </span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">step0</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
| 655 | <span class="w"> </span><span class="p">(</span><span class="n">'a1</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="p">(</span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">t</span><span class="p">)</span><span class="w"> </span><span class="n">step</span><span class="w"></span>\r | |
| 656 | </pre></div></div></div>\r | |
| 657 | <div class="paragraph"><p>Expanding out the type a bit gives:</p></div>\r | |
| 658 | <div class="listingblock">\r | |
| 659 | <div class="content"><div class="highlight"><pre><span class="k">type</span><span class="w"> </span><span class="p">(</span><span class="n">'a1</span><span class="p">,</span><span class="w"> </span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">step0</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
| 660 | <span class="w"> </span><span class="n">'a1</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="p">(</span><span class="n">'b</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'c</span><span class="p">)</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="p">(</span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">t</span><span class="w"></span>\r | |
| 661 | </pre></div></div></div>\r | |
| 662 | <div class="paragraph"><p>So, a step function takes the accumulator (<span class="monospaced">'a1</span>) and finishing\r | |
| 663 | function (<span class="monospaced">'b -> 'c</span>), which will be passed to it by the previous\r | |
| 664 | folder, and transforms them to a new folder. This new folder has a\r | |
| 665 | new accumulator (<span class="monospaced">'a2</span>) and the same finishing function.</p></div>\r | |
| 666 | <div class="paragraph"><p>Again, imagining that SML had <a href="FirstClassPolymorphism">first-class polymorphism</a> makes the type\r | |
| 667 | clearer.</p></div>\r | |
| 668 | <div class="listingblock">\r | |
| 669 | <div class="content"><div class="highlight"><pre><span class="k">type</span><span class="w"> </span><span class="p">(</span><span class="n">'a1</span><span class="p">,</span><span class="w"> </span><span class="n">'a2</span><span class="p">)</span><span class="w"> </span><span class="n">step0</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
| 670 | <span class="w"> </span><span class="n">Forall</span><span class="w"> </span><span class="p">(</span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">)</span><span class="w"> </span><span class="err">. ('a1, 'b, 'c, ('a2, 'b, 'c) t) step</span>\r | |
| 671 | </pre></div></div></div>\r | |
| 672 | <div class="paragraph"><p>Thus, in essence, a <span class="monospaced">step0</span> function is a wrapper around a\r | |
| 673 | function of type <span class="monospaced">'a1 -> 'a2</span>, which is exactly what the\r | |
| 674 | definition of <span class="monospaced">step0</span> does.</p></div>\r | |
| 675 | <div class="listingblock">\r | |
| 676 | <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">step0</span><span class="p">:</span><span class="w"> </span><span class="p">(</span><span class="n">'a1</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'a2</span><span class="p">)</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="p">(</span><span class="n">'a1</span><span class="p">,</span><span class="w"> </span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">step0</span><span class="w"></span>\r | |
| 677 | <span class="k">fun</span><span class="w"> </span><span class="n">step0</span><span class="w"> </span><span class="p">(</span><span class="n">h</span><span class="p">:</span><span class="w"> </span><span class="n">'a1</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'a2</span><span class="p">)</span><span class="w"></span>\r | |
| 678 | <span class="w"> </span><span class="p">(</span><span class="n">a1</span><span class="p">:</span><span class="w"> </span><span class="n">'a1</span><span class="p">,</span><span class="w"> </span><span class="n">f</span><span class="p">:</span><span class="w"> </span><span class="n">'b</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'c</span><span class="p">):</span><span class="w"> </span><span class="p">(</span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
| 679 | <span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="p">(</span><span class="n">h</span><span class="w"> </span><span class="n">a1</span><span class="p">,</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"></span>\r | |
| 680 | </pre></div></div></div>\r | |
| 681 | <div class="paragraph"><p>It is not much beyond <span class="monospaced">step0</span> to understand <span class="monospaced">step1</span>.</p></div>\r | |
| 682 | <div class="listingblock">\r | |
| 683 | <div class="content"><div class="highlight"><pre><span class="k">type</span><span class="w"> </span><span class="p">(</span><span class="n">'a11</span><span class="p">,</span><span class="w"> </span><span class="n">'a12</span><span class="p">,</span><span class="w"> </span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">step1</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
| 684 | <span class="w"> </span><span class="p">(</span><span class="n">'a12</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'a11</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="p">(</span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">t</span><span class="p">)</span><span class="w"> </span><span class="n">step</span><span class="w"></span>\r | |
| 685 | </pre></div></div></div>\r | |
| 686 | <div class="paragraph"><p>A <span class="monospaced">step1</span> function takes the accumulator (<span class="monospaced">'a12</span>) and finisher\r | |
| 687 | (<span class="monospaced">'b -> 'c</span>) passed to it by the previous folder and transforms\r | |
| 688 | them into a function that consumes the next argument (<span class="monospaced">'a11</span>) and\r | |
| 689 | produces a folder that will continue the fold with a new accumulator\r | |
| 690 | (<span class="monospaced">'a2</span>) and the same finisher.</p></div>\r | |
| 691 | <div class="listingblock">\r | |
| 692 | <div class="content"><div class="highlight"><pre><span class="k">fun</span><span class="w"> </span><span class="n">step1</span><span class="w"> </span><span class="p">(</span><span class="n">h</span><span class="p">:</span><span class="w"> </span><span class="n">'a11</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">'a12</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'a2</span><span class="p">)</span><span class="w"></span>\r | |
| 693 | <span class="w"> </span><span class="p">(</span><span class="n">a12</span><span class="p">:</span><span class="w"> </span><span class="n">'a12</span><span class="p">,</span><span class="w"> </span><span class="n">f</span><span class="p">:</span><span class="w"> </span><span class="n">'b</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'c</span><span class="p">)</span><span class="w"></span>\r | |
| 694 | <span class="w"> </span><span class="p">(</span><span class="n">a11</span><span class="p">:</span><span class="w"> </span><span class="n">'a11</span><span class="p">):</span><span class="w"> </span><span class="p">(</span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
| 695 | <span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="p">(</span><span class="n">h</span><span class="w"> </span><span class="p">(</span><span class="n">a11</span><span class="p">,</span><span class="w"> </span><span class="n">a12</span><span class="p">),</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"></span>\r | |
| 696 | </pre></div></div></div>\r | |
| 697 | <div class="paragraph"><p>With <a href="FirstClassPolymorphism">first-class polymorphism</a>, a <span class="monospaced">step1</span> function is more clearly\r | |
| 698 | seen as a wrapper around a binary function of type\r | |
| 699 | <span class="monospaced">'a11 * 'a12 -> 'a2</span>.</p></div>\r | |
| 700 | <div class="listingblock">\r | |
| 701 | <div class="content"><div class="highlight"><pre><span class="k">type</span><span class="w"> </span><span class="p">(</span><span class="n">'a11</span><span class="p">,</span><span class="w"> </span><span class="n">'a12</span><span class="p">,</span><span class="w"> </span><span class="n">'a2</span><span class="p">)</span><span class="w"> </span><span class="n">step1</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
| 702 | <span class="w"> </span><span class="n">Forall</span><span class="w"> </span><span class="p">(</span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">)</span><span class="w"> </span><span class="err">. ('a12, 'b, 'c, 'a11 -> ('a2, 'b, 'c) t) step</span>\r | |
| 703 | </pre></div></div></div>\r | |
| 704 | <div class="paragraph"><p>The type of <span class="monospaced">post</span> is clear: it takes a folder with a finishing\r | |
| 705 | function that produces type <span class="monospaced">'c1</span>, and a function of type\r | |
| 706 | <span class="monospaced">'c1 -> 'c2</span> to postcompose onto the folder. It returns a new\r | |
| 707 | folder with a finishing function that produces type <span class="monospaced">'c2</span>.</p></div>\r | |
| 708 | <div class="listingblock">\r | |
| 709 | <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">post</span><span class="p">:</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">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c1</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</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">'c1</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'c2</span><span class="p">)</span><span class="w"></span>\r | |
| 710 | <span class="w"> </span><span class="p">-></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">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c2</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">t</span><span class="w"></span>\r | |
| 711 | <span class="k">fun</span><span class="w"> </span><span class="n">post</span><span class="w"> </span><span class="p">(</span><span class="n">w</span><span class="p">:</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">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c1</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">t</span><span class="p">,</span><span class="w"></span>\r | |
| 712 | <span class="w"> </span><span class="n">g</span><span class="p">:</span><span class="w"> </span><span class="n">'c1</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'c2</span><span class="p">)</span><span class="w"></span>\r | |
| 713 | <span class="w"> </span><span class="p">(</span><span class="n">s</span><span class="p">:</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">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c2</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">step</span><span class="p">):</span><span class="w"> </span><span class="n">'d</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
| 714 | <span class="w"> </span><span class="n">w</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">a</span><span class="p">,</span><span class="w"> </span><span class="n">h</span><span class="p">)</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">s</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">g</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">h</span><span class="p">))</span><span class="w"></span>\r | |
| 715 | </pre></div></div></div>\r | |
| 716 | <div class="paragraph"><p>We will return to <span class="monospaced">lift0</span> after an example.</p></div>\r | |
| 717 | </div>\r | |
| 718 | </div>\r | |
| 719 | <div class="sect1">\r | |
| 720 | <h2 id="_an_example_typing">An example typing</h2>\r | |
| 721 | <div class="sectionbody">\r | |
| 722 | <div class="paragraph"><p>Let’s type check our simplest example, a variable-argument fold.\r | |
| 723 | Recall that we have a folder <span class="monospaced">f</span> and a stepper <span class="monospaced">a</span> defined as\r | |
| 724 | follows.</p></div>\r | |
| 725 | <div class="listingblock">\r | |
| 726 | <div class="content"><div class="highlight"><pre><span class="k">val</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">fn</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">Fold</span><span class="p">.</span><span class="n">fold</span><span class="w"> </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">=></span><span class="w"> </span><span class="p">())</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 727 | <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="k">fn</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">Fold</span><span class="p">.</span><span class="n">step0</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="p">())</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 728 | </pre></div></div></div>\r | |
| 729 | <div class="paragraph"><p>Since the accumulator and finisher are uninteresting, we’ll use some\r | |
| 730 | abbreviations to simplify things.</p></div>\r | |
| 731 | <div class="listingblock">\r | |
| 732 | <div class="content"><div class="highlight"><pre><span class="k">type</span><span class="w"> </span><span class="n">'d</span><span class="w"> </span><span class="n">step</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="p">(</span><span class="n">unit</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">unit</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">Fold</span><span class="p">.</span><span class="n">step</span><span class="w"></span>\r | |
| 733 | <span class="k">type</span><span class="w"> </span><span class="n">'d</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">'d</span><span class="w"> </span><span class="n">step</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'d</span><span class="w"></span>\r | |
| 734 | </pre></div></div></div>\r | |
| 735 | <div class="paragraph"><p>With these abbreviations, <span class="monospaced">f</span> and <span class="monospaced">a</span> have the following polymorphic\r | |
| 736 | types.</p></div>\r | |
| 737 | <div class="listingblock">\r | |
| 738 | <div class="content"><div class="highlight"><pre><span class="n">f</span><span class="p">:</span><span class="w"> </span><span class="n">'d</span><span class="w"> </span><span class="n">fold</span><span class="w"></span>\r | |
| 739 | <span class="n">a</span><span class="p">:</span><span class="w"> </span><span class="n">'d</span><span class="w"> </span><span class="n">step</span><span class="w"></span>\r | |
| 740 | </pre></div></div></div>\r | |
| 741 | <div class="paragraph"><p>Suppose we want to type check</p></div>\r | |
| 742 | <div class="listingblock">\r | |
| 743 | <div class="content"><div class="highlight"><pre><span class="n">f</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">$:</span><span class="w"> </span><span class="n">unit</span><span class="w"></span>\r | |
| 744 | </pre></div></div></div>\r | |
| 745 | <div class="paragraph"><p>As a reminder, the fully parenthesized expression is</p></div>\r | |
| 746 | <div class="listingblock">\r | |
| 747 | <div class="content"><div class="highlight"><pre><span class="p">((((</span><span class="n">f</span><span class="w"> </span><span class="n">a</span><span class="p">)</span><span class="w"> </span><span class="n">a</span><span class="p">)</span><span class="w"> </span><span class="n">a</span><span class="p">)</span><span class="w"> </span><span class="n">a</span><span class="p">)</span><span class="w"> </span><span class="n">$</span><span class="w"></span>\r | |
| 748 | </pre></div></div></div>\r | |
| 749 | <div class="paragraph"><p>The observation that we will use repeatedly is that for any type\r | |
| 750 | <span class="monospaced">z</span>, if <span class="monospaced">f: z fold</span> and <span class="monospaced">s: z step</span>, then <span class="monospaced">f s: z</span>.\r | |
| 751 | So, if we want</p></div>\r | |
| 752 | <div class="listingblock">\r | |
| 753 | <div class="content"><div class="highlight"><pre><span class="p">(</span><span class="n">f</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">a</span><span class="p">)</span><span class="w"> </span><span class="n">$:</span><span class="w"> </span><span class="n">unit</span><span class="w"></span>\r | |
| 754 | </pre></div></div></div>\r | |
| 755 | <div class="paragraph"><p>then we must have</p></div>\r | |
| 756 | <div class="listingblock">\r | |
| 757 | <div class="content"><div class="highlight"><pre><span class="n">f</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">a</span><span class="p">:</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="n">fold</span><span class="w"></span>\r | |
| 758 | <span class="n">$:</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="n">step</span><span class="w"></span>\r | |
| 759 | </pre></div></div></div>\r | |
| 760 | <div class="paragraph"><p>Applying the observation again, we must have</p></div>\r | |
| 761 | <div class="listingblock">\r | |
| 762 | <div class="content"><div class="highlight"><pre><span class="n">f</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">a</span><span class="p">:</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="n">fold</span><span class="w"></span>\r | |
| 763 | <span class="n">a</span><span class="p">:</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="n">step</span><span class="w"></span>\r | |
| 764 | </pre></div></div></div>\r | |
| 765 | <div class="paragraph"><p>Applying the observation two more times leads to the following type\r | |
| 766 | derivation.</p></div>\r | |
| 767 | <div class="listingblock">\r | |
| 768 | <div class="content"><div class="highlight"><pre><span class="n">f</span><span class="p">:</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="n">a</span><span class="p">:</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="n">step</span><span class="w"></span>\r | |
| 769 | <span class="n">f</span><span class="w"> </span><span class="n">a</span><span class="p">:</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="n">a</span><span class="p">:</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="n">step</span><span class="w"></span>\r | |
| 770 | <span class="n">f</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">a</span><span class="p">:</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="n">a</span><span class="p">:</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="n">step</span><span class="w"></span>\r | |
| 771 | <span class="n">f</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">a</span><span class="p">:</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="n">$:</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="n">step</span><span class="w"></span>\r | |
| 772 | <span class="n">f</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">$:</span><span class="w"> </span><span class="n">unit</span><span class="w"></span>\r | |
| 773 | </pre></div></div></div>\r | |
| 774 | <div class="paragraph"><p>So, each application is a fold that consumes the next step, producing\r | |
| 775 | a fold of one smaller type.</p></div>\r | |
| 776 | <div class="paragraph"><p>One can expand some of the type definitions in <span class="monospaced">f</span> to see that it is\r | |
| 777 | indeed a function that takes four curried arguments, each one a step\r | |
| 778 | function.</p></div>\r | |
| 779 | <div class="listingblock">\r | |
| 780 | <div class="content"><div class="highlight"><pre><span class="n">f</span><span class="p">:</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="n">step</span><span class="w"></span>\r | |
| 781 | <span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="n">step</span><span class="w"></span>\r | |
| 782 | <span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="n">step</span><span class="w"></span>\r | |
| 783 | <span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="n">step</span><span class="w"></span>\r | |
| 784 | <span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">unit</span><span class="w"></span>\r | |
| 785 | </pre></div></div></div>\r | |
| 786 | <div class="paragraph"><p>This example shows why we must eta expand uses of <span class="monospaced">fold</span> and <span class="monospaced">step0</span>\r | |
| 787 | to work around the value restriction and make folders and steppers\r | |
| 788 | polymorphic. The type of a fold function like <span class="monospaced">f</span> depends on the\r | |
| 789 | number of arguments, and so will vary from use to use. Similarly,\r | |
| 790 | each occurrence of an argument like <span class="monospaced">a</span> has a different type,\r | |
| 791 | depending on the number of remaining arguments.</p></div>\r | |
| 792 | <div class="paragraph"><p>This example also shows that the type of a folder, when fully\r | |
| 793 | expanded, is exponential in the number of arguments: there are as many\r | |
| 794 | nested occurrences of the <span class="monospaced">fold</span> type constructor as there are\r | |
| 795 | arguments, and each occurrence duplicates its type argument. One can\r | |
| 796 | observe this exponential behavior in a type checker that doesn’t share\r | |
| 797 | enough of the representation of types (e.g. one that represents types\r | |
| 798 | as trees rather than directed acyclic graphs).</p></div>\r | |
| 799 | <div class="paragraph"><p>Generalizing this type derivation to uses of fold where the\r | |
| 800 | accumulator and finisher are more interesting is straightforward. One\r | |
| 801 | simply includes the type of the accumulator, which may change, for\r | |
| 802 | each step, and the type of the finisher, which doesn’t change from\r | |
| 803 | step to step.</p></div>\r | |
| 804 | </div>\r | |
| 805 | </div>\r | |
| 806 | <div class="sect1">\r | |
| 807 | <h2 id="_typing_lift">Typing lift</h2>\r | |
| 808 | <div class="sectionbody">\r | |
| 809 | <div class="paragraph"><p>The lack of <a href="FirstClassPolymorphism">first-class polymorphism</a> in SML\r | |
| 810 | causes problems if one wants to use a step in a first-class way.\r | |
| 811 | Consider the following <span class="monospaced">double</span> function, which takes a step, <span class="monospaced">s</span>, and\r | |
| 812 | produces a composite step that does <span class="monospaced">s</span> twice.</p></div>\r | |
| 813 | <div class="listingblock">\r | |
| 814 | <div class="content"><div class="highlight"><pre><span class="k">fun</span><span class="w"> </span><span class="n">double</span><span class="w"> </span><span class="n">s</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">u</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">Fold</span><span class="p">.</span><span class="n">fold</span><span class="w"> </span><span class="n">u</span><span class="w"> </span><span class="n">s</span><span class="w"> </span><span class="n">s</span><span class="w"></span>\r | |
| 815 | </pre></div></div></div>\r | |
| 816 | <div class="paragraph"><p>The definition of <span class="monospaced">double</span> is not type correct. The problem is that\r | |
| 817 | the type of a step depends on the number of remaining arguments but\r | |
| 818 | that the parameter <span class="monospaced">s</span> is not polymorphic, and so can not be used in\r | |
| 819 | two different positions.</p></div>\r | |
| 820 | <div class="paragraph"><p>Fortunately, we can define a function, <span class="monospaced">lift0</span>, that takes a monotyped\r | |
| 821 | step function and <em>lifts</em> it into a polymorphic step function. This\r | |
| 822 | is apparent in the type of <span class="monospaced">lift0</span>.</p></div>\r | |
| 823 | <div class="listingblock">\r | |
| 824 | <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">lift0</span><span class="p">:</span><span class="w"> </span><span class="p">(</span><span class="n">'a1</span><span class="p">,</span><span class="w"> </span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'a2</span><span class="p">)</span><span class="w"> </span><span class="n">step0</span><span class="w"></span>\r | |
| 825 | <span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="p">(</span><span class="n">'a1</span><span class="p">,</span><span class="w"> </span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">step0</span><span class="w"></span>\r | |
| 826 | <span class="k">fun</span><span class="w"> </span><span class="n">lift0</span><span class="w"> </span><span class="p">(</span><span class="n">s</span><span class="p">:</span><span class="w"> </span><span class="p">(</span><span class="n">'a1</span><span class="p">,</span><span class="w"> </span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'a2</span><span class="p">)</span><span class="w"> </span><span class="n">step0</span><span class="p">)</span><span class="w"></span>\r | |
| 827 | <span class="w"> </span><span class="p">(</span><span class="n">a</span><span class="p">:</span><span class="w"> </span><span class="n">'a1</span><span class="p">,</span><span class="w"> </span><span class="n">f</span><span class="p">:</span><span class="w"> </span><span class="n">'b</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'c</span><span class="p">):</span><span class="w"> </span><span class="p">(</span><span class="n">'a2</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
| 828 | <span class="w"> </span><span class="n">fold</span><span class="w"> </span><span class="p">(</span><span class="n">fold</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">id</span><span class="p">)</span><span class="w"> </span><span class="n">s</span><span class="w"> </span><span class="n">$</span><span class="p">,</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"></span>\r | |
| 829 | </pre></div></div></div>\r | |
| 830 | <div class="paragraph"><p>The following definition of <span class="monospaced">double</span> uses <span class="monospaced">lift0</span>, appropriately eta\r | |
| 831 | wrapped, to fix the problem.</p></div>\r | |
| 832 | <div class="listingblock">\r | |
| 833 | <div class="content"><div class="highlight"><pre><span class="k">fun</span><span class="w"> </span><span class="n">double</span><span class="w"> </span><span class="n">s</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
| 834 | <span class="w"> </span><span class="k">let</span><span class="w"></span>\r | |
| 835 | <span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">s</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">=></span><span class="w"> </span><span class="n">Fold</span><span class="p">.</span><span class="n">lift0</span><span class="w"> </span><span class="n">s</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 836 | <span class="w"> </span><span class="k">in</span><span class="w"></span>\r | |
| 837 | <span class="w"> </span><span class="k">fn</span><span class="w"> </span><span class="n">u</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">Fold</span><span class="p">.</span><span class="n">fold</span><span class="w"> </span><span class="n">u</span><span class="w"> </span><span class="n">s</span><span class="w"> </span><span class="n">s</span><span class="w"></span>\r | |
| 838 | <span class="w"> </span><span class="k">end</span><span class="w"></span>\r | |
| 839 | </pre></div></div></div>\r | |
| 840 | <div class="paragraph"><p>With that definition of <span class="monospaced">double</span> in place, we can use it as in the\r | |
| 841 | following example.</p></div>\r | |
| 842 | <div class="listingblock">\r | |
| 843 | <div class="content"><div class="highlight"><pre><span class="k">val</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">fn</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">Fold</span><span class="p">.</span><span class="n">fold</span><span class="w"> </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">=></span><span class="w"> </span><span class="p">())</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 844 | <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="k">fn</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">Fold</span><span class="p">.</span><span class="n">step0</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="p">())</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 845 | <span class="k">val</span><span class="w"> </span><span class="n">a2</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">=></span><span class="w"> </span><span class="n">double</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 846 | <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">f</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">a2</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">a2</span><span class="w"> </span><span class="n">$</span><span class="w"></span>\r | |
| 847 | </pre></div></div></div>\r | |
| 848 | <div class="paragraph"><p>Of course, we must eta wrap the call <span class="monospaced">double</span> in order to use its\r | |
| 849 | result, which is a step function, polymorphically.</p></div>\r | |
| 850 | </div>\r | |
| 851 | </div>\r | |
| 852 | <div class="sect1">\r | |
| 853 | <h2 id="_hiding_the_type_of_the_accumulator">Hiding the type of the accumulator</h2>\r | |
| 854 | <div class="sectionbody">\r | |
| 855 | <div class="paragraph"><p>For clarity and to avoid mistakes, it can be useful to hide the type\r | |
| 856 | of the accumulator in a fold. Reworking the simple variable-argument\r | |
| 857 | example to do this leads to the following.</p></div>\r | |
| 858 | <div class="listingblock">\r | |
| 859 | <div class="content"><div class="highlight"><pre><span class="k">structure</span><span class="w"> </span><span class="n">S</span><span class="p">:></span><span class="w"></span>\r | |
| 860 | <span class="w"> </span><span class="k">sig</span><span class="w"></span>\r | |
| 861 | <span class="w"> </span><span class="k">type</span><span class="w"> </span><span class="n">ac</span><span class="w"></span>\r | |
| 862 | <span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">f</span><span class="p">:</span><span class="w"> </span><span class="p">(</span><span class="n">ac</span><span class="p">,</span><span class="w"> </span><span class="n">ac</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">'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>\r | |
| 863 | <span class="w"> </span><span class="k">val</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">ac</span><span class="p">,</span><span class="w"> </span><span class="n">ac</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'c</span><span class="p">,</span><span class="w"> </span><span class="n">'d</span><span class="p">)</span><span class="w"> </span><span class="n">Fold</span><span class="p">.</span><span class="n">step0</span><span class="w"></span>\r | |
| 864 | <span class="w"> </span><span class="k">end</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
| 865 | <span class="w"> </span><span class="k">struct</span><span class="w"></span>\r | |
| 866 | <span class="w"> </span><span class="k">type</span><span class="w"> </span><span class="n">ac</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">unit</span><span class="w"></span>\r | |
| 867 | <span class="w"> </span><span class="k">val</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">fn</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">Fold</span><span class="p">.</span><span class="n">fold</span><span class="w"> </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">=></span><span class="w"> </span><span class="p">())</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 868 | <span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">s</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">=></span><span class="w"> </span><span class="n">Fold</span><span class="p">.</span><span class="n">step0</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="p">())</span><span class="w"> </span><span class="n">z</span><span class="w"></span>\r | |
| 869 | <span class="w"> </span><span class="k">end</span><span class="w"></span>\r | |
| 870 | </pre></div></div></div>\r | |
| 871 | <div class="paragraph"><p>The idea is to name the accumulator type and use opaque signature\r | |
| 872 | matching to make it abstract. This can prevent improper manipulation\r | |
| 873 | of the accumulator by client code and ensure invariants that the\r | |
| 874 | folder and stepper would like to maintain.</p></div>\r | |
| 875 | <div class="paragraph"><p>For a practical example of this technique, see <a href="ArrayLiteral">ArrayLiteral</a>.</p></div>\r | |
| 876 | </div>\r | |
| 877 | </div>\r | |
| 878 | <div class="sect1">\r | |
| 879 | <h2 id="_also_see">Also see</h2>\r | |
| 880 | <div class="sectionbody">\r | |
| 881 | <div class="paragraph"><p>Fold has a number of practical applications. Here are some of them.</p></div>\r | |
| 882 | <div class="ulist"><ul>\r | |
| 883 | <li>\r | |
| 884 | <p>\r | |
| 885 | <a href="ArrayLiteral">ArrayLiteral</a>\r | |
| 886 | </p>\r | |
| 887 | </li>\r | |
| 888 | <li>\r | |
| 889 | <p>\r | |
| 890 | <a href="Fold01N">Fold01N</a>\r | |
| 891 | </p>\r | |
| 892 | </li>\r | |
| 893 | <li>\r | |
| 894 | <p>\r | |
| 895 | <a href="FunctionalRecordUpdate">FunctionalRecordUpdate</a>\r | |
| 896 | </p>\r | |
| 897 | </li>\r | |
| 898 | <li>\r | |
| 899 | <p>\r | |
| 900 | <a href="NumericLiteral">NumericLiteral</a>\r | |
| 901 | </p>\r | |
| 902 | </li>\r | |
| 903 | <li>\r | |
| 904 | <p>\r | |
| 905 | <a href="OptionalArguments">OptionalArguments</a>\r | |
| 906 | </p>\r | |
| 907 | </li>\r | |
| 908 | <li>\r | |
| 909 | <p>\r | |
| 910 | <a href="Printf">Printf</a>\r | |
| 911 | </p>\r | |
| 912 | </li>\r | |
| 913 | <li>\r | |
| 914 | <p>\r | |
| 915 | <a href="VariableArityPolymorphism">VariableArityPolymorphism</a>\r | |
| 916 | </p>\r | |
| 917 | </li>\r | |
| 918 | </ul></div>\r | |
| 919 | <div class="paragraph"><p>There are a number of related techniques. Here are some of them.</p></div>\r | |
| 920 | <div class="ulist"><ul>\r | |
| 921 | <li>\r | |
| 922 | <p>\r | |
| 923 | <a href="StaticSum">StaticSum</a>\r | |
| 924 | </p>\r | |
| 925 | </li>\r | |
| 926 | <li>\r | |
| 927 | <p>\r | |
| 928 | <a href="TypeIndexedValues">TypeIndexedValues</a>\r | |
| 929 | </p>\r | |
| 930 | </li>\r | |
| 931 | </ul></div>\r | |
| 932 | </div>\r | |
| 933 | </div>\r | |
| 934 | </div>\r | |
| 935 | <div id="footnotes"><hr></div>\r | |
| 936 | <div id="footer">\r | |
| 937 | <div id="footer-text">\r | |
| 938 | </div>\r | |
| 939 | <div id="footer-badges">\r | |
| 940 | </div>\r | |
| 941 | </div>\r | |
| 942 | </body>\r | |
| 943 | </html>\r |