</section>
<section id="define-treestep">
<h2>Define <code class="docutils literal notranslate"><span class="pre">treestep</span></code><a class="headerlink" href="#define-treestep" title="Permalink to this headline">¶</a></h2>
-<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">J</span><span class="p">,</span> <span class="n">V</span><span class="p">,</span> <span class="n">define</span><span class="p">,</span> <span class="n">DefinitionWrapper</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">J</span><span class="p">,</span> <span class="n">V</span><span class="p">,</span> <span class="n">define</span><span class="p">,</span> <span class="n">DefinitionWrapper</span>
</pre></div>
</div>
-<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">DefinitionWrapper</span><span class="o">.</span><span class="n">add_definitions</span><span class="p">(</span><span class="s1">'''</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">DefinitionWrapper</span><span class="o">.</span><span class="n">add_definitions</span><span class="p">(</span><span class="s1">'''</span>
<span class="s1"> _treestep_0 == [[not] swap] dip</span>
<span class="s1"> _treestep_1 == [dip] cons [uncons] swoncat</span>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">sumtree</span> <span class="o">==</span> <span class="p">[</span><span class="n">pop</span> <span class="mi">0</span><span class="p">]</span> <span class="p">[]</span> <span class="p">[</span><span class="nb">sum</span> <span class="o">+</span><span class="p">]</span> <span class="n">treestep</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">'sumtree == [pop 0] [] [sum +] treestep'</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">'sumtree == [pop 0] [] [sum +] treestep'</span><span class="p">)</span>
</pre></div>
</div>
<p>Running this function on an empty tree value gives zero:</p>
<span class="mi">0</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">'[] sumtree'</span><span class="p">)</span> <span class="c1"># Empty tree.</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'[] sumtree'</span><span class="p">)</span> <span class="c1"># Empty tree.</span>
</pre></div>
</div>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">0</span>
<span class="n">n</span><span class="o">+</span><span class="n">m</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">'[23] sumtree'</span><span class="p">)</span> <span class="c1"># No child trees.</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'[23] sumtree'</span><span class="p">)</span> <span class="c1"># No child trees.</span>
</pre></div>
</div>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">23</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">'[23 []] sumtree'</span><span class="p">)</span> <span class="c1"># Child tree, empty.</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'[23 []] sumtree'</span><span class="p">)</span> <span class="c1"># Child tree, empty.</span>
</pre></div>
</div>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">23</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">'[23 [2 [4]] [3]] sumtree'</span><span class="p">)</span> <span class="c1"># Non-empty child trees.</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'[23 [2 [4]] [3]] sumtree'</span><span class="p">)</span> <span class="c1"># Non-empty child trees.</span>
</pre></div>
</div>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">32</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">'[23 [2 [8] [9]] [3] [4 []]] sumtree'</span><span class="p">)</span> <span class="c1"># Etc...</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'[23 [2 [8] [9]] [3] [4 []]] sumtree'</span><span class="p">)</span> <span class="c1"># Etc...</span>
</pre></div>
</div>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">49</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">'[23 [2 [8] [9]] [3] [4 []]] [pop 0] [] [cons sum] treestep'</span><span class="p">)</span> <span class="c1"># Alternate "spelling".</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'[23 [2 [8] [9]] [3] [4 []]] [pop 0] [] [cons sum] treestep'</span><span class="p">)</span> <span class="c1"># Alternate "spelling".</span>
</pre></div>
</div>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">49</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">'[23 [2 [8] [9]] [3] [4 []]] [] [pop 23] [cons] treestep'</span><span class="p">)</span> <span class="c1"># Replace each node.</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'[23 [2 [8] [9]] [3] [4 []]] [] [pop 23] [cons] treestep'</span><span class="p">)</span> <span class="c1"># Replace each node.</span>
</pre></div>
</div>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="mi">23</span> <span class="p">[</span><span class="mi">23</span> <span class="p">[</span><span class="mi">23</span><span class="p">]</span> <span class="p">[</span><span class="mi">23</span><span class="p">]]</span> <span class="p">[</span><span class="mi">23</span><span class="p">]</span> <span class="p">[</span><span class="mi">23</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">'[23 [2 [8] [9]] [3] [4 []]] [] [pop 1] [cons] treestep'</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">'[23 [2 [8] [9]] [3] [4 []]] [] [pop 1] [cons] treestep'</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="p">[</span><span class="mi">1</span> <span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="p">[</span><span class="mi">1</span><span class="p">]]</span> <span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="p">[</span><span class="mi">1</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">'[23 [2 [8] [9]] [3] [4 []]] [] [pop 1] [cons] treestep sumtree'</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">'[23 [2 [8] [9]] [3] [4 []]] [] [pop 1] [cons] treestep sumtree'</span><span class="p">)</span>
</pre></div>
</div>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">6</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">'[23 [2 [8] [9]] [3] [4 []]] [pop 0] [pop 1] [sum +] treestep'</span><span class="p">)</span> <span class="c1"># Combine replace and sum into one function.</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'[23 [2 [8] [9]] [3] [4 []]] [pop 0] [pop 1] [sum +] treestep'</span><span class="p">)</span> <span class="c1"># Combine replace and sum into one function.</span>
</pre></div>
</div>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">6</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">'[4 [3 [] [7]]] [pop 0] [pop 1] [sum +] treestep'</span><span class="p">)</span> <span class="c1"># Combine replace and sum into one function.</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'[4 [3 [] [7]]] [pop 0] [pop 1] [sum +] treestep'</span><span class="p">)</span> <span class="c1"># Combine replace and sum into one function.</span>
</pre></div>
</div>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">3</span>
</pre></div>
</div>
<p>This doesn’t quite work:</p>
-<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'[[3 0] [[2 0] [][]] [[9 0] [[5 0] [[4 0] [][]] [[8 0] [[6 0] [] [[7 0] [][]]][]]][]]] ["B"] [first] [i] treestep'</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">'[[3 0] [[2 0] [][]] [[9 0] [[5 0] [[4 0] [][]] [[8 0] [[6 0] [] [[7 0] [][]]][]]][]]] ["B"] [first] [i] treestep'</span><span class="p">)</span>
</pre></div>
</div>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">3</span> <span class="s1">'B'</span> <span class="s1">'B'</span>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[]</span> <span class="p">[</span><span class="n">first</span><span class="p">]</span> <span class="p">[</span><span class="n">flatten</span> <span class="n">cons</span><span class="p">]</span> <span class="n">treestep</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">'[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]] [] [first] [flatten cons] treestep'</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">'[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]] [] [first] [flatten cons] treestep'</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">3</span> <span class="mi">2</span> <span class="mi">9</span> <span class="mi">5</span> <span class="mi">4</span> <span class="mi">8</span> <span class="mi">6</span> <span class="mi">7</span><span class="p">]</span>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[]</span> <span class="p">[</span><span class="n">i</span> <span class="n">roll</span><span class="o"><</span> <span class="n">swons</span> <span class="n">concat</span><span class="p">]</span> <span class="p">[</span><span class="n">first</span><span class="p">]</span> <span class="n">treestep</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">'[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]] [] [uncons pop] [i roll< swons concat] treestep'</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">'[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]] [] [uncons pop] [i roll< swons concat] treestep'</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">2</span> <span class="mi">3</span> <span class="mi">4</span> <span class="mi">5</span> <span class="mi">6</span> <span class="mi">7</span> <span class="mi">8</span> <span class="mi">9</span><span class="p">]</span>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">key</span> <span class="n">value</span><span class="p">]</span> <span class="n">N</span> <span class="p">[</span><span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">K</span><span class="p">]</span> <span class="n">C</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">'[["key" "value"] ["left"] ["right"] ] ["B"] ["N"] ["C"] treegrind'</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">'[["key" "value"] ["left"] ["right"] ] ["B"] ["N"] ["C"] treegrind'</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="s1">'key'</span> <span class="s1">'value'</span><span class="p">]</span> <span class="s1">'N'</span> <span class="p">[[</span><span class="s1">'left'</span><span class="p">]</span> <span class="p">[</span><span class="s1">'right'</span><span class="p">]]</span> <span class="p">[[</span><span class="ow">not</span><span class="p">]</span> <span class="p">[</span><span class="s1">'B'</span><span class="p">]</span> <span class="p">[</span><span class="n">uncons</span> <span class="p">[</span><span class="s1">'N'</span><span class="p">]</span> <span class="n">dip</span><span class="p">]</span> <span class="p">[</span><span class="s1">'C'</span><span class="p">]</span> <span class="n">genrec</span><span class="p">]</span> <span class="s1">'C'</span>
<section id="treegrind-with-step">
<h2><code class="docutils literal notranslate"><span class="pre">treegrind</span></code> with <code class="docutils literal notranslate"><span class="pre">step</span></code><a class="headerlink" href="#treegrind-with-step" title="Permalink to this headline">¶</a></h2>
<p>Iteration through the nodes</p>
-<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]] [pop] ["N"] [step] treegrind'</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">'[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]] [pop] ["N"] [step] treegrind'</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">3</span> <span class="mi">0</span><span class="p">]</span> <span class="s1">'N'</span> <span class="p">[</span><span class="mi">2</span> <span class="mi">0</span><span class="p">]</span> <span class="s1">'N'</span> <span class="p">[</span><span class="mi">9</span> <span class="mi">0</span><span class="p">]</span> <span class="s1">'N'</span> <span class="p">[</span><span class="mi">5</span> <span class="mi">0</span><span class="p">]</span> <span class="s1">'N'</span> <span class="p">[</span><span class="mi">4</span> <span class="mi">0</span><span class="p">]</span> <span class="s1">'N'</span> <span class="p">[</span><span class="mi">8</span> <span class="mi">0</span><span class="p">]</span> <span class="s1">'N'</span> <span class="p">[</span><span class="mi">6</span> <span class="mi">0</span><span class="p">]</span> <span class="s1">'N'</span> <span class="p">[</span><span class="mi">7</span> <span class="mi">0</span><span class="p">]</span> <span class="s1">'N'</span>
</pre></div>
</div>
<p>Sum the nodes’ keys.</p>
-<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'0 [[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]] [pop] [first +] [step] treegrind'</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 [[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]] [pop] [first +] [step] treegrind'</span><span class="p">)</span>
</pre></div>
</div>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">44</span>
</pre></div>
</div>
<p>Rebuild the tree using <code class="docutils literal notranslate"><span class="pre">map</span></code> (imitating <code class="docutils literal notranslate"><span class="pre">treestep</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">'[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]] [] [[100 +] infra] [map cons] treegrind'</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">'[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]] [] [[100 +] infra] [map cons] treegrind'</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">103</span> <span class="mi">0</span><span class="p">]</span> <span class="p">[[</span><span class="mi">102</span> <span class="mi">0</span><span class="p">]</span> <span class="p">[]</span> <span class="p">[]]</span> <span class="p">[[</span><span class="mi">109</span> <span class="mi">0</span><span class="p">]</span> <span class="p">[[</span><span class="mi">105</span> <span class="mi">0</span><span class="p">]</span> <span class="p">[[</span><span class="mi">104</span> <span class="mi">0</span><span class="p">]</span> <span class="p">[]</span> <span class="p">[]]</span> <span class="p">[[</span><span class="mi">108</span> <span class="mi">0</span><span class="p">]</span> <span class="p">[[</span><span class="mi">106</span> <span class="mi">0</span><span class="p">]</span> <span class="p">[]</span> <span class="p">[[</span><span class="mi">107</span> <span class="mi">0</span><span class="p">]</span> <span class="p">[]</span> <span class="p">[]]]</span> <span class="p">[]]]</span> <span class="p">[]]]</span>
</pre></div>
</div>
<p>To me, that seems simpler than the <code class="docutils literal notranslate"><span class="pre">genrec</span></code> version.</p>
-<div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">DefinitionWrapper</span><span class="o">.</span><span class="n">add_definitions</span><span class="p">(</span><span class="s1">'''</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">DefinitionWrapper</span><span class="o">.</span><span class="n">add_definitions</span><span class="p">(</span><span class="s1">'''</span>
<span class="s1"> T> == pop [first] dip i</span>
<span class="s1"> T< == pop [second] dip i</span>
<span class="s1">'''</span><span class="p">,</span> <span class="n">D</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">'''</span><span class="se">\</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'''</span><span class="se">\</span>
<span class="s1">[[3 13] [[2 12] [] []] [[9 19] [[5 15] [[4 14] [] []] [[8 18] [[6 16] [] [[7 17] [] []]] []]] []]]</span>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">15</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">'''</span><span class="se">\</span>
+<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'''</span><span class="se">\</span>
<span class="s1">[[3 13] [[2 12] [] []] [[9 19] [[5 15] [[4 14] [] []] [[8 18] [[6 16] [] [[7 17] [] []]] []]] []]]</span>