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

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