<div class="body" role="main">
- <div class="highlight-python 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>
+ <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>
</pre></div>
</div>
<section id="recursion-combinators">
</ul>
<p>It may be helpful to see this function implemented in imperative Python
code.</p>
-<div class="highlight-python 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>
+<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>
<span class="sd">'''Return a hylomorphism function H.'''</span>
<span class="k">def</span> <span class="nf">H</span><span class="p">(</span><span class="n">a</span><span class="p">):</span>
<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>
</pre></div>
</div>
-<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'hylomorphism == [unit [pop] swoncat] dipd [dip] swoncat genrec'</span><span class="p">)</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'hylomorphism == [unit [pop] swoncat] dipd [dip] swoncat genrec'</span><span class="p">)</span>
</pre></div>
</div>
<section id="example-finding-triangular-numbers">
<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>
<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>
</ul>
-<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'triangular_number == [1 <=] 0 [-- dup] [+] hylomorphism'</span><span class="p">)</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'triangular_number == [1 <=] 0 [-- dup] [+] hylomorphism'</span><span class="p">)</span>
</pre></div>
</div>
<p>Let’s try it:</p>
-<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'5 triangular_number'</span><span class="p">)</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'5 triangular_number'</span><span class="p">)</span>
</pre></div>
</div>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">10</span>
</pre></div>
</div>
-<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'[0 1 2 3 4 5 6] [triangular_number] map'</span><span class="p">)</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'[0 1 2 3 4 5 6] [triangular_number] map'</span><span class="p">)</span>
</pre></div>
</div>
<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>
<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>
</pre></div>
</div>
-<section id="range-et-al">
-<h3><code class="docutils literal notranslate"><span class="pre">range</span></code> et. al.<a class="headerlink" href="#range-et-al" title="Permalink to this headline">¶</a></h3>
-<p>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>.</p>
+<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">
+<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>
<p>Each of the above variations can be used to make four slightly different
<code class="docutils literal notranslate"><span class="pre">range</span></code> functions.</p>
<section id="range-with-h1">
<span class="o">==</span> <span class="p">[</span><span class="mi">0</span> <span class="o"><=</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>
</pre></div>
</div>
-<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'range == [0 <=] [] [-- dup] [swons] hylomorphism'</span><span class="p">)</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'range == [0 <=] [] [-- dup] [swons] hylomorphism'</span><span class="p">)</span>
</pre></div>
</div>
-<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'5 range'</span><span class="p">)</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'5 range'</span><span class="p">)</span>
</pre></div>
</div>
<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>
<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"><=</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>
</pre></div>
</div>
-<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'range_reverse == [] swap [0 <=] [pop] [-- dup [swons] dip] primrec'</span><span class="p">)</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'range_reverse == [] swap [0 <=] [pop] [-- dup [swons] dip] primrec'</span><span class="p">)</span>
</pre></div>
</div>
-<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'5 range_reverse'</span><span class="p">)</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'5 range_reverse'</span><span class="p">)</span>
</pre></div>
</div>
<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>
<span class="o">==</span> <span class="p">[</span><span class="mi">0</span> <span class="o"><=</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>
</pre></div>
</div>
-<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'ranger == [0 <=] [pop []] [[--] dupdip] [dip swons] genrec'</span><span class="p">)</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'ranger == [0 <=] [pop []] [[--] dupdip] [dip swons] genrec'</span><span class="p">)</span>
</pre></div>
</div>
-<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'5 ranger'</span><span class="p">)</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'5 ranger'</span><span class="p">)</span>
</pre></div>
</div>
<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>
<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"><=</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>
</pre></div>
</div>
-<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'ranger_reverse == [] swap [0 <=] [pop] [[swons] dupdip --] primrec'</span><span class="p">)</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'ranger_reverse == [] swap [0 <=] [pop] [[swons] dupdip --] primrec'</span><span class="p">)</span>
</pre></div>
</div>
-<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'5 ranger_reverse'</span><span class="p">)</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'5 ranger_reverse'</span><span class="p">)</span>
</pre></div>
</div>
<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>
<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>
</pre></div>
</div>
-<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'swuncons == uncons swap'</span><span class="p">)</span> <span class="c1"># Awkward name.</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'swuncons == uncons swap'</span><span class="p">)</span> <span class="c1"># Awkward name.</span>
</pre></div>
</div>
<p>An example of a catamorphism is the sum function.</p>
<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>
</pre></div>
</div>
-<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'sum == [not] 0 [swuncons] [+] hylomorphism'</span><span class="p">)</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'sum == [not] 0 [swuncons] [+] hylomorphism'</span><span class="p">)</span>
</pre></div>
</div>
-<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'[5 4 3 2 1] sum'</span><span class="p">)</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'[5 4 3 2 1] sum'</span><span class="p">)</span>
</pre></div>
</div>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">15</span>
<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>
<p>The <code class="docutils literal notranslate"><span class="pre">step</span></code> combinator will usually be better to use than
<code class="docutils literal notranslate"><span class="pre">catamorphism</span></code>.</p>
-<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'[step] help'</span><span class="p">)</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'[step] help'</span><span class="p">)</span>
</pre></div>
</div>
<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>
<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>
</pre></div>
</div>
-<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'sum == 0 swap [+] step'</span><span class="p">)</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'sum == 0 swap [+] step'</span><span class="p">)</span>
</pre></div>
</div>
-<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'[5 4 3 2 1] sum'</span><span class="p">)</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'[5 4 3 2 1] sum'</span><span class="p">)</span>
</pre></div>
</div>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">15</span>
<span class="n">P</span> <span class="o">==</span> <span class="mi">1</span> <span class="o"><=</span>
</pre></div>
</div>
-<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'factorial == 1 swap [1 <=] [pop] [[*] dupdip --] primrec'</span><span class="p">)</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'factorial == 1 swap [1 <=] [pop] [[*] dupdip --] primrec'</span><span class="p">)</span>
</pre></div>
</div>
-<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'5 factorial'</span><span class="p">)</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'5 factorial'</span><span class="p">)</span>
</pre></div>
</div>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">120</span>
<span class="n">P</span> <span class="o">==</span> <span class="ow">not</span>
</pre></div>
</div>
-<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'tails == [] swap [not] [pop] [rest dup [swons] dip] primrec'</span><span class="p">)</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">'tails == [] swap [not] [pop] [rest dup [swons] dip] primrec'</span><span class="p">)</span>
</pre></div>
</div>
-<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'[1 2 3] tails'</span><span class="p">)</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'[1 2 3] tails'</span><span class="p">)</span>
</pre></div>
</div>
<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>