docs/sphinx_docs/_build/html/notebooks/Recursion_Combinators.html

   1
   2 <!DOCTYPE html>
   3
   4 <html>
   5   <head>
   6     <meta charset="utf-8" />
   7     <meta name="viewport" content="width=device-width, initial-scale=1.0" /><meta name="generator" content="Docutils 0.17.1: http://docutils.sourceforge.net/" />
   8
   9     <title>Recursion Combinators &#8212; Thun 0.4.1 documentation</title>
  10     <link rel="stylesheet" type="text/css" href="../_static/pygments.css" />
  11     <link rel="stylesheet" type="text/css" href="../_static/alabaster.css" />
  12     <script data-url_root="../" id="documentation_options" src="../_static/documentation_options.js"></script>
  13     <script src="../_static/jquery.js"></script>
  14     <script src="../_static/underscore.js"></script>
  15     <script src="../_static/doctools.js"></script>
  16     <link rel="index" title="Index" href="../genindex.html" />
  17     <link rel="search" title="Search" href="../search.html" />
  18     <link rel="next" title="Treating Trees I: Ordered Binary Trees" href="Ordered_Binary_Trees.html" />
  19     <link rel="prev" title="Replacing Functions in the Dictionary" href="Replacing.html" />
  20
  21   <link rel="stylesheet" href="../_static/custom.css" type="text/css" />
  22
  23
  24   <meta name="viewport" content="width=device-width, initial-scale=0.9, maximum-scale=0.9" />
  25
  26   </head><body>
  27
  28
  29     <div class="document">
  30       <div class="documentwrapper">
  31         <div class="bodywrapper">
  32
  33
  34           <div class="body" role="main">
  35
  36   <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="kn">from</span> <span class="nn">notebook_preamble</span> <span class="kn">import</span> <span class="n">D</span><span class="p">,</span> <span class="n">DefinitionWrapper</span><span class="p">,</span> <span class="n">J</span><span class="p">,</span> <span class="n">V</span><span class="p">,</span> <span class="n">define</span>
  37 </pre></div>
  38 </div>
  39 <section id="recursion-combinators">
  40 <h1>Recursion Combinators<a class="headerlink" href="#recursion-combinators" title="Permalink to this headline">¶</a></h1>
  41 <p>This article describes the <code class="docutils literal notranslate"><span class="pre">genrec</span></code> combinator, how to use it, and
  42 several generic specializations.</p>
  43 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>                      <span class="p">[</span><span class="k">if</span><span class="p">]</span> <span class="p">[</span><span class="n">then</span><span class="p">]</span> <span class="p">[</span><span class="n">rec1</span><span class="p">]</span> <span class="p">[</span><span class="n">rec2</span><span class="p">]</span> <span class="n">genrec</span>
  44 <span class="o">---------------------------------------------------------------------</span>
  45    <span class="p">[</span><span class="k">if</span><span class="p">]</span> <span class="p">[</span><span class="n">then</span><span class="p">]</span> <span class="p">[</span><span class="n">rec1</span> <span class="p">[[</span><span class="k">if</span><span class="p">]</span> <span class="p">[</span><span class="n">then</span><span class="p">]</span> <span class="p">[</span><span class="n">rec1</span><span class="p">]</span> <span class="p">[</span><span class="n">rec2</span><span class="p">]</span> <span class="n">genrec</span><span class="p">]</span> <span class="n">rec2</span><span class="p">]</span> <span class="n">ifte</span>
  46 </pre></div>
  47 </div>
  48 <p>From “Recursion Theory and Joy” (j05cmp.html) by Manfred von Thun:</p>
  49 <blockquote>
  50 <div><p>“The genrec combinator takes four program parameters in addition to
  51 whatever data parameters it needs. Fourth from the top is an if-part,
  52 followed by a then-part. If the if-part yields true, then the
  53 then-part is executed and the combinator terminates. The other two
  54 parameters are the rec1-part and the rec2-part. If the if-part yields
  55 false, the rec1-part is executed. Following that the four program
  56 parameters and the combinator are again pushed onto the stack bundled
  57 up in a quoted form. Then the rec2-part is executed, where it will
  58 find the bundled form. Typically it will then execute the bundled
  59 form, either with i or with app2, or some other combinator.”</p>
  60 </div></blockquote>
  61 <section id="designing-recursive-functions">
  62 <h2>Designing Recursive Functions<a class="headerlink" href="#designing-recursive-functions" title="Permalink to this headline">¶</a></h2>
  63 <p>The way to design one of these is to fix your base case and test and
  64 then treat <code class="docutils literal notranslate"><span class="pre">R1</span></code> and <code class="docutils literal notranslate"><span class="pre">R2</span></code> as an else-part “sandwiching” a quotation
  65 of the whole function.</p>
  66 <p>For example, given a (general recursive) function <code class="docutils literal notranslate"><span class="pre">F</span></code>:</p>
  67 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">F</span> <span class="o">==</span> <span class="p">[</span><span class="n">I</span><span class="p">]</span> <span class="p">[</span><span class="n">T</span><span class="p">]</span> <span class="p">[</span><span class="n">R1</span><span class="p">]</span>   <span class="p">[</span><span class="n">R2</span><span class="p">]</span> <span class="n">genrec</span>
  68   <span class="o">==</span> <span class="p">[</span><span class="n">I</span><span class="p">]</span> <span class="p">[</span><span class="n">T</span><span class="p">]</span> <span class="p">[</span><span class="n">R1</span> <span class="p">[</span><span class="n">F</span><span class="p">]</span> <span class="n">R2</span><span class="p">]</span> <span class="n">ifte</span>
  69 </pre></div>
  70 </div>
  71 <p>If the <code class="docutils literal notranslate"><span class="pre">[I]</span></code> predicate is false you must derive <code class="docutils literal notranslate"><span class="pre">R1</span></code> and <code class="docutils literal notranslate"><span class="pre">R2</span></code>
  72 from:</p>
  73 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="o">...</span> <span class="n">R1</span> <span class="p">[</span><span class="n">F</span><span class="p">]</span> <span class="n">R2</span>
  74 </pre></div>
  75 </div>
  76 <p>Set the stack arguments in front and figure out what <code class="docutils literal notranslate"><span class="pre">R1</span></code> and <code class="docutils literal notranslate"><span class="pre">R2</span></code>
  77 have to do to apply the quoted <code class="docutils literal notranslate"><span class="pre">[F]</span></code> in the proper way.</p>
  78 </section>
  79 <section id="primitive-recursive-functions">
  80 <h2>Primitive Recursive Functions<a class="headerlink" href="#primitive-recursive-functions" title="Permalink to this headline">¶</a></h2>
  81 <p>Primitive recursive functions are those where <code class="docutils literal notranslate"><span class="pre">R2</span> <span class="pre">==</span> <span class="pre">i</span></code>.</p>
  82 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">P</span> <span class="o">==</span> <span class="p">[</span><span class="n">I</span><span class="p">]</span> <span class="p">[</span><span class="n">T</span><span class="p">]</span> <span class="p">[</span><span class="n">R</span><span class="p">]</span> <span class="n">primrec</span>
  83   <span class="o">==</span> <span class="p">[</span><span class="n">I</span><span class="p">]</span> <span class="p">[</span><span class="n">T</span><span class="p">]</span> <span class="p">[</span><span class="n">R</span> <span class="p">[</span><span class="n">P</span><span class="p">]</span> <span class="n">i</span><span class="p">]</span> <span class="n">ifte</span>
  84   <span class="o">==</span> <span class="p">[</span><span class="n">I</span><span class="p">]</span> <span class="p">[</span><span class="n">T</span><span class="p">]</span> <span class="p">[</span><span class="n">R</span> <span class="n">P</span><span class="p">]</span> <span class="n">ifte</span>
  85 </pre></div>
  86 </div>
  87 </section>
  88 <section id="hylomorphism">
  89 <h2><a class="reference external" href="https://en.wikipedia.org/wiki/Hylomorphism_%28computer_science%29">Hylomorphism</a><a class="headerlink" href="#hylomorphism" title="Permalink to this headline">¶</a></h2>
  90 <p>A
  91 <a class="reference external" href="https://en.wikipedia.org/wiki/Hylomorphism_%28computer_science%29">hylomorphism</a>
  92 is a recursive function <code class="docutils literal notranslate"><span class="pre">H</span> <span class="pre">::</span> <span class="pre">A</span> <span class="pre">-&gt;</span> <span class="pre">C</span></code> that converts a value of type
  93 <code class="docutils literal notranslate"><span class="pre">A</span></code> into a value of type <code class="docutils literal notranslate"><span class="pre">C</span></code> by means of:</p>
  94 <ul class="simple">
  95 <li><p>A generator <code class="docutils literal notranslate"><span class="pre">G</span> <span class="pre">::</span> <span class="pre">A</span> <span class="pre">-&gt;</span> <span class="pre">(B,</span> <span class="pre">A)</span></code></p></li>
  96 <li><p>A combiner <code class="docutils literal notranslate"><span class="pre">F</span> <span class="pre">::</span> <span class="pre">(B,</span> <span class="pre">C)</span> <span class="pre">-&gt;</span> <span class="pre">C</span></code></p></li>
  97 <li><p>A predicate <code class="docutils literal notranslate"><span class="pre">P</span> <span class="pre">::</span> <span class="pre">A</span> <span class="pre">-&gt;</span> <span class="pre">Bool</span></code> to detect the base case</p></li>
  98 <li><p>A base case value <code class="docutils literal notranslate"><span class="pre">c</span> <span class="pre">::</span> <span class="pre">C</span></code></p></li>
  99 <li><p>Recursive calls (zero or more); it has a “call stack in the form of a
 100 cons list”.</p></li>
 101 </ul>
 102 <p>It may be helpful to see this function implemented in imperative Python
 103 code.</p>
 104 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">hylomorphism</span><span class="p">(</span><span class="n">c</span><span class="p">,</span> <span class="n">F</span><span class="p">,</span> <span class="n">P</span><span class="p">,</span> <span class="n">G</span><span class="p">):</span>
 105     <span class="sd">&#39;&#39;&#39;Return a hylomorphism function H.&#39;&#39;&#39;</span>
 106
 107     <span class="k">def</span> <span class="nf">H</span><span class="p">(</span><span class="n">a</span><span class="p">):</span>
 108         <span class="k">if</span> <span class="n">P</span><span class="p">(</span><span class="n">a</span><span class="p">):</span>
 109             <span class="n">result</span> <span class="o">=</span> <span class="n">c</span>
 110         <span class="k">else</span><span class="p">:</span>
 111             <span class="n">b</span><span class="p">,</span> <span class="n">aa</span> <span class="o">=</span> <span class="n">G</span><span class="p">(</span><span class="n">a</span><span class="p">)</span>
 112             <span class="n">result</span> <span class="o">=</span> <span class="n">F</span><span class="p">(</span><span class="n">b</span><span class="p">,</span> <span class="n">H</span><span class="p">(</span><span class="n">aa</span><span class="p">))</span>  <span class="c1"># b is stored in the stack frame during recursive call to H().</span>
 113         <span class="k">return</span> <span class="n">result</span>
 114
 115     <span class="k">return</span> <span class="n">H</span>
 116 </pre></div>
 117 </div>
 118 <p>Cf. <a class="reference external" href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.125">“Bananas, Lenses, &amp; Barbed
 119 Wire”</a></p>
 120 <p>Note that during evaluation of <code class="docutils literal notranslate"><span class="pre">H()</span></code> the intermediate <code class="docutils literal notranslate"><span class="pre">b</span></code> values are
 121 stored in the Python call stack. This is what is meant by “call stack in
 122 the form of a cons list”.</p>
 123 </section>
 124 <section id="hylomorphism-in-joy">
 125 <h2>Hylomorphism in Joy<a class="headerlink" href="#hylomorphism-in-joy" title="Permalink to this headline">¶</a></h2>
 126 <p>We can define a combinator <code class="docutils literal notranslate"><span class="pre">hylomorphism</span></code> that will make a
 127 hylomorphism combinator <code class="docutils literal notranslate"><span class="pre">H</span></code> from constituent parts.</p>
 128 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">H</span> <span class="o">==</span> <span class="p">[</span><span class="n">P</span><span class="p">]</span> <span class="n">c</span> <span class="p">[</span><span class="n">G</span><span class="p">]</span> <span class="p">[</span><span class="n">F</span><span class="p">]</span> <span class="n">hylomorphism</span>
 129 </pre></div>
 130 </div>
 131 <p>The function <code class="docutils literal notranslate"><span class="pre">H</span></code> is recursive, so we start with <code class="docutils literal notranslate"><span class="pre">ifte</span></code> and set the
 132 else-part to some function <code class="docutils literal notranslate"><span class="pre">J</span></code> that will contain a quoted copy of
 133 <code class="docutils literal notranslate"><span class="pre">H</span></code>. (The then-part just discards the leftover <code class="docutils literal notranslate"><span class="pre">a</span></code> and replaces it
 134 with the base case value <code class="docutils literal notranslate"><span class="pre">c</span></code>.)</p>
 135 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">H</span> <span class="o">==</span> <span class="p">[</span><span class="n">P</span><span class="p">]</span> <span class="p">[</span><span class="n">pop</span> <span class="n">c</span><span class="p">]</span> <span class="p">[</span><span class="n">J</span><span class="p">]</span> <span class="n">ifte</span>
 136 </pre></div>
 137 </div>
 138 <p>The else-part <code class="docutils literal notranslate"><span class="pre">J</span></code> gets just the argument <code class="docutils literal notranslate"><span class="pre">a</span></code> on the stack.</p>
 139 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">a</span> <span class="n">J</span>
 140 <span class="n">a</span> <span class="n">G</span>              <span class="n">The</span> <span class="n">first</span> <span class="n">thing</span> <span class="n">to</span> <span class="n">do</span> <span class="ow">is</span> <span class="n">use</span> <span class="n">the</span> <span class="n">generator</span> <span class="n">G</span>
 141 <span class="n">aa</span> <span class="n">b</span>             <span class="n">which</span> <span class="n">produces</span> <span class="n">b</span> <span class="ow">and</span> <span class="n">a</span> <span class="n">new</span> <span class="n">aa</span>
 142 <span class="n">aa</span> <span class="n">b</span> <span class="p">[</span><span class="n">H</span><span class="p">]</span> <span class="n">dip</span>     <span class="n">we</span> <span class="n">recur</span> <span class="k">with</span> <span class="n">H</span> <span class="n">on</span> <span class="n">the</span> <span class="n">new</span> <span class="n">aa</span>
 143 <span class="n">aa</span> <span class="n">H</span> <span class="n">b</span> <span class="n">F</span>         <span class="ow">and</span> <span class="n">run</span> <span class="n">F</span> <span class="n">on</span> <span class="n">the</span> <span class="n">result</span><span class="o">.</span>
 144 </pre></div>
 145 </div>
 146 <p>This gives us a definition for <code class="docutils literal notranslate"><span class="pre">J</span></code>.</p>
 147 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">J</span> <span class="o">==</span> <span class="n">G</span> <span class="p">[</span><span class="n">H</span><span class="p">]</span> <span class="n">dip</span> <span class="n">F</span>
 148 </pre></div>
 149 </div>
 150 <p>Plug it in and convert to genrec.</p>
 151 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">H</span> <span class="o">==</span> <span class="p">[</span><span class="n">P</span><span class="p">]</span> <span class="p">[</span><span class="n">pop</span> <span class="n">c</span><span class="p">]</span> <span class="p">[</span><span class="n">G</span> <span class="p">[</span><span class="n">H</span><span class="p">]</span> <span class="n">dip</span> <span class="n">F</span><span class="p">]</span> <span class="n">ifte</span>
 152 <span class="n">H</span> <span class="o">==</span> <span class="p">[</span><span class="n">P</span><span class="p">]</span> <span class="p">[</span><span class="n">pop</span> <span class="n">c</span><span class="p">]</span> <span class="p">[</span><span class="n">G</span><span class="p">]</span>   <span class="p">[</span><span class="n">dip</span> <span class="n">F</span><span class="p">]</span> <span class="n">genrec</span>
 153 </pre></div>
 154 </div>
 155 <p>This is the form of a hylomorphism in Joy, which nicely illustrates that
 156 it is a simple specialization of the general recursion combinator.</p>
 157 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">H</span> <span class="o">==</span> <span class="p">[</span><span class="n">P</span><span class="p">]</span> <span class="n">c</span> <span class="p">[</span><span class="n">G</span><span class="p">]</span> <span class="p">[</span><span class="n">F</span><span class="p">]</span> <span class="n">hylomorphism</span> <span class="o">==</span> <span class="p">[</span><span class="n">P</span><span class="p">]</span> <span class="p">[</span><span class="n">pop</span> <span class="n">c</span><span class="p">]</span> <span class="p">[</span><span class="n">G</span><span class="p">]</span> <span class="p">[</span><span class="n">dip</span> <span class="n">F</span><span class="p">]</span> <span class="n">genrec</span>
 158 </pre></div>
 159 </div>
 160 </section>
 161 <section id="derivation-of-hylomorphism-combinator">
 162 <h2>Derivation of <code class="docutils literal notranslate"><span class="pre">hylomorphism</span></code> combinator<a class="headerlink" href="#derivation-of-hylomorphism-combinator" title="Permalink to this headline">¶</a></h2>
 163 <p>Now we just need to derive a definition that builds the <code class="docutils literal notranslate"><span class="pre">genrec</span></code>
 164 arguments out of the pieces given to the <code class="docutils literal notranslate"><span class="pre">hylomorphism</span></code> combinator.</p>
 165 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>   <span class="p">[</span><span class="n">P</span><span class="p">]</span>      <span class="n">c</span>  <span class="p">[</span><span class="n">G</span><span class="p">]</span>     <span class="p">[</span><span class="n">F</span><span class="p">]</span> <span class="n">hylomorphism</span>
 166 <span class="o">------------------------------------------</span>
 167    <span class="p">[</span><span class="n">P</span><span class="p">]</span> <span class="p">[</span><span class="n">pop</span> <span class="n">c</span><span class="p">]</span> <span class="p">[</span><span class="n">G</span><span class="p">]</span> <span class="p">[</span><span class="n">dip</span> <span class="n">F</span><span class="p">]</span> <span class="n">genrec</span>
 168 </pre></div>
 169 </div>
 170 <p>Working in reverse:</p>
 171 <ul class="simple">
 172 <li><p>Use <code class="docutils literal notranslate"><span class="pre">swoncat</span></code> twice to decouple <code class="docutils literal notranslate"><span class="pre">[c]</span></code> and <code class="docutils literal notranslate"><span class="pre">[F]</span></code>.</p></li>
 173 <li><p>Use <code class="docutils literal notranslate"><span class="pre">unit</span></code> to dequote <code class="docutils literal notranslate"><span class="pre">c</span></code>.</p></li>
 174 <li><p>Use <code class="docutils literal notranslate"><span class="pre">dipd</span></code> to untangle <code class="docutils literal notranslate"><span class="pre">[unit</span> <span class="pre">[pop]</span> <span class="pre">swoncat]</span></code> from the givens.</p></li>
 175 </ul>
 176 <p>So:</p>
 177 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">H</span> <span class="o">==</span> <span class="p">[</span><span class="n">P</span><span class="p">]</span> <span class="p">[</span><span class="n">pop</span> <span class="n">c</span><span class="p">]</span>              <span class="p">[</span><span class="n">G</span><span class="p">]</span>                  <span class="p">[</span><span class="n">dip</span> <span class="n">F</span><span class="p">]</span> <span class="n">genrec</span>
 178      <span class="p">[</span><span class="n">P</span><span class="p">]</span> <span class="p">[</span><span class="n">c</span><span class="p">]</span>    <span class="p">[</span><span class="n">pop</span><span class="p">]</span> <span class="n">swoncat</span> <span class="p">[</span><span class="n">G</span><span class="p">]</span>        <span class="p">[</span><span class="n">F</span><span class="p">]</span> <span class="p">[</span><span class="n">dip</span><span class="p">]</span> <span class="n">swoncat</span> <span class="n">genrec</span>
 179      <span class="p">[</span><span class="n">P</span><span class="p">]</span> <span class="n">c</span> <span class="n">unit</span> <span class="p">[</span><span class="n">pop</span><span class="p">]</span> <span class="n">swoncat</span> <span class="p">[</span><span class="n">G</span><span class="p">]</span>        <span class="p">[</span><span class="n">F</span><span class="p">]</span> <span class="p">[</span><span class="n">dip</span><span class="p">]</span> <span class="n">swoncat</span> <span class="n">genrec</span>
 180      <span class="p">[</span><span class="n">P</span><span class="p">]</span> <span class="n">c</span> <span class="p">[</span><span class="n">G</span><span class="p">]</span> <span class="p">[</span><span class="n">F</span><span class="p">]</span> <span class="p">[</span><span class="n">unit</span> <span class="p">[</span><span class="n">pop</span><span class="p">]</span> <span class="n">swoncat</span><span class="p">]</span> <span class="n">dipd</span> <span class="p">[</span><span class="n">dip</span><span class="p">]</span> <span class="n">swoncat</span> <span class="n">genrec</span>
 181 </pre></div>
 182 </div>
 183 <p>At this point all of the arguments (givens) to the hylomorphism are to
 184 the left so we have a definition for <code class="docutils literal notranslate"><span class="pre">hylomorphism</span></code>:</p>
 185 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">hylomorphism</span> <span class="o">==</span> <span class="p">[</span><span class="n">unit</span> <span class="p">[</span><span class="n">pop</span><span class="p">]</span> <span class="n">swoncat</span><span class="p">]</span> <span class="n">dipd</span> <span class="p">[</span><span class="n">dip</span><span class="p">]</span> <span class="n">swoncat</span> <span class="n">genrec</span>
 186 </pre></div>
 187 </div>
 188 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">&#39;hylomorphism == [unit [pop] swoncat] dipd [dip] swoncat genrec&#39;</span><span class="p">)</span>
 189 </pre></div>
 190 </div>
 191 <section id="example-finding-triangular-numbers">
 192 <h3>Example: Finding <a class="reference external" href="https://en.wikipedia.org/wiki/Triangular_number">Triangular Numbers</a><a class="headerlink" href="#example-finding-triangular-numbers" title="Permalink to this headline">¶</a></h3>
 193 <p>Let’s write a function that, given a positive integer, returns the sum
 194 of all positive integers less than that one. (In this case the types
 195 <code class="docutils literal notranslate"><span class="pre">A</span></code>, <code class="docutils literal notranslate"><span class="pre">B</span></code> and <code class="docutils literal notranslate"><span class="pre">C</span></code> are all <code class="docutils literal notranslate"><span class="pre">int</span></code>.)</p>
 196 <p>To sum a range of integers from 0 to <em>n</em> - 1:</p>
 197 <ul class="simple">
 198 <li><p><code class="docutils literal notranslate"><span class="pre">[P]</span></code> is <code class="docutils literal notranslate"><span class="pre">[1</span> <span class="pre">&lt;=]</span></code></p></li>
 199 <li><p><code class="docutils literal notranslate"><span class="pre">c</span></code> is <code class="docutils literal notranslate"><span class="pre">0</span></code></p></li>
 200 <li><p><code class="docutils literal notranslate"><span class="pre">[G]</span></code> is <code class="docutils literal notranslate"><span class="pre">[--</span> <span class="pre">dup]</span></code></p></li>
 201 <li><p><code class="docutils literal notranslate"><span class="pre">[F]</span></code> is <code class="docutils literal notranslate"><span class="pre">[+]</span></code></p></li>
 202 </ul>
 203 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">&#39;triangular_number == [1 &lt;=] 0 [-- dup] [+] hylomorphism&#39;</span><span class="p">)</span>
 204 </pre></div>
 205 </div>
 206 <p>Let’s try it:</p>
 207 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;5 triangular_number&#39;</span><span class="p">)</span>
 208 </pre></div>
 209 </div>
 210 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">10</span>
 211 </pre></div>
 212 </div>
 213 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;[0 1 2 3 4 5 6] [triangular_number] map&#39;</span><span class="p">)</span>
 214 </pre></div>
 215 </div>
 216 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="mi">0</span> <span class="mi">0</span> <span class="mi">1</span> <span class="mi">3</span> <span class="mi">6</span> <span class="mi">10</span> <span class="mi">15</span><span class="p">]</span>
 217 </pre></div>
 218 </div>
 219 </section>
 220 </section>
 221 <section id="four-specializations">
 222 <h2>Four Specializations<a class="headerlink" href="#four-specializations" title="Permalink to this headline">¶</a></h2>
 223 <p>There are at least four kinds of recursive combinator, depending on two
 224 choices. The first choice is whether the combiner function <code class="docutils literal notranslate"><span class="pre">F</span></code> should
 225 be evaluated during the recursion or pushed into the pending expression
 226 to be “collapsed” at the end. The second choice is whether the combiner
 227 needs to operate on the current value of the datastructure or the
 228 generator’s output, in other words, whether <code class="docutils literal notranslate"><span class="pre">F</span></code> or <code class="docutils literal notranslate"><span class="pre">G</span></code> should run
 229 first in the recursive branch.</p>
 230 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">H1</span> <span class="o">==</span>        <span class="p">[</span><span class="n">P</span><span class="p">]</span> <span class="p">[</span><span class="n">pop</span> <span class="n">c</span><span class="p">]</span> <span class="p">[</span><span class="n">G</span>             <span class="p">]</span> <span class="p">[</span><span class="n">dip</span> <span class="n">F</span><span class="p">]</span> <span class="n">genrec</span>
 231 <span class="n">H2</span> <span class="o">==</span> <span class="n">c</span> <span class="n">swap</span> <span class="p">[</span><span class="n">P</span><span class="p">]</span> <span class="p">[</span><span class="n">pop</span><span class="p">]</span>   <span class="p">[</span><span class="n">G</span> <span class="p">[</span><span class="n">F</span><span class="p">]</span>    <span class="n">dip</span>  <span class="p">]</span> <span class="p">[</span><span class="n">i</span><span class="p">]</span>     <span class="n">genrec</span>
 232 <span class="n">H3</span> <span class="o">==</span>        <span class="p">[</span><span class="n">P</span><span class="p">]</span> <span class="p">[</span><span class="n">pop</span> <span class="n">c</span><span class="p">]</span> <span class="p">[</span>  <span class="p">[</span><span class="n">G</span><span class="p">]</span> <span class="n">dupdip</span>  <span class="p">]</span> <span class="p">[</span><span class="n">dip</span> <span class="n">F</span><span class="p">]</span> <span class="n">genrec</span>
 233 <span class="n">H4</span> <span class="o">==</span> <span class="n">c</span> <span class="n">swap</span> <span class="p">[</span><span class="n">P</span><span class="p">]</span> <span class="p">[</span><span class="n">pop</span><span class="p">]</span>   <span class="p">[</span>  <span class="p">[</span><span class="n">F</span><span class="p">]</span> <span class="n">dupdip</span> <span class="n">G</span><span class="p">]</span> <span class="p">[</span><span class="n">i</span><span class="p">]</span>     <span class="n">genrec</span>
 234 </pre></div>
 235 </div>
 236 <p>The working of the generator function <code class="docutils literal notranslate"><span class="pre">G</span></code> differs slightly for each.
 237 Consider the recursive branches:</p>
 238 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>... a G [H1] dip F                w/ a G == a′ b
 239
 240 ... c a G [F] dip H2                 a G == b  a′
 241
 242 ... a [G] dupdip [H3] dip F          a G == a′
 243
 244 ... c a [F] dupdip G H4              a G == a′
 245 </pre></div>
 246 </div>
 247 <p>The following four sections illustrate how these work, omitting the
 248 predicate evaluation.</p>
 249 <section id="h1">
 250 <h3><code class="docutils literal notranslate"><span class="pre">H1</span></code><a class="headerlink" href="#h1" title="Permalink to this headline">¶</a></h3>
 251 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">H1</span> <span class="o">==</span> <span class="p">[</span><span class="n">P</span><span class="p">]</span> <span class="p">[</span><span class="n">pop</span> <span class="n">c</span><span class="p">]</span> <span class="p">[</span><span class="n">G</span><span class="p">]</span> <span class="p">[</span><span class="n">dip</span> <span class="n">F</span><span class="p">]</span> <span class="n">genrec</span>
 252 </pre></div>
 253 </div>
 254 <p>Iterate n times.</p>
 255 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>... a  G [H1] dip F
 256 ... a′ b [H1] dip F
 257 ... a′ H1 b F
 258 ... a′ G [H1] dip F b F
 259 ... a″ b′ [H1] dip F b F
 260 ... a″ H1 b′ F b F
 261 ... a″ G [H1] dip F b′ F b F
 262 ... a‴ b″ [H1] dip F b′ F b F
 263 ... a‴ H1 b″ F b′ F b F
 264 ... a‴ pop c b″ F b′ F b F
 265 ... c b″ F b′ F b F
 266 ... d      b′ F b F
 267 ... d′          b F
 268 ... d″
 269 </pre></div>
 270 </div>
 271 <p>This form builds up a pending expression (continuation) that contains
 272 the intermediate results along with the pending combiner functions. When
 273 the base case is reached the last term is replaced by the identity value
 274 <code class="docutils literal notranslate"><span class="pre">c</span></code> and the continuation “collapses” into the final result using the
 275 combiner <code class="docutils literal notranslate"><span class="pre">F</span></code>.</p>
 276 </section>
 277 <section id="h2">
 278 <h3><code class="docutils literal notranslate"><span class="pre">H2</span></code><a class="headerlink" href="#h2" title="Permalink to this headline">¶</a></h3>
 279 <p>When you can start with the identity value <code class="docutils literal notranslate"><span class="pre">c</span></code> on the stack and the
 280 combiner <code class="docutils literal notranslate"><span class="pre">F</span></code> can operate as you go using the intermediate results
 281 immediately rather than queuing them up, use this form. An important
 282 difference is that the generator function must return its results in the
 283 reverse order.</p>
 284 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>H2 == c swap [P] [pop] [G [F] dip] primrec
 285
 286 ... c a G  [F] dip H2
 287 ... c b a′ [F] dip H2
 288 ... c b F a′ H2
 289 ... d     a′ H2
 290 ... d a′ G  [F] dip H2
 291 ... d b′ a″ [F] dip H2
 292 ... d b′ F a″ H2
 293 ... d′     a″ H2
 294 ... d′ a″ G  [F] dip H2
 295 ... d′ b″ a‴ [F] dip H2
 296 ... d′ b″ F a‴ H2
 297 ... d″      a‴ H2
 298 ... d″ a‴ pop
 299 ... d″
 300 </pre></div>
 301 </div>
 302 </section>
 303 <section id="h3">
 304 <h3><code class="docutils literal notranslate"><span class="pre">H3</span></code><a class="headerlink" href="#h3" title="Permalink to this headline">¶</a></h3>
 305 <p>If you examine the traces above you’ll see that the combiner <code class="docutils literal notranslate"><span class="pre">F</span></code> only
 306 gets to operate on the results of <code class="docutils literal notranslate"><span class="pre">G</span></code>, it never “sees” the first value
 307 <code class="docutils literal notranslate"><span class="pre">a</span></code>. If the combiner and the generator both need to work on the
 308 current value then <code class="docutils literal notranslate"><span class="pre">dup</span></code> must be used, and the generator must produce
 309 one item instead of two (the b is instead the duplicate of a.)</p>
 310 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>H3 == [P] [pop c] [[G] dupdip] [dip F] genrec
 311
 312 ... a [G] dupdip [H3] dip F
 313 ... a  G  a      [H3] dip F
 314 ... a′    a      [H3] dip F
 315 ... a′ H3 a               F
 316 ... a′ [G] dupdip [H3] dip F a F
 317 ... a′  G  a′     [H3] dip F a F
 318 ... a″     a′     [H3] dip F a F
 319 ... a″ H3  a′              F a F
 320 ... a″ [G] dupdip [H3] dip F a′ F a F
 321 ... a″  G    a″   [H3] dip F a′ F a F
 322 ... a‴       a″   [H3] dip F a′ F a F
 323 ... a‴ H3    a″            F a′ F a F
 324 ... a‴ pop c a″ F a′ F a F
 325 ...        c a″ F a′ F a F
 326 ...        d      a′ F a F
 327 ...        d′          a F
 328 ...        d″
 329 </pre></div>
 330 </div>
 331 </section>
 332 <section id="h4">
 333 <h3><code class="docutils literal notranslate"><span class="pre">H4</span></code><a class="headerlink" href="#h4" title="Permalink to this headline">¶</a></h3>
 334 <p>And, last but not least, if you can combine as you go, starting with
 335 <code class="docutils literal notranslate"><span class="pre">c</span></code>, and the combiner <code class="docutils literal notranslate"><span class="pre">F</span></code> needs to work on the current item, this is
 336 the form:</p>
 337 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>H4 == c swap [P] [pop] [[F] dupdip G] primrec
 338
 339 ... c  a  [F] dupdip G H4
 340 ... c  a   F  a      G H4
 341 ... d         a      G H4
 342 ... d  a′              H4
 343 ... d  a′ [F] dupdip G H4
 344 ... d  a′  F  a′     G H4
 345 ... d′        a′     G H4
 346 ... d′ a″              H4
 347 ... d′ a″ [F] dupdip G H4
 348 ... d′ a″  F  a″     G H4
 349 ... d″        a″     G H4
 350 ... d″ a‴              H4
 351 ... d″ a‴ pop
 352 ... d″
 353 </pre></div>
 354 </div>
 355 </section>
 356 </section>
 357 <section id="anamorphism">
 358 <h2>Anamorphism<a class="headerlink" href="#anamorphism" title="Permalink to this headline">¶</a></h2>
 359 <p>An anamorphism can be defined as a hylomorphism that uses <code class="docutils literal notranslate"><span class="pre">[]</span></code> for
 360 <code class="docutils literal notranslate"><span class="pre">c</span></code> and <code class="docutils literal notranslate"><span class="pre">swons</span></code> for <code class="docutils literal notranslate"><span class="pre">F</span></code>. An anamorphic function builds a list of
 361 values.</p>
 362 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">A</span> <span class="o">==</span> <span class="p">[</span><span class="n">P</span><span class="p">]</span> <span class="p">[]</span> <span class="p">[</span><span class="n">G</span><span class="p">]</span> <span class="p">[</span><span class="n">swons</span><span class="p">]</span> <span class="n">hylomorphism</span>
 363 </pre></div>
 364 </div>
 365 <section id="range-et-al-an-example-of-an-anamorphism-is-the-range-function-which-generates-the-list-of-integers-from-0-to-n-1-given-n">
 366 <h3><code class="docutils literal notranslate"><span class="pre">range</span></code> et. al. An example of an anamorphism is the <code class="docutils literal notranslate"><span class="pre">range</span></code> function which generates the list of integers from 0 to <em>n</em> - 1 given <em>n</em>.<a class="headerlink" href="#range-et-al-an-example-of-an-anamorphism-is-the-range-function-which-generates-the-list-of-integers-from-0-to-n-1-given-n" title="Permalink to this headline">¶</a></h3>
 367 <p>Each of the above variations can be used to make four slightly different
 368 <code class="docutils literal notranslate"><span class="pre">range</span></code> functions.</p>
 369 <section id="range-with-h1">
 370 <h4><code class="docutils literal notranslate"><span class="pre">range</span></code> with <code class="docutils literal notranslate"><span class="pre">H1</span></code><a class="headerlink" href="#range-with-h1" title="Permalink to this headline">¶</a></h4>
 371 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">H1</span> <span class="o">==</span> <span class="p">[</span><span class="n">P</span><span class="p">]</span>    <span class="p">[</span><span class="n">pop</span> <span class="n">c</span><span class="p">]</span>  <span class="p">[</span><span class="n">G</span><span class="p">]</span>      <span class="p">[</span><span class="n">dip</span> <span class="n">F</span><span class="p">]</span>     <span class="n">genrec</span>
 372    <span class="o">==</span> <span class="p">[</span><span class="mi">0</span> <span class="o">&lt;=</span><span class="p">]</span> <span class="p">[</span><span class="n">pop</span> <span class="p">[]]</span> <span class="p">[</span><span class="o">--</span> <span class="n">dup</span><span class="p">]</span> <span class="p">[</span><span class="n">dip</span> <span class="n">swons</span><span class="p">]</span> <span class="n">genrec</span>
 373 </pre></div>
 374 </div>
 375 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">&#39;range == [0 &lt;=] [] [-- dup] [swons] hylomorphism&#39;</span><span class="p">)</span>
 376 </pre></div>
 377 </div>
 378 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;5 range&#39;</span><span class="p">)</span>
 379 </pre></div>
 380 </div>
 381 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="mi">4</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">0</span><span class="p">]</span>
 382 </pre></div>
 383 </div>
 384 </section>
 385 <section id="range-with-h2">
 386 <h4><code class="docutils literal notranslate"><span class="pre">range</span></code> with <code class="docutils literal notranslate"><span class="pre">H2</span></code><a class="headerlink" href="#range-with-h2" title="Permalink to this headline">¶</a></h4>
 387 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">H2</span> <span class="o">==</span> <span class="n">c</span>  <span class="n">swap</span> <span class="p">[</span><span class="n">P</span><span class="p">]</span>    <span class="p">[</span><span class="n">pop</span><span class="p">]</span> <span class="p">[</span><span class="n">G</span>      <span class="p">[</span><span class="n">F</span><span class="p">]</span>     <span class="n">dip</span><span class="p">]</span> <span class="n">primrec</span>
 388    <span class="o">==</span> <span class="p">[]</span> <span class="n">swap</span> <span class="p">[</span><span class="mi">0</span> <span class="o">&lt;=</span><span class="p">]</span> <span class="p">[</span><span class="n">pop</span><span class="p">]</span> <span class="p">[</span><span class="o">--</span> <span class="n">dup</span> <span class="p">[</span><span class="n">swons</span><span class="p">]</span> <span class="n">dip</span><span class="p">]</span> <span class="n">primrec</span>
 389 </pre></div>
 390 </div>
 391 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">&#39;range_reverse == [] swap [0 &lt;=] [pop] [-- dup [swons] dip] primrec&#39;</span><span class="p">)</span>
 392 </pre></div>
 393 </div>
 394 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;5 range_reverse&#39;</span><span class="p">)</span>
 395 </pre></div>
 396 </div>
 397 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="mi">0</span> <span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">4</span><span class="p">]</span>
 398 </pre></div>
 399 </div>
 400 </section>
 401 <section id="range-with-h3">
 402 <h4><code class="docutils literal notranslate"><span class="pre">range</span></code> with <code class="docutils literal notranslate"><span class="pre">H3</span></code><a class="headerlink" href="#range-with-h3" title="Permalink to this headline">¶</a></h4>
 403 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">H3</span> <span class="o">==</span> <span class="p">[</span><span class="n">P</span><span class="p">]</span>    <span class="p">[</span><span class="n">pop</span> <span class="n">c</span><span class="p">]</span>  <span class="p">[[</span><span class="n">G</span><span class="p">]</span>  <span class="n">dupdip</span><span class="p">]</span> <span class="p">[</span><span class="n">dip</span> <span class="n">F</span><span class="p">]</span>     <span class="n">genrec</span>
 404    <span class="o">==</span> <span class="p">[</span><span class="mi">0</span> <span class="o">&lt;=</span><span class="p">]</span> <span class="p">[</span><span class="n">pop</span> <span class="p">[]]</span> <span class="p">[[</span><span class="o">--</span><span class="p">]</span> <span class="n">dupdip</span><span class="p">]</span> <span class="p">[</span><span class="n">dip</span> <span class="n">swons</span><span class="p">]</span> <span class="n">genrec</span>
 405 </pre></div>
 406 </div>
 407 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">&#39;ranger == [0 &lt;=] [pop []] [[--] dupdip] [dip swons] genrec&#39;</span><span class="p">)</span>
 408 </pre></div>
 409 </div>
 410 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;5 ranger&#39;</span><span class="p">)</span>
 411 </pre></div>
 412 </div>
 413 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="mi">5</span> <span class="mi">4</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span><span class="p">]</span>
 414 </pre></div>
 415 </div>
 416 </section>
 417 <section id="range-with-h4">
 418 <h4><code class="docutils literal notranslate"><span class="pre">range</span></code> with <code class="docutils literal notranslate"><span class="pre">H4</span></code><a class="headerlink" href="#range-with-h4" title="Permalink to this headline">¶</a></h4>
 419 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">H4</span> <span class="o">==</span> <span class="n">c</span>  <span class="n">swap</span> <span class="p">[</span><span class="n">P</span><span class="p">]</span>    <span class="p">[</span><span class="n">pop</span><span class="p">]</span> <span class="p">[[</span><span class="n">F</span><span class="p">]</span>     <span class="n">dupdip</span> <span class="n">G</span> <span class="p">]</span> <span class="n">primrec</span>
 420    <span class="o">==</span> <span class="p">[]</span> <span class="n">swap</span> <span class="p">[</span><span class="mi">0</span> <span class="o">&lt;=</span><span class="p">]</span> <span class="p">[</span><span class="n">pop</span><span class="p">]</span> <span class="p">[[</span><span class="n">swons</span><span class="p">]</span> <span class="n">dupdip</span> <span class="o">--</span><span class="p">]</span> <span class="n">primrec</span>
 421 </pre></div>
 422 </div>
 423 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">&#39;ranger_reverse == [] swap [0 &lt;=] [pop] [[swons] dupdip --] primrec&#39;</span><span class="p">)</span>
 424 </pre></div>
 425 </div>
 426 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;5 ranger_reverse&#39;</span><span class="p">)</span>
 427 </pre></div>
 428 </div>
 429 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span> <span class="mi">4</span> <span class="mi">5</span><span class="p">]</span>
 430 </pre></div>
 431 </div>
 432 <p>Hopefully this illustrates the workings of the variations. For more
 433 insight you can run the cells using the <code class="docutils literal notranslate"><span class="pre">V()</span></code> function instead of the
 434 <code class="docutils literal notranslate"><span class="pre">J()</span></code> function to get a trace of the Joy evaluation.</p>
 435 </section>
 436 </section>
 437 </section>
 438 <section id="catamorphism">
 439 <h2>Catamorphism<a class="headerlink" href="#catamorphism" title="Permalink to this headline">¶</a></h2>
 440 <p>A catamorphism can be defined as a hylomorphism that uses
 441 <code class="docutils literal notranslate"><span class="pre">[uncons</span> <span class="pre">swap]</span></code> for <code class="docutils literal notranslate"><span class="pre">[G]</span></code> and <code class="docutils literal notranslate"><span class="pre">[[]</span> <span class="pre">=]</span></code> (or just <code class="docutils literal notranslate"><span class="pre">[not]</span></code>) for the
 442 predicate <code class="docutils literal notranslate"><span class="pre">[P]</span></code>. A catamorphic function tears down a list term-by-term
 443 and makes some new value.</p>
 444 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">C</span> <span class="o">==</span> <span class="p">[</span><span class="ow">not</span><span class="p">]</span> <span class="n">c</span> <span class="p">[</span><span class="n">uncons</span> <span class="n">swap</span><span class="p">]</span> <span class="p">[</span><span class="n">F</span><span class="p">]</span> <span class="n">hylomorphism</span>
 445 </pre></div>
 446 </div>
 447 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">&#39;swuncons == uncons swap&#39;</span><span class="p">)</span>  <span class="c1"># Awkward name.</span>
 448 </pre></div>
 449 </div>
 450 <p>An example of a catamorphism is the sum function.</p>
 451 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="nb">sum</span> <span class="o">==</span> <span class="p">[</span><span class="ow">not</span><span class="p">]</span> <span class="mi">0</span> <span class="p">[</span><span class="n">swuncons</span><span class="p">]</span> <span class="p">[</span><span class="o">+</span><span class="p">]</span> <span class="n">hylomorphism</span>
 452 </pre></div>
 453 </div>
 454 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">&#39;sum == [not] 0 [swuncons] [+] hylomorphism&#39;</span><span class="p">)</span>
 455 </pre></div>
 456 </div>
 457 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;[5 4 3 2 1] sum&#39;</span><span class="p">)</span>
 458 </pre></div>
 459 </div>
 460 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">15</span>
 461 </pre></div>
 462 </div>
 463 <section id="the-step-combinator">
 464 <h3>The <code class="docutils literal notranslate"><span class="pre">step</span></code> combinator<a class="headerlink" href="#the-step-combinator" title="Permalink to this headline">¶</a></h3>
 465 <p>The <code class="docutils literal notranslate"><span class="pre">step</span></code> combinator will usually be better to use than
 466 <code class="docutils literal notranslate"><span class="pre">catamorphism</span></code>.</p>
 467 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;[step] help&#39;</span><span class="p">)</span>
 468 </pre></div>
 469 </div>
 470 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">Run</span> <span class="n">a</span> <span class="n">quoted</span> <span class="n">program</span> <span class="n">on</span> <span class="n">each</span> <span class="n">item</span> <span class="ow">in</span> <span class="n">a</span> <span class="n">sequence</span><span class="o">.</span>
 471 <span class="p">::</span>
 472
 473         <span class="o">...</span> <span class="p">[]</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="o">.</span> <span class="n">step</span>
 474      <span class="o">-----------------------</span>
 475                <span class="o">...</span> <span class="o">.</span>
 476
 477
 478        <span class="o">...</span> <span class="p">[</span><span class="n">a</span><span class="p">]</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="o">.</span> <span class="n">step</span>
 479     <span class="o">------------------------</span>
 480              <span class="o">...</span> <span class="n">a</span> <span class="o">.</span> <span class="n">Q</span>
 481
 482
 483      <span class="o">...</span> <span class="p">[</span><span class="n">a</span> <span class="n">b</span> <span class="n">c</span><span class="p">]</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="o">.</span> <span class="n">step</span>
 484   <span class="o">----------------------------------------</span>
 485                <span class="o">...</span> <span class="n">a</span> <span class="o">.</span> <span class="n">Q</span> <span class="p">[</span><span class="n">b</span> <span class="n">c</span><span class="p">]</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="n">step</span>
 486
 487 <span class="n">The</span> <span class="n">step</span> <span class="n">combinator</span> <span class="n">executes</span> <span class="n">the</span> <span class="n">quotation</span> <span class="n">on</span> <span class="n">each</span> <span class="n">member</span> <span class="n">of</span> <span class="n">the</span> <span class="nb">list</span>
 488 <span class="n">on</span> <span class="n">top</span> <span class="n">of</span> <span class="n">the</span> <span class="n">stack</span><span class="o">.</span>
 489 </pre></div>
 490 </div>
 491 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">&#39;sum == 0 swap [+] step&#39;</span><span class="p">)</span>
 492 </pre></div>
 493 </div>
 494 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;[5 4 3 2 1] sum&#39;</span><span class="p">)</span>
 495 </pre></div>
 496 </div>
 497 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">15</span>
 498 </pre></div>
 499 </div>
 500 </section>
 501 </section>
 502 <section id="example-factorial-function">
 503 <h2>Example: Factorial Function<a class="headerlink" href="#example-factorial-function" title="Permalink to this headline">¶</a></h2>
 504 <p>For the Factorial function:</p>
 505 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">H4</span> <span class="o">==</span> <span class="n">c</span> <span class="n">swap</span> <span class="p">[</span><span class="n">P</span><span class="p">]</span> <span class="p">[</span><span class="n">pop</span><span class="p">]</span> <span class="p">[[</span><span class="n">F</span><span class="p">]</span> <span class="n">dupdip</span> <span class="n">G</span><span class="p">]</span> <span class="n">primrec</span>
 506 </pre></div>
 507 </div>
 508 <p>With:</p>
 509 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">c</span> <span class="o">==</span> <span class="mi">1</span>
 510 <span class="n">F</span> <span class="o">==</span> <span class="o">*</span>
 511 <span class="n">G</span> <span class="o">==</span> <span class="o">--</span>
 512 <span class="n">P</span> <span class="o">==</span> <span class="mi">1</span> <span class="o">&lt;=</span>
 513 </pre></div>
 514 </div>
 515 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">&#39;factorial == 1 swap [1 &lt;=] [pop] [[*] dupdip --] primrec&#39;</span><span class="p">)</span>
 516 </pre></div>
 517 </div>
 518 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;5 factorial&#39;</span><span class="p">)</span>
 519 </pre></div>
 520 </div>
 521 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">120</span>
 522 </pre></div>
 523 </div>
 524 </section>
 525 <section id="example-tails">
 526 <h2>Example: <code class="docutils literal notranslate"><span class="pre">tails</span></code><a class="headerlink" href="#example-tails" title="Permalink to this headline">¶</a></h2>
 527 <p>An example of a paramorphism for lists given in the <a class="reference external" href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.125">“Bananas…”
 528 paper</a>
 529 is <code class="docutils literal notranslate"><span class="pre">tails</span></code> which returns the list of “tails” of a list.</p>
 530 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>    <span class="p">[</span><span class="mi">1</span> <span class="mi">2</span> <span class="mi">3</span><span class="p">]</span> <span class="n">tails</span>
 531 <span class="o">--------------------</span>
 532    <span class="p">[[]</span> <span class="p">[</span><span class="mi">3</span><span class="p">]</span> <span class="p">[</span><span class="mi">2</span> <span class="mi">3</span><span class="p">]]</span>
 533 </pre></div>
 534 </div>
 535 <p>We can build as we go, and we want <code class="docutils literal notranslate"><span class="pre">F</span></code> to run after <code class="docutils literal notranslate"><span class="pre">G</span></code>, so we use
 536 pattern <code class="docutils literal notranslate"><span class="pre">H2</span></code>:</p>
 537 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">H2</span> <span class="o">==</span> <span class="n">c</span> <span class="n">swap</span> <span class="p">[</span><span class="n">P</span><span class="p">]</span> <span class="p">[</span><span class="n">pop</span><span class="p">]</span> <span class="p">[</span><span class="n">G</span> <span class="p">[</span><span class="n">F</span><span class="p">]</span> <span class="n">dip</span><span class="p">]</span> <span class="n">primrec</span>
 538 </pre></div>
 539 </div>
 540 <p>We would use:</p>
 541 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">c</span> <span class="o">==</span> <span class="p">[]</span>
 542 <span class="n">F</span> <span class="o">==</span> <span class="n">swons</span>
 543 <span class="n">G</span> <span class="o">==</span> <span class="n">rest</span> <span class="n">dup</span>
 544 <span class="n">P</span> <span class="o">==</span> <span class="ow">not</span>
 545 </pre></div>
 546 </div>
 547 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">&#39;tails == [] swap [not] [pop] [rest dup [swons] dip] primrec&#39;</span><span class="p">)</span>
 548 </pre></div>
 549 </div>
 550 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;[1 2 3] tails&#39;</span><span class="p">)</span>
 551 </pre></div>
 552 </div>
 553 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[[]</span> <span class="p">[</span><span class="mi">3</span><span class="p">]</span> <span class="p">[</span><span class="mi">2</span> <span class="mi">3</span><span class="p">]]</span>
 554 </pre></div>
 555 </div>
 556 </section>
 557 <section id="conclusion-patterns-of-recursion">
 558 <h2>Conclusion: Patterns of Recursion<a class="headerlink" href="#conclusion-patterns-of-recursion" title="Permalink to this headline">¶</a></h2>
 559 <p>Our story so far…</p>
 560 <section id="hylo-ana-cata">
 561 <h3>Hylo-, Ana-, Cata-<a class="headerlink" href="#hylo-ana-cata" title="Permalink to this headline">¶</a></h3>
 562 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">H</span> <span class="o">==</span> <span class="p">[</span><span class="n">P</span>  <span class="p">]</span> <span class="p">[</span><span class="n">pop</span> <span class="n">c</span> <span class="p">]</span> <span class="p">[</span><span class="n">G</span>          <span class="p">]</span> <span class="p">[</span><span class="n">dip</span> <span class="n">F</span>        <span class="p">]</span> <span class="n">genrec</span>
 563 <span class="n">A</span> <span class="o">==</span> <span class="p">[</span><span class="n">P</span>  <span class="p">]</span> <span class="p">[</span><span class="n">pop</span> <span class="p">[]]</span> <span class="p">[</span><span class="n">G</span>          <span class="p">]</span> <span class="p">[</span><span class="n">dip</span> <span class="n">swap</span> <span class="n">cons</span><span class="p">]</span> <span class="n">genrec</span>
 564 <span class="n">C</span> <span class="o">==</span> <span class="p">[</span><span class="ow">not</span><span class="p">]</span> <span class="p">[</span><span class="n">pop</span> <span class="n">c</span> <span class="p">]</span> <span class="p">[</span><span class="n">uncons</span> <span class="n">swap</span><span class="p">]</span> <span class="p">[</span><span class="n">dip</span> <span class="n">F</span>        <span class="p">]</span> <span class="n">genrec</span>
 565 </pre></div>
 566 </div>
 567 </section>
 568 <section id="para">
 569 <h3>Para-, ?-, ?-<a class="headerlink" href="#para" title="Permalink to this headline">¶</a></h3>
 570 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>P == c  swap [P  ] [pop] [[F        ] dupdip G          ] primrec
 571 ? == [] swap [P  ] [pop] [[swap cons] dupdip G          ] primrec
 572 ? == c  swap [not] [pop] [[F        ] dupdip uncons swap] primrec
 573 </pre></div>
 574 </div>
 575 </section>
 576 </section>
 577 <section id="appendix-fun-with-symbols">
 578 <h2>Appendix: Fun with Symbols<a class="headerlink" href="#appendix-fun-with-symbols" title="Permalink to this headline">¶</a></h2>
 579 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>|[ (c, F), (G, P) ]| == (|c, F|) • [(G, P)]
 580 </pre></div>
 581 </div>
 582 <p><a class="reference external" href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.125">“Bananas, Lenses, &amp; Barbed
 583 Wire”</a></p>
 584 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">(</span><span class="o">|...|</span><span class="p">)</span>  <span class="p">[(</span><span class="o">...</span><span class="p">)]</span>  <span class="p">[</span><span class="o">&lt;...&gt;</span><span class="p">]</span>
 585 </pre></div>
 586 </div>
 587 <p>I think they are having slightly too much fun with the symbols. However,
 588 “Too much is always better than not enough.”</p>
 589 </section>
 590 </section>
 591
 592
 593           </div>
 594
 595         </div>
 596       </div>
 597       <div class="sphinxsidebar" role="navigation" aria-label="main navigation">
 598         <div class="sphinxsidebarwrapper">
 599 <h1 class="logo"><a href="../index.html">Thun</a></h1>
 600
 601
 602
 603
 604
 605
 606
 607
 608 <h3>Navigation</h3>
 609 <ul class="current">
 610 <li class="toctree-l1"><a class="reference internal" href="Intro.html">Thun: Joy in Python</a></li>
 611 <li class="toctree-l1"><a class="reference internal" href="../joy.html">Joy Interpreter</a></li>
 612 <li class="toctree-l1"><a class="reference internal" href="../stack.html">Stack or Quote or Sequence or List…</a></li>
 613 <li class="toctree-l1"><a class="reference internal" href="../parser.html">Parsing Text into Joy Expressions</a></li>
 614 <li class="toctree-l1"><a class="reference internal" href="../pretty.html">Tracing Joy Execution</a></li>
 615 <li class="toctree-l1"><a class="reference internal" href="../library.html">Function Reference</a></li>
 616 <li class="toctree-l1"><a class="reference internal" href="../lib.html">Functions Grouped by, er, Function with Examples</a></li>
 617 <li class="toctree-l1"><a class="reference internal" href="../types.html">Type Inference of Joy Expressions</a></li>
 618 <li class="toctree-l1 current"><a class="reference internal" href="index.html">Essays about Programming in Joy</a><ul class="current">
 619 <li class="toctree-l2"><a class="reference internal" href="Developing.html">Developing a Program in Joy</a></li>
 620 <li class="toctree-l2"><a class="reference internal" href="Quadratic.html">Quadratic formula</a></li>
 621 <li class="toctree-l2"><a class="reference internal" href="Replacing.html">Replacing Functions in the Dictionary</a></li>
 622 <li class="toctree-l2 current"><a class="current reference internal" href="#">Recursion Combinators</a></li>
 623 <li class="toctree-l2"><a class="reference internal" href="Ordered_Binary_Trees.html">Treating Trees I: Ordered Binary Trees</a></li>
 624 <li class="toctree-l2"><a class="reference internal" href="Treestep.html">Treating Trees II: <code class="docutils literal notranslate"><span class="pre">treestep</span></code></a></li>
 625 <li class="toctree-l2"><a class="reference internal" href="Generator_Programs.html">Using <code class="docutils literal notranslate"><span class="pre">x</span></code> to Generate Values</a></li>
 626 <li class="toctree-l2"><a class="reference internal" href="Newton-Raphson.html">Newton’s method</a></li>
 627 <li class="toctree-l2"><a class="reference internal" href="Square_Spiral.html">Square Spiral Example Joy Code</a></li>
 628 <li class="toctree-l2"><a class="reference internal" href="Zipper.html">Traversing Datastructures with Zippers</a></li>
 629 <li class="toctree-l2"><a class="reference internal" href="Types.html">The Blissful Elegance of Typing Joy</a></li>
 630 <li class="toctree-l2"><a class="reference internal" href="TypeChecking.html">Type Checking</a></li>
 631 <li class="toctree-l2"><a class="reference internal" href="NoUpdates.html">No Updates</a></li>
 632 <li class="toctree-l2"><a class="reference internal" href="Categorical.html">Categorical Programming</a></li>
 633 <li class="toctree-l2"><a class="reference internal" href="The_Four_Operations.html">The Four Fundamental Operations of Definite Action</a></li>
 634 <li class="toctree-l2"><a class="reference internal" href="Derivatives_of_Regular_Expressions.html">∂RE</a></li>
 635 </ul>
 636 </li>
 637 </ul>
 638
 639 <div class="relations">
 640 <h3>Related Topics</h3>
 641 <ul>
 642   <li><a href="../index.html">Documentation overview</a><ul>
 643   <li><a href="index.html">Essays about Programming in Joy</a><ul>
 644       <li>Previous: <a href="Replacing.html" title="previous chapter">Replacing Functions in the Dictionary</a></li>
 645       <li>Next: <a href="Ordered_Binary_Trees.html" title="next chapter">Treating Trees I: Ordered Binary Trees</a></li>
 646   </ul></li>
 647   </ul></li>
 648 </ul>
 649 </div>
 650 <div id="searchbox" style="display: none" role="search">
 651   <h3 id="searchlabel">Quick search</h3>
 652     <div class="searchformwrapper">
 653     <form class="search" action="../search.html" method="get">
 654       <input type="text" name="q" aria-labelledby="searchlabel" autocomplete="off" autocorrect="off" autocapitalize="off" spellcheck="false"/>
 655       <input type="submit" value="Go" />
 656     </form>
 657     </div>
 658 </div>
 659 <script>$('#searchbox').show(0);</script>
 660
 661
 662
 663
 664
 665
 666
 667
 668         </div>
 669       </div>
 670       <div class="clearer"></div>
 671     </div>
 672     <div class="footer" role="contentinfo">
 673 <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/">
 674 <img alt="Creative Commons License" style="border-width:0" src="https://i.creativecommons.org/l/by-nc-sa/4.0/88x31.png" />
 675 </a>
 676 <br />
 677 <span xmlns:dct="http://purl.org/dc/terms/" property="dct:title">Thun Documentation</span> by <a xmlns:cc="http://creativecommons.org/ns#" href="https://joypy.osdn.io/" property="cc:attributionName" rel="cc:attributionURL">Simon Forman</a> is licensed under a <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/">Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License</a>.<br />Based on a work at <a xmlns:dct="http://purl.org/dc/terms/" href="https://osdn.net/projects/joypy/" rel="dct:source">https://osdn.net/projects/joypy/</a>.
 678       Created using <a href="http://sphinx-doc.org/">Sphinx</a> 4.3.0.
 679     </div>
 680
 681   </body>
 682 </html>