docs/sphinx_docs/_build/html/notebooks/Ordered_Binary_Trees.html

   1
   2 <!DOCTYPE html>
   3
   4 <html>
   5   <head>
   6     <meta charset="utf-8" />
   7     <meta name="viewport" content="width=device-width, initial-scale=1.0" /><meta name="generator" content="Docutils 0.17.1: http://docutils.sourceforge.net/" />
   8
   9     <title>Treating Trees I: Ordered Binary Trees &#8212; Thun 0.4.1 documentation</title>
  10     <link rel="stylesheet" type="text/css" href="../_static/pygments.css" />
  11     <link rel="stylesheet" type="text/css" href="../_static/alabaster.css" />
  12     <script data-url_root="../" id="documentation_options" src="../_static/documentation_options.js"></script>
  13     <script src="../_static/jquery.js"></script>
  14     <script src="../_static/underscore.js"></script>
  15     <script src="../_static/doctools.js"></script>
  16     <link rel="index" title="Index" href="../genindex.html" />
  17     <link rel="search" title="Search" href="../search.html" />
  18     <link rel="next" title="Treating Trees II: treestep" href="Treestep.html" />
  19     <link rel="prev" title="Recursion Combinators" href="Recursion_Combinators.html" />
  20
  21   <link rel="stylesheet" href="../_static/custom.css" type="text/css" />
  22
  23
  24   <meta name="viewport" content="width=device-width, initial-scale=0.9, maximum-scale=0.9" />
  25
  26   </head><body>
  27
  28
  29     <div class="document">
  30       <div class="documentwrapper">
  31         <div class="bodywrapper">
  32
  33
  34           <div class="body" role="main">
  35
  36   <section id="treating-trees-i-ordered-binary-trees">
  37 <h1>Treating Trees I: Ordered Binary Trees<a class="headerlink" href="#treating-trees-i-ordered-binary-trees" title="Permalink to this headline">¶</a></h1>
  38 <p>Although any expression in Joy can be considered to describe a
  39 <a class="reference external" href="https://en.wikipedia.org/wiki/Tree_structure">tree</a> with the quotes
  40 as compound nodes and the non-quote values as leaf nodes, in this page I
  41 want to talk about <a class="reference external" href="https://en.wikipedia.org/wiki/Binary_search_tree">ordered binary
  42 trees</a> and how to
  43 make and use them.</p>
  44 <p>The basic structure, in a <a class="reference external" href="https://en.wikipedia.org/wiki/Algebraic_data_type">crude type
  45 notation</a>, is:</p>
  46 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">Tree</span> <span class="p">::</span> <span class="p">[]</span> <span class="o">|</span> <span class="p">[</span><span class="n">key</span> <span class="n">value</span> <span class="n">Tree</span> <span class="n">Tree</span><span class="p">]</span>
  47 </pre></div>
  48 </div>
  49 <p>That says that a Tree is either the empty quote <code class="docutils literal notranslate"><span class="pre">[]</span></code> or a quote with
  50 four items: a key, a value, and two Trees representing the left and
  51 right branches of the tree.</p>
  52 <p>We’re going to derive some recursive functions to work with such
  53 datastructures:</p>
  54 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">Tree</span><span class="o">-</span><span class="n">add</span>
  55 <span class="n">Tree</span><span class="o">-</span><span class="n">delete</span>
  56 <span class="n">Tree</span><span class="o">-</span><span class="n">get</span>
  57 <span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span>
  58 <span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</span>
  59 </pre></div>
  60 </div>
  61 <p>Once these functions are defined we have a new “type” to work with, and
  62 the Sufficiently Smart Compiler can be modified to use an optimized
  63 implementation under the hood. (Where does the “type” come from? It has
  64 a contingent existence predicated on the disciplined use of these
  65 functions on otherwise undistinguished Joy datastructures.)</p>
  66 <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>
  67 </pre></div>
  68 </div>
  69 <section id="adding-nodes-to-the-tree">
  70 <h2>Adding Nodes to the Tree<a class="headerlink" href="#adding-nodes-to-the-tree" title="Permalink to this headline">¶</a></h2>
  71 <p>Let’s consider adding nodes to a Tree structure.</p>
  72 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>   Tree value key Tree-add
  73 -----------------------------
  74             Tree′
  75 </pre></div>
  76 </div>
  77 <section id="adding-to-an-empty-node">
  78 <h3>Adding to an empty node.<a class="headerlink" href="#adding-to-an-empty-node" title="Permalink to this headline">¶</a></h3>
  79 <p>If the current node is <code class="docutils literal notranslate"><span class="pre">[]</span></code> then you just return
  80 <code class="docutils literal notranslate"><span class="pre">[key</span> <span class="pre">value</span> <span class="pre">[]</span> <span class="pre">[]]</span></code>:</p>
  81 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">Tree</span><span class="o">-</span><span class="n">add</span> <span class="o">==</span> <span class="p">[</span><span class="n">popop</span> <span class="ow">not</span><span class="p">]</span> <span class="p">[[</span><span class="n">pop</span><span class="p">]</span> <span class="n">dipd</span> <span class="n">Tree</span><span class="o">-</span><span class="n">new</span><span class="p">]</span> <span class="p">[</span><span class="n">R0</span><span class="p">]</span> <span class="p">[</span><span class="n">R1</span><span class="p">]</span> <span class="n">genrec</span>
  82 </pre></div>
  83 </div>
  84 <section id="tree-new">
  85 <h4><code class="docutils literal notranslate"><span class="pre">Tree-new</span></code><a class="headerlink" href="#tree-new" title="Permalink to this headline">¶</a></h4>
  86 <p>Where <code class="docutils literal notranslate"><span class="pre">Tree-new</span></code> is defined as:</p>
  87 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>   <span class="n">value</span> <span class="n">key</span> <span class="n">Tree</span><span class="o">-</span><span class="n">new</span>
  88 <span class="o">------------------------</span>
  89    <span class="p">[</span><span class="n">key</span> <span class="n">value</span> <span class="p">[]</span> <span class="p">[]]</span>
  90 </pre></div>
  91 </div>
  92 <p>Example:</p>
  93 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">value</span> <span class="n">key</span> <span class="n">swap</span> <span class="p">[[]</span> <span class="p">[]]</span> <span class="n">cons</span> <span class="n">cons</span>
  94 <span class="n">key</span> <span class="n">value</span>      <span class="p">[[]</span> <span class="p">[]]</span> <span class="n">cons</span> <span class="n">cons</span>
  95 <span class="n">key</span>      <span class="p">[</span><span class="n">value</span> <span class="p">[]</span> <span class="p">[]]</span>      <span class="n">cons</span>
  96      <span class="p">[</span><span class="n">key</span> <span class="n">value</span> <span class="p">[]</span> <span class="p">[]]</span>
  97 </pre></div>
  98 </div>
  99 <p>Definition:</p>
 100 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">Tree</span><span class="o">-</span><span class="n">new</span> <span class="o">==</span> <span class="n">swap</span> <span class="p">[[]</span> <span class="p">[]]</span> <span class="n">cons</span> <span class="n">cons</span>
 101 </pre></div>
 102 </div>
 103 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">&#39;Tree-new == swap [[] []] cons cons&#39;</span><span class="p">)</span>
 104 </pre></div>
 105 </div>
 106 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;&quot;v&quot; &quot;k&quot; Tree-new&#39;</span><span class="p">)</span>
 107 </pre></div>
 108 </div>
 109 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="s1">&#39;k&#39;</span> <span class="s1">&#39;v&#39;</span> <span class="p">[]</span> <span class="p">[]]</span>
 110 </pre></div>
 111 </div>
 112 <p>(As an implementation detail, the <code class="docutils literal notranslate"><span class="pre">[[]</span> <span class="pre">[]]</span></code> literal used in the
 113 definition of <code class="docutils literal notranslate"><span class="pre">Tree-new</span></code> will be reused to supply the <em>constant</em> tail
 114 for <em>all</em> new nodes produced by it. This is one of those cases where you
 115 get amortized storage “for free” by using <a class="reference external" href="https://en.wikipedia.org/wiki/Persistent_data_structure">persistent
 116 datastructures</a>.
 117 Because the tail, which is <code class="docutils literal notranslate"><span class="pre">((),</span> <span class="pre">((),</span> <span class="pre">()))</span></code> in Python, is immutable
 118 and embedded in the definition body for <code class="docutils literal notranslate"><span class="pre">Tree-new</span></code>, all new nodes can
 119 reuse it as their own tail without fear that some other code somewhere
 120 will change it.)</p>
 121 </section>
 122 </section>
 123 <section id="adding-to-a-non-empty-node">
 124 <h3>Adding to a non-empty node.<a class="headerlink" href="#adding-to-a-non-empty-node" title="Permalink to this headline">¶</a></h3>
 125 <p>We now have to derive <code class="docutils literal notranslate"><span class="pre">R0</span></code> and <code class="docutils literal notranslate"><span class="pre">R1</span></code>, consider:</p>
 126 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">key_n</span> <span class="n">value_n</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">value</span> <span class="n">key</span> <span class="n">R0</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span> <span class="n">R1</span>
 127 </pre></div>
 128 </div>
 129 <p>In this case, there are three possibilites: the key can be greater or
 130 less than or equal to the node’s key. In two of those cases we will need
 131 to apply a copy of <code class="docutils literal notranslate"><span class="pre">Tree-add</span></code>, so <code class="docutils literal notranslate"><span class="pre">R0</span></code> is pretty much out of the
 132 picture.</p>
 133 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">R0</span><span class="p">]</span> <span class="o">==</span> <span class="p">[]</span>
 134 </pre></div>
 135 </div>
 136 <section id="a-predicate-to-compare-keys">
 137 <h4>A predicate to compare keys.<a class="headerlink" href="#a-predicate-to-compare-keys" title="Permalink to this headline">¶</a></h4>
 138 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">key_n</span> <span class="n">value_n</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">value</span> <span class="n">key</span> <span class="p">[</span><span class="n">BTree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span> <span class="n">R1</span>
 139 </pre></div>
 140 </div>
 141 <p>The first thing we need to do is compare the the key we’re adding to the
 142 node key and <code class="docutils literal notranslate"><span class="pre">branch</span></code> accordingly:</p>
 143 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">key_n</span> <span class="n">value_n</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">value</span> <span class="n">key</span> <span class="p">[</span><span class="n">BTree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span> <span class="p">[</span><span class="n">P</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">E</span><span class="p">]</span> <span class="n">ifte</span>
 144 </pre></div>
 145 </div>
 146 <p>That would suggest something like:</p>
 147 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">key_n</span> <span class="n">value_n</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">value</span> <span class="n">key</span> <span class="p">[</span><span class="n">BTree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span> <span class="n">P</span>
 148 <span class="p">[</span><span class="n">key_n</span> <span class="n">value_n</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">value</span> <span class="n">key</span> <span class="p">[</span><span class="n">BTree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span> <span class="n">pop</span> <span class="n">roll</span><span class="o">&gt;</span> <span class="n">pop</span> <span class="n">first</span> <span class="o">&gt;</span>
 149 <span class="p">[</span><span class="n">key_n</span> <span class="n">value_n</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">value</span> <span class="n">key</span>                 <span class="n">roll</span><span class="o">&gt;</span> <span class="n">pop</span> <span class="n">first</span> <span class="o">&gt;</span>
 150 <span class="n">key</span> <span class="p">[</span><span class="n">key_n</span> <span class="n">value_n</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">value</span>                 <span class="n">roll</span><span class="o">&gt;</span> <span class="n">pop</span> <span class="n">first</span> <span class="o">&gt;</span>
 151 <span class="n">key</span> <span class="n">key_n</span>                                                            <span class="o">&gt;</span>
 152 <span class="n">Boolean</span>
 153 </pre></div>
 154 </div>
 155 <p>Let’s abstract the predicate just a little to let us specify the
 156 comparison operator:</p>
 157 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">P</span> <span class="o">&gt;</span> <span class="o">==</span> <span class="n">pop</span> <span class="n">roll</span><span class="o">&gt;</span> <span class="n">pop</span> <span class="n">first</span> <span class="o">&gt;</span>
 158 <span class="n">P</span> <span class="o">&lt;</span> <span class="o">==</span> <span class="n">pop</span> <span class="n">roll</span><span class="o">&gt;</span> <span class="n">pop</span> <span class="n">first</span> <span class="o">&lt;</span>
 159 <span class="n">P</span>   <span class="o">==</span> <span class="n">pop</span> <span class="n">roll</span><span class="o">&gt;</span> <span class="n">pop</span> <span class="n">first</span>
 160 </pre></div>
 161 </div>
 162 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">&#39;P == pop roll&gt; pop first&#39;</span><span class="p">)</span>
 163 </pre></div>
 164 </div>
 165 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;[&quot;old_key&quot; 23 [] []] 17 &quot;new_key&quot; [&quot;...&quot;] P&#39;</span><span class="p">)</span>
 166 </pre></div>
 167 </div>
 168 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="s1">&#39;new_key&#39;</span> <span class="s1">&#39;old_key&#39;</span>
 169 </pre></div>
 170 </div>
 171 </section>
 172 <section id="if-the-key-were-adding-is-greater-than-the-nodes-key">
 173 <h4>If the key we’re adding is greater than the node’s key.<a class="headerlink" href="#if-the-key-were-adding-is-greater-than-the-nodes-key" title="Permalink to this headline">¶</a></h4>
 174 <p>Here the parentheses are meant to signify that the expression is not
 175 literal, the code in the parentheses is meant to have been evaluated:</p>
 176 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>   <span class="p">[</span><span class="n">key_n</span> <span class="n">value_n</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">value</span> <span class="n">key</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span> <span class="n">T</span>
 177 <span class="o">-------------------------------------------------------</span>
 178    <span class="p">[</span><span class="n">key_n</span> <span class="n">value_n</span> <span class="n">left</span> <span class="p">(</span><span class="n">Tree</span><span class="o">-</span><span class="n">add</span> <span class="n">key</span> <span class="n">value</span> <span class="n">right</span><span class="p">)]</span>
 179 </pre></div>
 180 </div>
 181 <p>So how do we do this? We’re going to want to use <code class="docutils literal notranslate"><span class="pre">infra</span></code> on some
 182 function <code class="docutils literal notranslate"><span class="pre">K</span></code> that has the key and value to work with, as well as the
 183 quoted copy of <code class="docutils literal notranslate"><span class="pre">Tree-add</span></code> to apply somehow. Considering the node as a
 184 stack:</p>
 185 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>   <span class="n">right</span> <span class="n">left</span> <span class="n">value_n</span> <span class="n">key_n</span> <span class="n">value</span> <span class="n">key</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span> <span class="n">K</span>
 186 <span class="o">-----------------------------------------------------</span>
 187    <span class="n">right</span> <span class="n">value</span> <span class="n">key</span> <span class="n">Tree</span><span class="o">-</span><span class="n">add</span> <span class="n">left</span> <span class="n">value_n</span> <span class="n">key_n</span>
 188 </pre></div>
 189 </div>
 190 <p>Pretty easy:</p>
 191 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">right</span> <span class="n">left</span> <span class="n">value_n</span> <span class="n">key_n</span> <span class="n">value</span> <span class="n">key</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span> <span class="n">cons</span> <span class="n">cons</span> <span class="n">dipdd</span>
 192 <span class="n">right</span> <span class="n">left</span> <span class="n">value_n</span> <span class="n">key_n</span> <span class="p">[</span><span class="n">value</span> <span class="n">key</span> <span class="n">Tree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span>           <span class="n">dipdd</span>
 193 <span class="n">right</span> <span class="n">value</span> <span class="n">key</span> <span class="n">Tree</span><span class="o">-</span><span class="n">add</span> <span class="n">left</span> <span class="n">value_n</span> <span class="n">key_n</span>
 194 </pre></div>
 195 </div>
 196 <p>So:</p>
 197 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">K</span> <span class="o">==</span> <span class="n">cons</span> <span class="n">cons</span> <span class="n">dipdd</span>
 198 </pre></div>
 199 </div>
 200 <p>Looking at it from the point-of-view of the node as node again:</p>
 201 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">key_n</span> <span class="n">value_n</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">value</span> <span class="n">key</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span> <span class="n">K</span><span class="p">]</span> <span class="n">infra</span>
 202 </pre></div>
 203 </div>
 204 <p>Expand <code class="docutils literal notranslate"><span class="pre">K</span></code> and evaluate a little:</p>
 205 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">key_n</span> <span class="n">value_n</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">value</span> <span class="n">key</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span> <span class="n">K</span><span class="p">]</span> <span class="n">infra</span>
 206 <span class="p">[</span><span class="n">key_n</span> <span class="n">value_n</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">value</span> <span class="n">key</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span> <span class="n">cons</span> <span class="n">cons</span> <span class="n">dipdd</span><span class="p">]</span> <span class="n">infra</span>
 207 <span class="p">[</span><span class="n">key_n</span> <span class="n">value_n</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[[</span><span class="n">value</span> <span class="n">key</span> <span class="n">Tree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span>           <span class="n">dipdd</span><span class="p">]</span> <span class="n">infra</span>
 208 </pre></div>
 209 </div>
 210 <p>Then, working backwards:</p>
 211 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">key_n</span> <span class="n">value_n</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[[</span><span class="n">value</span> <span class="n">key</span> <span class="n">Tree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span>           <span class="n">dipdd</span><span class="p">]</span>      <span class="n">infra</span>
 212 <span class="p">[</span><span class="n">key_n</span> <span class="n">value_n</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">value</span> <span class="n">key</span> <span class="n">Tree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span>           <span class="p">[</span><span class="n">dipdd</span><span class="p">]</span> <span class="n">cons</span> <span class="n">infra</span>
 213 <span class="p">[</span><span class="n">key_n</span> <span class="n">value_n</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">value</span> <span class="n">key</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span> <span class="n">cons</span> <span class="n">cons</span> <span class="p">[</span><span class="n">dipdd</span><span class="p">]</span> <span class="n">cons</span> <span class="n">infra</span>
 214 </pre></div>
 215 </div>
 216 <p>And so <code class="docutils literal notranslate"><span class="pre">T</span></code> is just:</p>
 217 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">T</span> <span class="o">==</span> <span class="n">cons</span> <span class="n">cons</span> <span class="p">[</span><span class="n">dipdd</span><span class="p">]</span> <span class="n">cons</span> <span class="n">infra</span>
 218 </pre></div>
 219 </div>
 220 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">&#39;T == cons cons [dipdd] cons infra&#39;</span><span class="p">)</span>
 221 </pre></div>
 222 </div>
 223 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;[&quot;old_k&quot; &quot;old_value&quot; &quot;left&quot; &quot;right&quot;] &quot;new_value&quot; &quot;new_key&quot; [&quot;Tree-add&quot;] T&#39;</span><span class="p">)</span>
 224 </pre></div>
 225 </div>
 226 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="s1">&#39;old_k&#39;</span> <span class="s1">&#39;old_value&#39;</span> <span class="s1">&#39;left&#39;</span> <span class="s1">&#39;Tree-add&#39;</span> <span class="s1">&#39;new_key&#39;</span> <span class="s1">&#39;new_value&#39;</span> <span class="s1">&#39;right&#39;</span><span class="p">]</span>
 227 </pre></div>
 228 </div>
 229 </section>
 230 <section id="if-the-key-were-adding-is-less-than-the-nodes-key">
 231 <h4>If the key we’re adding is less than the node’s key.<a class="headerlink" href="#if-the-key-were-adding-is-less-than-the-nodes-key" title="Permalink to this headline">¶</a></h4>
 232 <p>This is very very similar to the above:</p>
 233 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">key_n</span> <span class="n">value_n</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">value</span> <span class="n">key</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span> <span class="n">E</span>
 234 <span class="p">[</span><span class="n">key_n</span> <span class="n">value_n</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">value</span> <span class="n">key</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span> <span class="p">[</span><span class="n">P</span> <span class="o">&lt;</span><span class="p">]</span> <span class="p">[</span><span class="n">Te</span><span class="p">]</span> <span class="p">[</span><span class="n">Ee</span><span class="p">]</span> <span class="n">ifte</span>
 235 </pre></div>
 236 </div>
 237 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">&#39;E == [P &lt;] [Te] [Ee] ifte&#39;</span><span class="p">)</span>
 238 </pre></div>
 239 </div>
 240 <p>In this case <code class="docutils literal notranslate"><span class="pre">Te</span></code> works that same as <code class="docutils literal notranslate"><span class="pre">T</span></code> but on the left child tree
 241 instead of the right, so the only difference is that it must use
 242 <code class="docutils literal notranslate"><span class="pre">dipd</span></code> instead of <code class="docutils literal notranslate"><span class="pre">dipdd</span></code>:</p>
 243 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">Te</span> <span class="o">==</span> <span class="n">cons</span> <span class="n">cons</span> <span class="p">[</span><span class="n">dipd</span><span class="p">]</span> <span class="n">cons</span> <span class="n">infra</span>
 244 </pre></div>
 245 </div>
 246 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">&#39;Te == cons cons [dipd] cons infra&#39;</span><span class="p">)</span>
 247 </pre></div>
 248 </div>
 249 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;[&quot;old_k&quot; &quot;old_value&quot; &quot;left&quot; &quot;right&quot;] &quot;new_value&quot; &quot;new_key&quot; [&quot;Tree-add&quot;] Te&#39;</span><span class="p">)</span>
 250 </pre></div>
 251 </div>
 252 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="s1">&#39;old_k&#39;</span> <span class="s1">&#39;old_value&#39;</span> <span class="s1">&#39;Tree-add&#39;</span> <span class="s1">&#39;new_key&#39;</span> <span class="s1">&#39;new_value&#39;</span> <span class="s1">&#39;left&#39;</span> <span class="s1">&#39;right&#39;</span><span class="p">]</span>
 253 </pre></div>
 254 </div>
 255 </section>
 256 <section id="else-the-keys-must-be-equal">
 257 <h4>Else the keys must be equal.<a class="headerlink" href="#else-the-keys-must-be-equal" title="Permalink to this headline">¶</a></h4>
 258 <p>This means we must find:</p>
 259 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>   <span class="p">[</span><span class="n">key</span> <span class="n">old_value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">new_value</span> <span class="n">key</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span> <span class="n">Ee</span>
 260 <span class="o">------------------------------------------------------------</span>
 261    <span class="p">[</span><span class="n">key</span> <span class="n">new_value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span>
 262 </pre></div>
 263 </div>
 264 <p>This is another easy one:</p>
 265 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">Ee</span> <span class="o">==</span> <span class="n">pop</span> <span class="n">swap</span> <span class="n">roll</span><span class="o">&lt;</span> <span class="n">rest</span> <span class="n">rest</span> <span class="n">cons</span> <span class="n">cons</span>
 266 </pre></div>
 267 </div>
 268 <p>Example:</p>
 269 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">key</span> <span class="n">old_value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">new_value</span> <span class="n">key</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span> <span class="n">pop</span> <span class="n">swap</span> <span class="n">roll</span><span class="o">&lt;</span> <span class="n">rest</span> <span class="n">rest</span> <span class="n">cons</span> <span class="n">cons</span>
 270 <span class="p">[</span><span class="n">key</span> <span class="n">old_value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">new_value</span> <span class="n">key</span>                <span class="n">swap</span> <span class="n">roll</span><span class="o">&lt;</span> <span class="n">rest</span> <span class="n">rest</span> <span class="n">cons</span> <span class="n">cons</span>
 271 <span class="p">[</span><span class="n">key</span> <span class="n">old_value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">key</span> <span class="n">new_value</span>                     <span class="n">roll</span><span class="o">&lt;</span> <span class="n">rest</span> <span class="n">rest</span> <span class="n">cons</span> <span class="n">cons</span>
 272 <span class="n">key</span> <span class="n">new_value</span> <span class="p">[</span><span class="n">key</span> <span class="n">old_value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span>                           <span class="n">rest</span> <span class="n">rest</span> <span class="n">cons</span> <span class="n">cons</span>
 273 <span class="n">key</span> <span class="n">new_value</span> <span class="p">[</span>              <span class="n">left</span> <span class="n">right</span><span class="p">]</span>                                     <span class="n">cons</span> <span class="n">cons</span>
 274               <span class="p">[</span><span class="n">key</span> <span class="n">new_value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span>
 275 </pre></div>
 276 </div>
 277 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">&#39;Ee == pop swap roll&lt; rest rest cons cons&#39;</span><span class="p">)</span>
 278 </pre></div>
 279 </div>
 280 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;[&quot;k&quot; &quot;old_value&quot; &quot;left&quot; &quot;right&quot;] &quot;new_value&quot; &quot;k&quot; [&quot;Tree-add&quot;] Ee&#39;</span><span class="p">)</span>
 281 </pre></div>
 282 </div>
 283 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="s1">&#39;k&#39;</span> <span class="s1">&#39;new_value&#39;</span> <span class="s1">&#39;left&#39;</span> <span class="s1">&#39;right&#39;</span><span class="p">]</span>
 284 </pre></div>
 285 </div>
 286 </section>
 287 </section>
 288 <section id="now-we-can-define-tree-add">
 289 <h3>Now we can define <code class="docutils literal notranslate"><span class="pre">Tree-add</span></code><a class="headerlink" href="#now-we-can-define-tree-add" title="Permalink to this headline">¶</a></h3>
 290 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">Tree</span><span class="o">-</span><span class="n">add</span> <span class="o">==</span> <span class="p">[</span><span class="n">popop</span> <span class="ow">not</span><span class="p">]</span> <span class="p">[[</span><span class="n">pop</span><span class="p">]</span> <span class="n">dipd</span> <span class="n">Tree</span><span class="o">-</span><span class="n">new</span><span class="p">]</span> <span class="p">[]</span> <span class="p">[[</span><span class="n">P</span> <span class="o">&gt;</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">E</span><span class="p">]</span> <span class="n">ifte</span><span class="p">]</span> <span class="n">genrec</span>
 291 </pre></div>
 292 </div>
 293 <p>Putting it all together:</p>
 294 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">Tree</span><span class="o">-</span><span class="n">new</span> <span class="o">==</span> <span class="n">swap</span> <span class="p">[[]</span> <span class="p">[]]</span> <span class="n">cons</span> <span class="n">cons</span>
 295 <span class="n">P</span> <span class="o">==</span> <span class="n">pop</span> <span class="n">roll</span><span class="o">&gt;</span> <span class="n">pop</span> <span class="n">first</span>
 296 <span class="n">T</span> <span class="o">==</span> <span class="n">cons</span> <span class="n">cons</span> <span class="p">[</span><span class="n">dipdd</span><span class="p">]</span> <span class="n">cons</span> <span class="n">infra</span>
 297 <span class="n">Te</span> <span class="o">==</span> <span class="n">cons</span> <span class="n">cons</span> <span class="p">[</span><span class="n">dipd</span><span class="p">]</span> <span class="n">cons</span> <span class="n">infra</span>
 298 <span class="n">Ee</span> <span class="o">==</span> <span class="n">pop</span> <span class="n">swap</span> <span class="n">roll</span><span class="o">&lt;</span> <span class="n">rest</span> <span class="n">rest</span> <span class="n">cons</span> <span class="n">cons</span>
 299 <span class="n">E</span> <span class="o">==</span> <span class="p">[</span><span class="n">P</span> <span class="o">&lt;</span><span class="p">]</span> <span class="p">[</span><span class="n">Te</span><span class="p">]</span> <span class="p">[</span><span class="n">Ee</span><span class="p">]</span> <span class="n">ifte</span>
 300 <span class="n">R</span> <span class="o">==</span> <span class="p">[</span><span class="n">P</span> <span class="o">&gt;</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">E</span><span class="p">]</span> <span class="n">ifte</span>
 301
 302 <span class="n">Tree</span><span class="o">-</span><span class="n">add</span> <span class="o">==</span> <span class="p">[</span><span class="n">popop</span> <span class="ow">not</span><span class="p">]</span> <span class="p">[[</span><span class="n">pop</span><span class="p">]</span> <span class="n">dipd</span> <span class="n">Tree</span><span class="o">-</span><span class="n">new</span><span class="p">]</span> <span class="p">[]</span> <span class="p">[</span><span class="n">R</span><span class="p">]</span> <span class="n">genrec</span>
 303 </pre></div>
 304 </div>
 305 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">&#39;Tree-add == [popop not] [[pop] dipd Tree-new] [] [[P &gt;] [T] [E] ifte] genrec&#39;</span><span class="p">)</span>
 306 </pre></div>
 307 </div>
 308 </section>
 309 <section id="examples">
 310 <h3>Examples<a class="headerlink" href="#examples" title="Permalink to this headline">¶</a></h3>
 311 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;[] 23 &quot;b&quot; Tree-add&#39;</span><span class="p">)</span>  <span class="c1"># Initial</span>
 312 </pre></div>
 313 </div>
 314 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="s1">&#39;b&#39;</span> <span class="mi">23</span> <span class="p">[]</span> <span class="p">[]]</span>
 315 </pre></div>
 316 </div>
 317 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;[&quot;b&quot; 23 [] []] 88 &quot;c&quot; Tree-add&#39;</span><span class="p">)</span>  <span class="c1"># Greater than</span>
 318 </pre></div>
 319 </div>
 320 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="s1">&#39;b&#39;</span> <span class="mi">23</span> <span class="p">[]</span> <span class="p">[</span><span class="s1">&#39;c&#39;</span> <span class="mi">88</span> <span class="p">[]</span> <span class="p">[]]]</span>
 321 </pre></div>
 322 </div>
 323 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;[&quot;b&quot; 23 [] []] 88 &quot;a&quot; Tree-add&#39;</span><span class="p">)</span>  <span class="c1"># Less than</span>
 324 </pre></div>
 325 </div>
 326 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="s1">&#39;b&#39;</span> <span class="mi">23</span> <span class="p">[</span><span class="s1">&#39;a&#39;</span> <span class="mi">88</span> <span class="p">[]</span> <span class="p">[]]</span> <span class="p">[]]</span>
 327 </pre></div>
 328 </div>
 329 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;[&quot;b&quot; 23 [] []] 88 &quot;b&quot; Tree-add&#39;</span><span class="p">)</span>  <span class="c1"># Equal to</span>
 330 </pre></div>
 331 </div>
 332 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="s1">&#39;b&#39;</span> <span class="mi">88</span> <span class="p">[]</span> <span class="p">[]]</span>
 333 </pre></div>
 334 </div>
 335 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;[] 23 &quot;b&quot; Tree-add 88 &quot;a&quot; Tree-add 44 &quot;c&quot; Tree-add&#39;</span><span class="p">)</span>  <span class="c1"># Series.</span>
 336 </pre></div>
 337 </div>
 338 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="s1">&#39;b&#39;</span> <span class="mi">23</span> <span class="p">[</span><span class="s1">&#39;a&#39;</span> <span class="mi">88</span> <span class="p">[]</span> <span class="p">[]]</span> <span class="p">[</span><span class="s1">&#39;c&#39;</span> <span class="mi">44</span> <span class="p">[]</span> <span class="p">[]]]</span>
 339 </pre></div>
 340 </div>
 341 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;[] [[23 &quot;b&quot;] [88 &quot;a&quot;] [44 &quot;c&quot;]] [i Tree-add] step&#39;</span><span class="p">)</span>
 342 </pre></div>
 343 </div>
 344 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="s1">&#39;b&#39;</span> <span class="mi">23</span> <span class="p">[</span><span class="s1">&#39;a&#39;</span> <span class="mi">88</span> <span class="p">[]</span> <span class="p">[]]</span> <span class="p">[</span><span class="s1">&#39;c&#39;</span> <span class="mi">44</span> <span class="p">[]</span> <span class="p">[]]]</span>
 345 </pre></div>
 346 </div>
 347 </section>
 348 </section>
 349 <section id="interlude-cmp-combinator">
 350 <h2>Interlude: <code class="docutils literal notranslate"><span class="pre">cmp</span></code> combinator<a class="headerlink" href="#interlude-cmp-combinator" title="Permalink to this headline">¶</a></h2>
 351 <p>Instead of mucking about with nested <code class="docutils literal notranslate"><span class="pre">ifte</span></code> combinators let’s use
 352 <code class="docutils literal notranslate"><span class="pre">cmp</span></code> which takes two values and three quoted programs on the stack
 353 and runs one of the three depending on the results of comparing the two
 354 values:</p>
 355 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>   <span class="n">a</span> <span class="n">b</span> <span class="p">[</span><span class="n">G</span><span class="p">]</span> <span class="p">[</span><span class="n">E</span><span class="p">]</span> <span class="p">[</span><span class="n">L</span><span class="p">]</span> <span class="n">cmp</span>
 356 <span class="o">-------------------------</span> <span class="n">a</span> <span class="o">&gt;</span> <span class="n">b</span>
 357         <span class="n">G</span>
 358
 359    <span class="n">a</span> <span class="n">b</span> <span class="p">[</span><span class="n">G</span><span class="p">]</span> <span class="p">[</span><span class="n">E</span><span class="p">]</span> <span class="p">[</span><span class="n">L</span><span class="p">]</span> <span class="n">cmp</span>
 360 <span class="o">-------------------------</span> <span class="n">a</span> <span class="o">=</span> <span class="n">b</span>
 361             <span class="n">E</span>
 362
 363    <span class="n">a</span> <span class="n">b</span> <span class="p">[</span><span class="n">G</span><span class="p">]</span> <span class="p">[</span><span class="n">E</span><span class="p">]</span> <span class="p">[</span><span class="n">L</span><span class="p">]</span> <span class="n">cmp</span>
 364 <span class="o">-------------------------</span> <span class="n">a</span> <span class="o">&lt;</span> <span class="n">b</span>
 365                 <span class="n">L</span>
 366 </pre></div>
 367 </div>
 368 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s2">&quot;1 0 [&#39;G&#39;] [&#39;E&#39;] [&#39;L&#39;] cmp&quot;</span><span class="p">)</span>
 369 </pre></div>
 370 </div>
 371 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="s1">&#39;G&#39;</span>
 372 </pre></div>
 373 </div>
 374 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s2">&quot;1 1 [&#39;G&#39;] [&#39;E&#39;] [&#39;L&#39;] cmp&quot;</span><span class="p">)</span>
 375 </pre></div>
 376 </div>
 377 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="s1">&#39;E&#39;</span>
 378 </pre></div>
 379 </div>
 380 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s2">&quot;0 1 [&#39;G&#39;] [&#39;E&#39;] [&#39;L&#39;] cmp&quot;</span><span class="p">)</span>
 381 </pre></div>
 382 </div>
 383 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="s1">&#39;L&#39;</span>
 384 </pre></div>
 385 </div>
 386 <section id="redefine-tree-add">
 387 <h3>Redefine <code class="docutils literal notranslate"><span class="pre">Tree-add</span></code><a class="headerlink" href="#redefine-tree-add" title="Permalink to this headline">¶</a></h3>
 388 <p>We need a new non-destructive predicate <code class="docutils literal notranslate"><span class="pre">P</span></code>:</p>
 389 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>   <span class="p">[</span><span class="n">node_key</span> <span class="n">node_value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">value</span> <span class="n">key</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span> <span class="n">P</span>
 390 <span class="o">------------------------------------------------------------------------</span>
 391    <span class="p">[</span><span class="n">node_key</span> <span class="n">node_value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">value</span> <span class="n">key</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span> <span class="n">key</span> <span class="n">node_key</span>
 392 </pre></div>
 393 </div>
 394 <p>Let’s start with <code class="docutils literal notranslate"><span class="pre">over</span></code> to get a copy of the key and then apply some
 395 function <code class="docutils literal notranslate"><span class="pre">Q</span></code> with the <code class="docutils literal notranslate"><span class="pre">nullary</span></code> combinator so it can dig out the
 396 node key (by throwing everything else away):</p>
 397 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">P</span> <span class="o">==</span> <span class="n">over</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="n">nullary</span>
 398
 399 <span class="p">[</span><span class="n">node_key</span> <span class="n">node_value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">value</span> <span class="n">key</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span> <span class="n">over</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="n">nullary</span>
 400 <span class="p">[</span><span class="n">node_key</span> <span class="n">node_value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">value</span> <span class="n">key</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span> <span class="n">key</span>  <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="n">nullary</span>
 401 </pre></div>
 402 </div>
 403 <p>And <code class="docutils literal notranslate"><span class="pre">Q</span></code> would be:</p>
 404 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">Q</span> <span class="o">==</span> <span class="n">popop</span> <span class="n">popop</span> <span class="n">first</span>
 405
 406 <span class="p">[</span><span class="n">node_key</span> <span class="n">node_value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">value</span> <span class="n">key</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span> <span class="n">key</span> <span class="n">Q</span>
 407 <span class="p">[</span><span class="n">node_key</span> <span class="n">node_value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">value</span> <span class="n">key</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span> <span class="n">key</span> <span class="n">popop</span> <span class="n">popop</span> <span class="n">first</span>
 408 <span class="p">[</span><span class="n">node_key</span> <span class="n">node_value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">value</span> <span class="n">key</span>                      <span class="n">popop</span> <span class="n">first</span>
 409 <span class="p">[</span><span class="n">node_key</span> <span class="n">node_value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span>                                      <span class="n">first</span>
 410  <span class="n">node_key</span>
 411 </pre></div>
 412 </div>
 413 <p>Or just:</p>
 414 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">P</span> <span class="o">==</span> <span class="n">over</span> <span class="p">[</span><span class="n">popop</span> <span class="n">popop</span> <span class="n">first</span><span class="p">]</span> <span class="n">nullary</span>
 415 </pre></div>
 416 </div>
 417 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">&#39;P == over [popop popop first] nullary&#39;</span><span class="p">)</span>
 418 </pre></div>
 419 </div>
 420 <p>Using <code class="docutils literal notranslate"><span class="pre">cmp</span></code> to simplify <cite>our code above at
 421 ``R1`</cite> &lt;#Adding-to-a-non-empty-node.&gt;`__:</p>
 422 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">node_key</span> <span class="n">node_value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">value</span> <span class="n">key</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span> <span class="n">R1</span>
 423 <span class="p">[</span><span class="n">node_key</span> <span class="n">node_value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">value</span> <span class="n">key</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span> <span class="n">P</span> <span class="p">[</span><span class="n">T</span><span class="p">]</span> <span class="p">[</span><span class="n">E</span><span class="p">]</span> <span class="p">[</span><span class="n">Te</span><span class="p">]</span> <span class="n">cmp</span>
 424 </pre></div>
 425 </div>
 426 <p>The line above becomes one of the three lines below:</p>
 427 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">node_key</span> <span class="n">node_value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">value</span> <span class="n">key</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span> <span class="n">T</span>
 428 <span class="p">[</span><span class="n">node_key</span> <span class="n">node_value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">value</span> <span class="n">key</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span> <span class="n">E</span>
 429 <span class="p">[</span><span class="n">node_key</span> <span class="n">node_value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">value</span> <span class="n">key</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="n">add</span><span class="p">]</span> <span class="n">Te</span>
 430 </pre></div>
 431 </div>
 432 <p>The definition is a little longer but, I think, more elegant and easier
 433 to understand:</p>
 434 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">Tree</span><span class="o">-</span><span class="n">add</span> <span class="o">==</span> <span class="p">[</span><span class="n">popop</span> <span class="ow">not</span><span class="p">]</span> <span class="p">[[</span><span class="n">pop</span><span class="p">]</span> <span class="n">dipd</span> <span class="n">Tree</span><span class="o">-</span><span class="n">new</span><span class="p">]</span> <span class="p">[]</span> <span class="p">[</span><span class="n">P</span> <span class="p">[</span><span class="n">T</span><span class="p">]</span> <span class="p">[</span><span class="n">Ee</span><span class="p">]</span> <span class="p">[</span><span class="n">Te</span><span class="p">]</span> <span class="n">cmp</span><span class="p">]</span> <span class="n">genrec</span>
 435 </pre></div>
 436 </div>
 437 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">&#39;Tree-add == [popop not] [[pop] dipd Tree-new] [] [P [T] [Ee] [Te] cmp] genrec&#39;</span><span class="p">)</span>
 438 </pre></div>
 439 </div>
 440 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;[] 23 &quot;b&quot; Tree-add 88 &quot;a&quot; Tree-add 44 &quot;c&quot; Tree-add&#39;</span><span class="p">)</span>  <span class="c1"># Still works.</span>
 441 </pre></div>
 442 </div>
 443 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="s1">&#39;b&#39;</span> <span class="mi">23</span> <span class="p">[</span><span class="s1">&#39;a&#39;</span> <span class="mi">88</span> <span class="p">[]</span> <span class="p">[]]</span> <span class="p">[</span><span class="s1">&#39;c&#39;</span> <span class="mi">44</span> <span class="p">[]</span> <span class="p">[]]]</span>
 444 </pre></div>
 445 </div>
 446 </section>
 447 </section>
 448 <section id="a-function-to-traverse-this-structure">
 449 <h2>A Function to Traverse this Structure<a class="headerlink" href="#a-function-to-traverse-this-structure" title="Permalink to this headline">¶</a></h2>
 450 <p>Let’s take a crack at writing a function that can recursively iterate or
 451 traverse these trees.</p>
 452 <section id="base-case">
 453 <h3>Base case <code class="docutils literal notranslate"><span class="pre">[]</span></code><a class="headerlink" href="#base-case" title="Permalink to this headline">¶</a></h3>
 454 <p>The stopping predicate just has to detect the empty list:</p>
 455 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</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">E</span><span class="p">]</span> <span class="p">[</span><span class="n">R0</span><span class="p">]</span> <span class="p">[</span><span class="n">R1</span><span class="p">]</span> <span class="n">genrec</span>
 456 </pre></div>
 457 </div>
 458 <p>And since there’s nothing at this node, we just <code class="docutils literal notranslate"><span class="pre">pop</span></code> it:</p>
 459 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</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="p">]</span> <span class="p">[</span><span class="n">R0</span><span class="p">]</span> <span class="p">[</span><span class="n">R1</span><span class="p">]</span> <span class="n">genrec</span>
 460 </pre></div>
 461 </div>
 462 </section>
 463 <section id="node-case-key-value-left-right">
 464 <h3>Node case <code class="docutils literal notranslate"><span class="pre">[key</span> <span class="pre">value</span> <span class="pre">left</span> <span class="pre">right]</span></code><a class="headerlink" href="#node-case-key-value-left-right" title="Permalink to this headline">¶</a></h3>
 465 <p>Now we need to figure out <code class="docutils literal notranslate"><span class="pre">R0</span></code> and <code class="docutils literal notranslate"><span class="pre">R1</span></code>:</p>
 466 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</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="p">]</span> <span class="p">[</span><span class="n">R0</span><span class="p">]</span>           <span class="p">[</span><span class="n">R1</span><span class="p">]</span> <span class="n">genrec</span>
 467           <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="p">]</span> <span class="p">[</span><span class="n">R0</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="p">]</span> <span class="n">R1</span><span class="p">]</span> <span class="n">ifte</span>
 468 </pre></div>
 469 </div>
 470 <p>Let’s look at it <em>in situ</em>:</p>
 471 <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="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">R0</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="p">]</span> <span class="n">R1</span>
 472 </pre></div>
 473 </div>
 474 <section id="processing-the-current-node">
 475 <h4>Processing the current node.<a class="headerlink" href="#processing-the-current-node" title="Permalink to this headline">¶</a></h4>
 476 <p><code class="docutils literal notranslate"><span class="pre">R0</span></code> is almost certainly going to use <code class="docutils literal notranslate"><span class="pre">dup</span></code> to make a copy of the
 477 node and then <code class="docutils literal notranslate"><span class="pre">dip</span></code> on some function to process the copy with it:</p>
 478 <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="n">left</span> <span class="n">right</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="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="p">]</span> <span class="n">R1</span>
 479 <span class="p">[</span><span class="n">key</span> <span class="n">value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span>  <span class="n">F</span>  <span class="p">[</span><span class="n">key</span> <span class="n">value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="p">]</span> <span class="n">R1</span>
 480 </pre></div>
 481 </div>
 482 <p>For example, if we’re getting all the keys <code class="docutils literal notranslate"><span class="pre">F</span></code> would be <code class="docutils literal notranslate"><span class="pre">first</span></code>:</p>
 483 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">R0</span> <span class="o">==</span> <span class="p">[</span><span class="n">first</span><span class="p">]</span> <span class="n">dupdip</span>
 484
 485 <span class="p">[</span><span class="n">key</span> <span class="n">value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">first</span><span class="p">]</span> <span class="n">dupdip</span>                 <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="p">]</span> <span class="n">R1</span>
 486 <span class="p">[</span><span class="n">key</span> <span class="n">value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span>  <span class="n">first</span>  <span class="p">[</span><span class="n">key</span> <span class="n">value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="p">]</span> <span class="n">R1</span>
 487 <span class="n">key</span>                            <span class="p">[</span><span class="n">key</span> <span class="n">value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="p">]</span> <span class="n">R1</span>
 488 </pre></div>
 489 </div>
 490 </section>
 491 <section id="recur">
 492 <h4>Recur<a class="headerlink" href="#recur" title="Permalink to this headline">¶</a></h4>
 493 <p>Now <code class="docutils literal notranslate"><span class="pre">R1</span></code> needs to apply <code class="docutils literal notranslate"><span class="pre">[Tree-iter]</span></code> to <code class="docutils literal notranslate"><span class="pre">left</span></code> and <code class="docutils literal notranslate"><span class="pre">right</span></code>. If
 494 we drop the key and value from the node using <code class="docutils literal notranslate"><span class="pre">rest</span></code> twice we are left
 495 with an interesting situation:</p>
 496 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">key</span> <span class="p">[</span><span class="n">key</span> <span class="n">value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="p">]</span> <span class="n">R1</span>
 497 <span class="n">key</span> <span class="p">[</span><span class="n">key</span> <span class="n">value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="p">]</span> <span class="p">[</span><span class="n">rest</span> <span class="n">rest</span><span class="p">]</span> <span class="n">dip</span>
 498 <span class="n">key</span> <span class="p">[</span><span class="n">key</span> <span class="n">value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">rest</span> <span class="n">rest</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="p">]</span>
 499 <span class="n">key</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">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="p">]</span>
 500 </pre></div>
 501 </div>
 502 <p>Hmm, will <code class="docutils literal notranslate"><span class="pre">step</span></code> do?</p>
 503 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">key</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">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="p">]</span> <span class="n">step</span>
 504 <span class="n">key</span> <span class="n">left</span> <span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span> <span class="p">[</span><span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="p">]</span> <span class="n">step</span>
 505 <span class="n">key</span> <span class="n">left</span><span class="o">-</span><span class="n">keys</span> <span class="p">[</span><span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="p">]</span> <span class="n">step</span>
 506 <span class="n">key</span> <span class="n">left</span><span class="o">-</span><span class="n">keys</span> <span class="n">right</span> <span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span>
 507 <span class="n">key</span> <span class="n">left</span><span class="o">-</span><span class="n">keys</span> <span class="n">right</span><span class="o">-</span><span class="n">keys</span>
 508 </pre></div>
 509 </div>
 510 <p>Neat. So:</p>
 511 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">R1</span> <span class="o">==</span> <span class="p">[</span><span class="n">rest</span> <span class="n">rest</span><span class="p">]</span> <span class="n">dip</span> <span class="n">step</span>
 512 </pre></div>
 513 </div>
 514 </section>
 515 </section>
 516 <section id="putting-it-together">
 517 <h3>Putting it together<a class="headerlink" href="#putting-it-together" title="Permalink to this headline">¶</a></h3>
 518 <p>We have:</p>
 519 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</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="p">]</span> <span class="p">[[</span><span class="n">F</span><span class="p">]</span> <span class="n">dupdip</span><span class="p">]</span> <span class="p">[[</span><span class="n">rest</span> <span class="n">rest</span><span class="p">]</span> <span class="n">dip</span> <span class="n">step</span><span class="p">]</span> <span class="n">genrec</span>
 520 </pre></div>
 521 </div>
 522 <p>When I was reading this over I realized <code class="docutils literal notranslate"><span class="pre">rest</span> <span class="pre">rest</span></code> could go in
 523 <code class="docutils literal notranslate"><span class="pre">R0</span></code>:</p>
 524 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</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="p">]</span> <span class="p">[[</span><span class="n">F</span><span class="p">]</span> <span class="n">dupdip</span> <span class="n">rest</span> <span class="n">rest</span><span class="p">]</span> <span class="p">[</span><span class="n">step</span><span class="p">]</span> <span class="n">genrec</span>
 525 </pre></div>
 526 </div>
 527 <p>(And <code class="docutils literal notranslate"><span class="pre">[step]</span> <span class="pre">genrec</span></code> is such a cool and suggestive combinator!)</p>
 528 </section>
 529 <section id="parameterizing-the-f-per-node-processing-function">
 530 <h3>Parameterizing the <code class="docutils literal notranslate"><span class="pre">F</span></code> per-node processing function.<a class="headerlink" href="#parameterizing-the-f-per-node-processing-function" title="Permalink to this headline">¶</a></h3>
 531 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>                <span class="p">[</span><span class="n">F</span><span class="p">]</span> <span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span>
 532 <span class="o">------------------------------------------------------</span>
 533    <span class="p">[</span><span class="ow">not</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">rest</span> <span class="n">rest</span><span class="p">]</span> <span class="p">[</span><span class="n">step</span><span class="p">]</span> <span class="n">genrec</span>
 534 </pre></div>
 535 </div>
 536 <p>Working backward:</p>
 537 <div class="highlight-default notranslate"><div class="highlight"><pre><span></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="p">]</span> <span class="p">[[</span><span class="n">F</span><span class="p">]</span> <span class="n">dupdip</span> <span class="n">rest</span> <span class="n">rest</span><span class="p">]</span>            <span class="p">[</span><span class="n">step</span><span class="p">]</span> <span class="n">genrec</span>
 538 <span class="p">[</span><span class="ow">not</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="p">[</span><span class="n">dupdip</span> <span class="n">rest</span> <span class="n">rest</span><span class="p">]</span> <span class="n">cons</span> <span class="p">[</span><span class="n">step</span><span class="p">]</span> <span class="n">genrec</span>
 539 <span class="p">[</span><span class="n">F</span><span class="p">]</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="p">]</span> <span class="n">roll</span><span class="o">&lt;</span> <span class="p">[</span><span class="n">dupdip</span> <span class="n">rest</span> <span class="n">rest</span><span class="p">]</span> <span class="n">cons</span> <span class="p">[</span><span class="n">step</span><span class="p">]</span> <span class="n">genrec</span>
 540 </pre></div>
 541 </div>
 542 </section>
 543 <section id="tree-iter">
 544 <h3><code class="docutils literal notranslate"><span class="pre">Tree-iter</span></code><a class="headerlink" href="#tree-iter" title="Permalink to this headline">¶</a></h3>
 545 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</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="p">]</span> <span class="n">roll</span><span class="o">&lt;</span> <span class="p">[</span><span class="n">dupdip</span> <span class="n">rest</span> <span class="n">rest</span><span class="p">]</span> <span class="n">cons</span> <span class="p">[</span><span class="n">step</span><span class="p">]</span> <span class="n">genrec</span>
 546 </pre></div>
 547 </div>
 548 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">&#39;Tree-iter == [not] [pop] roll&lt; [dupdip rest rest] cons [step] genrec&#39;</span><span class="p">)</span>
 549 </pre></div>
 550 </div>
 551 </section>
 552 <section id="id1">
 553 <h3>Examples<a class="headerlink" href="#id1" title="Permalink to this headline">¶</a></h3>
 554 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;[] [foo] Tree-iter&#39;</span><span class="p">)</span>  <span class="c1">#  It doesn&#39;t matter what F is as it won&#39;t be used.</span>
 555 </pre></div>
 556 </div>
 557 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s2">&quot;[&#39;b&#39; 23 [&#39;a&#39; 88 [] []] [&#39;c&#39; 44 [] []]] [first] Tree-iter&quot;</span><span class="p">)</span>
 558 </pre></div>
 559 </div>
 560 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="s1">&#39;b&#39;</span> <span class="s1">&#39;a&#39;</span> <span class="s1">&#39;c&#39;</span>
 561 </pre></div>
 562 </div>
 563 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s2">&quot;[&#39;b&#39; 23 [&#39;a&#39; 88 [] []] [&#39;c&#39; 44 [] []]] [second] Tree-iter&quot;</span><span class="p">)</span>
 564 </pre></div>
 565 </div>
 566 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">23</span> <span class="mi">88</span> <span class="mi">44</span>
 567 </pre></div>
 568 </div>
 569 </section>
 570 </section>
 571 <section id="interlude-a-set-like-datastructure">
 572 <h2>Interlude: A Set-like Datastructure<a class="headerlink" href="#interlude-a-set-like-datastructure" title="Permalink to this headline">¶</a></h2>
 573 <p>We can use this to make a set-like datastructure by just setting values
 574 to e.g. 0 and ignoring them. It’s set-like in that duplicate items added
 575 to it will only occur once within it, and we can query it in
 576 <cite>:math:`O(log_2 N)</cite> &lt;<a class="reference external" href="https://en.wikipedia.org/wiki/Binary_search_tree#cite_note-2">https://en.wikipedia.org/wiki/Binary_search_tree#cite_note-2</a>&gt;`__
 577 time.</p>
 578 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;[] [3 9 5 2 8 6 7 8 4] [0 swap Tree-add] step&#39;</span><span class="p">)</span>
 579 </pre></div>
 580 </div>
 581 <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="mi">2</span> <span class="mi">0</span> <span class="p">[]</span> <span class="p">[]]</span> <span class="p">[</span><span class="mi">9</span> <span class="mi">0</span> <span class="p">[</span><span class="mi">5</span> <span class="mi">0</span> <span class="p">[</span><span class="mi">4</span> <span class="mi">0</span> <span class="p">[]</span> <span class="p">[]]</span> <span class="p">[</span><span class="mi">8</span> <span class="mi">0</span> <span class="p">[</span><span class="mi">6</span> <span class="mi">0</span> <span class="p">[]</span> <span class="p">[</span><span class="mi">7</span> <span class="mi">0</span> <span class="p">[]</span> <span class="p">[]]]</span> <span class="p">[]]]</span> <span class="p">[]]]</span>
 582 </pre></div>
 583 </div>
 584 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">&#39;to_set == [] swap [0 swap Tree-add] step&#39;</span><span class="p">)</span>
 585 </pre></div>
 586 </div>
 587 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;[3 9 5 2 8 6 7 8 4] to_set&#39;</span><span class="p">)</span>
 588 </pre></div>
 589 </div>
 590 <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="mi">2</span> <span class="mi">0</span> <span class="p">[]</span> <span class="p">[]]</span> <span class="p">[</span><span class="mi">9</span> <span class="mi">0</span> <span class="p">[</span><span class="mi">5</span> <span class="mi">0</span> <span class="p">[</span><span class="mi">4</span> <span class="mi">0</span> <span class="p">[]</span> <span class="p">[]]</span> <span class="p">[</span><span class="mi">8</span> <span class="mi">0</span> <span class="p">[</span><span class="mi">6</span> <span class="mi">0</span> <span class="p">[]</span> <span class="p">[</span><span class="mi">7</span> <span class="mi">0</span> <span class="p">[]</span> <span class="p">[]]]</span> <span class="p">[]]]</span> <span class="p">[]]]</span>
 591 </pre></div>
 592 </div>
 593 <p>And with that we can write a little program <code class="docutils literal notranslate"><span class="pre">unique</span></code> to remove
 594 duplicate items from a list.</p>
 595 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">define</span><span class="p">(</span><span class="s1">&#39;unique == [to_set [first] Tree-iter] cons run&#39;</span><span class="p">)</span>
 596 </pre></div>
 597 </div>
 598 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;[3 9 3 5 2 9 8 8 8 6 2 7 8 4 3] unique&#39;</span><span class="p">)</span>  <span class="c1"># Filter duplicate items.</span>
 599 </pre></div>
 600 </div>
 601 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="mi">7</span> <span class="mi">6</span> <span class="mi">8</span> <span class="mi">4</span> <span class="mi">5</span> <span class="mi">9</span> <span class="mi">2</span> <span class="mi">3</span><span class="p">]</span>
 602 </pre></div>
 603 </div>
 604 </section>
 605 <section id="a-version-of-tree-iter-that-does-in-order-traversal">
 606 <h2>A Version of <code class="docutils literal notranslate"><span class="pre">Tree-iter</span></code> that does In-Order Traversal<a class="headerlink" href="#a-version-of-tree-iter-that-does-in-order-traversal" title="Permalink to this headline">¶</a></h2>
 607 <p>If you look back to the <cite>non-empty case of the ``Tree-iter`</cite>
 608 function &lt;#Node-case-%5Bkey-value-left-right%5D&gt;`__ we can design a
 609 variant that first processes the left child, then the current node, then
 610 the right child. This will allow us to traverse the tree in sort order.</p>
 611 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</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="p">]</span> <span class="p">[</span><span class="n">R0</span><span class="p">]</span> <span class="p">[</span><span class="n">R1</span><span class="p">]</span> <span class="n">genrec</span>
 612 </pre></div>
 613 </div>
 614 <p>To define <code class="docutils literal notranslate"><span class="pre">R0</span></code> and <code class="docutils literal notranslate"><span class="pre">R1</span></code> it helps to look at them as they will appear
 615 when they run:</p>
 616 <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="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">R0</span> <span class="p">[</span><span class="n">BTree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</span><span class="p">]</span> <span class="n">R1</span>
 617 </pre></div>
 618 </div>
 619 <section id="process-the-left-child">
 620 <h3>Process the left child.<a class="headerlink" href="#process-the-left-child" title="Permalink to this headline">¶</a></h3>
 621 <p>Staring at this for a bit suggests <code class="docutils literal notranslate"><span class="pre">dup</span> <span class="pre">third</span></code> to start:</p>
 622 <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="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">R0</span>        <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</span><span class="p">]</span> <span class="n">R1</span>
 623 <span class="p">[</span><span class="n">key</span> <span class="n">value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">dup</span> <span class="n">third</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</span><span class="p">]</span> <span class="n">R1</span>
 624 <span class="p">[</span><span class="n">key</span> <span class="n">value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">left</span>      <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</span><span class="p">]</span> <span class="n">R1</span>
 625 </pre></div>
 626 </div>
 627 <p>Now maybe:</p>
 628 <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="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">left</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</span><span class="p">]</span> <span class="p">[</span><span class="n">cons</span> <span class="n">dip</span><span class="p">]</span> <span class="n">dupdip</span>
 629 <span class="p">[</span><span class="n">key</span> <span class="n">value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">left</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</span><span class="p">]</span>  <span class="n">cons</span> <span class="n">dip</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</span><span class="p">]</span>
 630 <span class="p">[</span><span class="n">key</span> <span class="n">value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">left</span> <span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</span><span class="p">]</span>       <span class="n">dip</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</span><span class="p">]</span>
 631 <span class="n">left</span> <span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</span> <span class="p">[</span><span class="n">key</span> <span class="n">value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span>             <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</span><span class="p">]</span>
 632 </pre></div>
 633 </div>
 634 </section>
 635 <section id="process-the-current-node">
 636 <h3>Process the current node.<a class="headerlink" href="#process-the-current-node" title="Permalink to this headline">¶</a></h3>
 637 <p>So far, so good. Now we need to process the current node’s values:</p>
 638 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">left</span> <span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</span> <span class="p">[</span><span class="n">key</span> <span class="n">value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</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="p">]</span> <span class="n">dip</span>
 639 <span class="n">left</span> <span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</span> <span class="p">[</span><span class="n">key</span> <span class="n">value</span> <span class="n">left</span> <span class="n">right</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="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</span><span class="p">]</span>
 640 <span class="n">left</span> <span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</span> <span class="p">[</span><span class="n">key</span> <span class="n">value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">F</span> <span class="p">[</span><span class="n">key</span> <span class="n">value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</span><span class="p">]</span>
 641 </pre></div>
 642 </div>
 643 <p>If <code class="docutils literal notranslate"><span class="pre">F</span></code> needs items from the stack below the left stuff it should have
 644 <code class="docutils literal notranslate"><span class="pre">cons</span></code>’d them before beginning maybe? For functions like <code class="docutils literal notranslate"><span class="pre">first</span></code>
 645 it works fine as-is.</p>
 646 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">left</span> <span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</span> <span class="p">[</span><span class="n">key</span> <span class="n">value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">first</span> <span class="p">[</span><span class="n">key</span> <span class="n">value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</span><span class="p">]</span>
 647 <span class="n">left</span> <span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</span> <span class="n">key</span> <span class="p">[</span><span class="n">key</span> <span class="n">value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</span><span class="p">]</span>
 648 </pre></div>
 649 </div>
 650 </section>
 651 <section id="process-the-right-child">
 652 <h3>Process the right child.<a class="headerlink" href="#process-the-right-child" title="Permalink to this headline">¶</a></h3>
 653 <p>First ditch the rest of the node and get the right child:</p>
 654 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">left</span> <span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</span> <span class="n">key</span> <span class="p">[</span><span class="n">key</span> <span class="n">value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</span><span class="p">]</span> <span class="p">[</span><span class="n">rest</span> <span class="n">rest</span> <span class="n">rest</span> <span class="n">first</span><span class="p">]</span> <span class="n">dip</span>
 655 <span class="n">left</span> <span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</span> <span class="n">key</span> <span class="n">right</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</span><span class="p">]</span>
 656 </pre></div>
 657 </div>
 658 <p>Then, of course, we just need <code class="docutils literal notranslate"><span class="pre">i</span></code> to run <code class="docutils literal notranslate"><span class="pre">Tree-iter-order</span></code> on the
 659 right side:</p>
 660 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">left</span> <span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</span> <span class="n">key</span> <span class="n">right</span> <span class="p">[</span><span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</span><span class="p">]</span> <span class="n">i</span>
 661 <span class="n">left</span> <span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</span> <span class="n">key</span> <span class="n">right</span> <span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</span>
 662 </pre></div>
 663 </div>
 664 </section>
 665 <section id="defining-tree-iter-order">
 666 <h3>Defining <code class="docutils literal notranslate"><span class="pre">Tree-iter-order</span></code><a class="headerlink" href="#defining-tree-iter-order" title="Permalink to this headline">¶</a></h3>
 667 <p>The result is a little awkward:</p>
 668 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">R1</span> <span class="o">==</span> <span class="p">[</span><span class="n">cons</span> <span class="n">dip</span><span class="p">]</span> <span class="n">dupdip</span> <span class="p">[[</span><span class="n">F</span><span class="p">]</span> <span class="n">dupdip</span><span class="p">]</span> <span class="n">dip</span> <span class="p">[</span><span class="n">rest</span> <span class="n">rest</span> <span class="n">rest</span> <span class="n">first</span><span class="p">]</span> <span class="n">dip</span> <span class="n">i</span>
 669 </pre></div>
 670 </div>
 671 <p>Let’s do a little semantic factoring:</p>
 672 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">fourth</span> <span class="o">==</span> <span class="n">rest</span> <span class="n">rest</span> <span class="n">rest</span> <span class="n">first</span>
 673
 674 <span class="n">proc_left</span> <span class="o">==</span> <span class="p">[</span><span class="n">cons</span> <span class="n">dip</span><span class="p">]</span> <span class="n">dupdip</span>
 675 <span class="n">proc_current</span> <span class="o">==</span> <span class="p">[[</span><span class="n">F</span><span class="p">]</span> <span class="n">dupdip</span><span class="p">]</span> <span class="n">dip</span>
 676 <span class="n">proc_right</span> <span class="o">==</span> <span class="p">[</span><span class="n">fourth</span><span class="p">]</span> <span class="n">dip</span> <span class="n">i</span>
 677
 678 <span class="n">Tree</span><span class="o">-</span><span class="nb">iter</span><span class="o">-</span><span class="n">order</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="p">]</span> <span class="p">[</span><span class="n">dup</span> <span class="n">third</span><span class="p">]</span> <span class="p">[</span><span class="n">proc_left</span> <span class="n">proc_current</span> <span class="n">proc_right</span><span class="p">]</span> <span class="n">genrec</span>
 679 </pre></div>
 680 </div>
 681 <p>Now we can sort sequences.</p>
 682 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="c1">#define(&#39;Tree-iter-order == [not] [pop] [dup third] [[cons dip] dupdip [[first] dupdip] dip [rest rest rest first] dip i] genrec&#39;)</span>
 683
 684
 685 <span class="n">DefinitionWrapper</span><span class="o">.</span><span class="n">add_definitions</span><span class="p">(</span><span class="s1">&#39;&#39;&#39;</span>
 686
 687 <span class="s1">fourth == rest rest rest first</span>
 688
 689 <span class="s1">proc_left == [cons dip] dupdip</span>
 690 <span class="s1">proc_current == [[first] dupdip] dip</span>
 691 <span class="s1">proc_right == [fourth] dip i</span>
 692
 693 <span class="s1">Tree-iter-order == [not] [pop] [dup third] [proc_left proc_current proc_right] genrec</span>
 694
 695 <span class="s1">&#39;&#39;&#39;</span><span class="p">,</span> <span class="n">D</span><span class="p">)</span>
 696 </pre></div>
 697 </div>
 698 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;[3 9 5 2 8 6 7 8 4] to_set Tree-iter-order&#39;</span><span class="p">)</span>
 699 </pre></div>
 700 </div>
 701 <div class="highlight-default notranslate"><div class="highlight"><pre><span></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>
 702 </pre></div>
 703 </div>
 704 <p>Parameterizing the <code class="docutils literal notranslate"><span class="pre">[F]</span></code> function is left as an exercise for the
 705 reader.</p>
 706 </section>
 707 </section>
 708 <section id="getting-values-by-key">
 709 <h2>Getting values by key<a class="headerlink" href="#getting-values-by-key" title="Permalink to this headline">¶</a></h2>
 710 <p>Let’s derive a function that accepts a tree and a key and returns the
 711 value associated with that key.</p>
 712 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>   <span class="n">tree</span> <span class="n">key</span> <span class="n">Tree</span><span class="o">-</span><span class="n">get</span>
 713 <span class="o">-----------------------</span>
 714         <span class="n">value</span>
 715 </pre></div>
 716 </div>
 717 <p>But what do we do if the key isn’t in the tree? In Python we might raise
 718 a <code class="docutils literal notranslate"><span class="pre">KeyError</span></code> but I’d like to avoid exceptions in Joy if possible, and
 719 here I think it’s possible. (Division by zero is an example of where I
 720 think it’s probably better to let Python crash Joy. Sometimes the
 721 machinery fails and you have to “stop the line”, I think.)</p>
 722 <p>Let’s pass the buck to the caller by making the base case a given, you
 723 have to decide for yourself what <code class="docutils literal notranslate"><span class="pre">[E]</span></code> should be.</p>
 724 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>   <span class="n">tree</span> <span class="n">key</span> <span class="p">[</span><span class="n">E</span><span class="p">]</span> <span class="n">Tree</span><span class="o">-</span><span class="n">get</span>
 725 <span class="o">----------------------------</span> <span class="n">key</span> <span class="ow">in</span> <span class="n">tree</span>
 726            <span class="n">value</span>
 727
 728    <span class="n">tree</span> <span class="n">key</span> <span class="p">[</span><span class="n">E</span><span class="p">]</span> <span class="n">Tree</span><span class="o">-</span><span class="n">get</span>
 729 <span class="o">----------------------------</span> <span class="n">key</span> <span class="ow">not</span> <span class="ow">in</span> <span class="n">tree</span>
 730          <span class="p">[]</span> <span class="n">key</span> <span class="n">E</span>
 731 </pre></div>
 732 </div>
 733 <section id="the-base-case">
 734 <h3>The base case <code class="docutils literal notranslate"><span class="pre">[]</span></code><a class="headerlink" href="#the-base-case" title="Permalink to this headline">¶</a></h3>
 735 <p>As before, the stopping predicate just has to detect the empty list:</p>
 736 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">Tree</span><span class="o">-</span><span class="n">get</span> <span class="o">==</span> <span class="p">[</span><span class="n">pop</span> <span class="ow">not</span><span class="p">]</span> <span class="p">[</span><span class="n">E</span><span class="p">]</span> <span class="p">[</span><span class="n">R0</span><span class="p">]</span> <span class="p">[</span><span class="n">R1</span><span class="p">]</span> <span class="n">genrec</span>
 737 </pre></div>
 738 </div>
 739 <p>So we define:</p>
 740 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">Tree</span><span class="o">-</span><span class="n">get</span> <span class="o">==</span> <span class="p">[</span><span class="n">pop</span> <span class="ow">not</span><span class="p">]</span> <span class="n">swap</span> <span class="p">[</span><span class="n">R0</span><span class="p">]</span> <span class="p">[</span><span class="n">R1</span><span class="p">]</span> <span class="n">genrec</span>
 741 </pre></div>
 742 </div>
 743 <p>Note that this <code class="docutils literal notranslate"><span class="pre">Tree-get</span></code> creates a slightly different function than
 744 itself and <em>that function</em> does the actual recursion. This kind of
 745 higher-level programming is unusual in most languages but natural in
 746 Joy.</p>
 747 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">tree</span> <span class="n">key</span> <span class="p">[</span><span class="n">E</span><span class="p">]</span> <span class="p">[</span><span class="n">pop</span> <span class="ow">not</span><span class="p">]</span> <span class="n">swap</span> <span class="p">[</span><span class="n">R0</span><span class="p">]</span> <span class="p">[</span><span class="n">R1</span><span class="p">]</span> <span class="n">genrec</span>
 748 <span class="n">tree</span> <span class="n">key</span> <span class="p">[</span><span class="n">pop</span> <span class="ow">not</span><span class="p">]</span> <span class="p">[</span><span class="n">E</span><span class="p">]</span> <span class="p">[</span><span class="n">R0</span><span class="p">]</span> <span class="p">[</span><span class="n">R1</span><span class="p">]</span> <span class="n">genrec</span>
 749 </pre></div>
 750 </div>
 751 <p>The anonymous specialized recursive function that will do the real work.</p>
 752 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">pop</span> <span class="ow">not</span><span class="p">]</span> <span class="p">[</span><span class="n">E</span><span class="p">]</span> <span class="p">[</span><span class="n">R0</span><span class="p">]</span> <span class="p">[</span><span class="n">R1</span><span class="p">]</span> <span class="n">genrec</span>
 753 </pre></div>
 754 </div>
 755 </section>
 756 <section id="id2">
 757 <h3>Node case <code class="docutils literal notranslate"><span class="pre">[key</span> <span class="pre">value</span> <span class="pre">left</span> <span class="pre">right]</span></code><a class="headerlink" href="#id2" title="Permalink to this headline">¶</a></h3>
 758 <p>Now we need to figure out <code class="docutils literal notranslate"><span class="pre">R0</span></code> and <code class="docutils literal notranslate"><span class="pre">R1</span></code>:</p>
 759 <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="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">key</span> <span class="n">R0</span> <span class="p">[</span><span class="n">BTree</span><span class="o">-</span><span class="n">get</span><span class="p">]</span> <span class="n">R1</span>
 760 </pre></div>
 761 </div>
 762 <p>We want to compare the search key with the key in the node, and if they
 763 are the same return the value, otherwise recur on one of the child
 764 nodes. So it’s very similar to the above funtion, with <code class="docutils literal notranslate"><span class="pre">[R0]</span> <span class="pre">==</span> <span class="pre">[]</span></code>
 765 and <code class="docutils literal notranslate"><span class="pre">R1</span> <span class="pre">==</span> <span class="pre">P</span> <span class="pre">[T&gt;]</span> <span class="pre">[E]</span> <span class="pre">[T&lt;]</span> <span class="pre">cmp</span></code>:</p>
 766 <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="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">key</span> <span class="p">[</span><span class="n">BTree</span><span class="o">-</span><span class="n">get</span><span class="p">]</span> <span class="n">P</span> <span class="p">[</span><span class="n">T</span><span class="o">&gt;</span><span class="p">]</span> <span class="p">[</span><span class="n">E</span><span class="p">]</span> <span class="p">[</span><span class="n">T</span><span class="o">&lt;</span><span class="p">]</span> <span class="n">cmp</span>
 767 </pre></div>
 768 </div>
 769 <section id="predicate">
 770 <h4>Predicate<a class="headerlink" href="#predicate" title="Permalink to this headline">¶</a></h4>
 771 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">P</span> <span class="o">==</span> <span class="n">over</span> <span class="p">[</span><span class="n">get</span><span class="o">-</span><span class="n">node</span><span class="o">-</span><span class="n">key</span><span class="p">]</span> <span class="n">nullary</span>
 772 <span class="n">get</span><span class="o">-</span><span class="n">node</span><span class="o">-</span><span class="n">key</span> <span class="o">==</span> <span class="n">pop</span> <span class="n">popop</span> <span class="n">first</span>
 773 </pre></div>
 774 </div>
 775 <p>The only difference is that <code class="docutils literal notranslate"><span class="pre">get-node-key</span></code> does one less <code class="docutils literal notranslate"><span class="pre">pop</span></code>
 776 because there’s no value to discard.</p>
 777 </section>
 778 <section id="branches">
 779 <h4>Branches<a class="headerlink" href="#branches" title="Permalink to this headline">¶</a></h4>
 780 <p>Now we have to derive the branches:</p>
 781 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">key_n</span> <span class="n">value_n</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">key</span> <span class="p">[</span><span class="n">BTree</span><span class="o">-</span><span class="n">get</span><span class="p">]</span> <span class="n">T</span><span class="o">&gt;</span>
 782 <span class="p">[</span><span class="n">key_n</span> <span class="n">value_n</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">key</span> <span class="p">[</span><span class="n">BTree</span><span class="o">-</span><span class="n">get</span><span class="p">]</span> <span class="n">E</span>
 783 <span class="p">[</span><span class="n">key_n</span> <span class="n">value_n</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">key</span> <span class="p">[</span><span class="n">BTree</span><span class="o">-</span><span class="n">get</span><span class="p">]</span> <span class="n">T</span><span class="o">&lt;</span>
 784 </pre></div>
 785 </div>
 786 </section>
 787 <section id="greater-than-and-less-than">
 788 <h4>Greater than and less than<a class="headerlink" href="#greater-than-and-less-than" title="Permalink to this headline">¶</a></h4>
 789 <p>The cases of <code class="docutils literal notranslate"><span class="pre">T&gt;</span></code> and <code class="docutils literal notranslate"><span class="pre">T&lt;</span></code> are similar to above but instead of using
 790 <code class="docutils literal notranslate"><span class="pre">infra</span></code> we have to discard the rest of the structure:</p>
 791 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>   <span class="p">[</span><span class="n">key_n</span> <span class="n">value_n</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">key</span> <span class="p">[</span><span class="n">BTree</span><span class="o">-</span><span class="n">get</span><span class="p">]</span> <span class="n">T</span><span class="o">&gt;</span>
 792 <span class="o">---------------------------------------------------</span>
 793                        <span class="n">right</span>  <span class="n">key</span>  <span class="n">BTree</span><span class="o">-</span><span class="n">get</span>
 794 </pre></div>
 795 </div>
 796 <p>And:</p>
 797 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>   <span class="p">[</span><span class="n">key_n</span> <span class="n">value_n</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">key</span> <span class="p">[</span><span class="n">BTree</span><span class="o">-</span><span class="n">get</span><span class="p">]</span> <span class="n">T</span><span class="o">&lt;</span>
 798 <span class="o">---------------------------------------------------</span>
 799                   <span class="n">left</span>        <span class="n">key</span>  <span class="n">BTree</span><span class="o">-</span><span class="n">get</span>
 800 </pre></div>
 801 </div>
 802 <p>So:</p>
 803 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">T</span><span class="o">&gt;</span> <span class="o">==</span> <span class="p">[</span><span class="n">fourth</span><span class="p">]</span> <span class="n">dipd</span> <span class="n">i</span>
 804 <span class="n">T</span><span class="o">&lt;</span> <span class="o">==</span> <span class="p">[</span><span class="n">third</span><span class="p">]</span> <span class="n">dipd</span> <span class="n">i</span>
 805 </pre></div>
 806 </div>
 807 <p>E.g.:</p>
 808 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">key_n</span> <span class="n">value_n</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span>        <span class="n">key</span> <span class="p">[</span><span class="n">BTree</span><span class="o">-</span><span class="n">get</span><span class="p">]</span> <span class="p">[</span><span class="n">fourth</span><span class="p">]</span> <span class="n">dipd</span> <span class="n">i</span>
 809 <span class="p">[</span><span class="n">key_n</span> <span class="n">value_n</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">fourth</span> <span class="n">key</span> <span class="p">[</span><span class="n">BTree</span><span class="o">-</span><span class="n">get</span><span class="p">]</span>               <span class="n">i</span>
 810                     <span class="n">right</span>         <span class="n">key</span> <span class="p">[</span><span class="n">BTree</span><span class="o">-</span><span class="n">get</span><span class="p">]</span>               <span class="n">i</span>
 811                     <span class="n">right</span>         <span class="n">key</span>  <span class="n">BTree</span><span class="o">-</span><span class="n">get</span>
 812 </pre></div>
 813 </div>
 814 </section>
 815 <section id="equal-keys">
 816 <h4>Equal keys<a class="headerlink" href="#equal-keys" title="Permalink to this headline">¶</a></h4>
 817 <p>Return the node’s value:</p>
 818 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">key_n</span> <span class="n">value_n</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="n">key</span> <span class="p">[</span><span class="n">BTree</span><span class="o">-</span><span class="n">get</span><span class="p">]</span> <span class="n">E</span> <span class="o">==</span> <span class="n">value_n</span>
 819
 820 <span class="n">E</span> <span class="o">==</span> <span class="n">popop</span> <span class="n">second</span>
 821 </pre></div>
 822 </div>
 823 </section>
 824 </section>
 825 <section id="tree-get">
 826 <h3><code class="docutils literal notranslate"><span class="pre">Tree-get</span></code><a class="headerlink" href="#tree-get" title="Permalink to this headline">¶</a></h3>
 827 <p>So:</p>
 828 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">fourth</span> <span class="o">==</span> <span class="n">rest</span> <span class="n">rest</span> <span class="n">rest</span> <span class="n">first</span>
 829 <span class="n">get</span><span class="o">-</span><span class="n">node</span><span class="o">-</span><span class="n">key</span> <span class="o">==</span> <span class="n">pop</span> <span class="n">popop</span> <span class="n">first</span>
 830 <span class="n">P</span> <span class="o">==</span> <span class="n">over</span> <span class="p">[</span><span class="n">get</span><span class="o">-</span><span class="n">node</span><span class="o">-</span><span class="n">key</span><span class="p">]</span> <span class="n">nullary</span>
 831 <span class="n">T</span><span class="o">&gt;</span> <span class="o">==</span> <span class="p">[</span><span class="n">fourth</span><span class="p">]</span> <span class="n">dipd</span> <span class="n">i</span>
 832 <span class="n">T</span><span class="o">&lt;</span> <span class="o">==</span> <span class="p">[</span><span class="n">third</span><span class="p">]</span> <span class="n">dipd</span> <span class="n">i</span>
 833 <span class="n">E</span> <span class="o">==</span> <span class="n">popop</span> <span class="n">second</span>
 834
 835 <span class="n">Tree</span><span class="o">-</span><span class="n">get</span> <span class="o">==</span> <span class="p">[</span><span class="n">pop</span> <span class="ow">not</span><span class="p">]</span> <span class="n">swap</span> <span class="p">[]</span> <span class="p">[</span><span class="n">P</span> <span class="p">[</span><span class="n">T</span><span class="o">&gt;</span><span class="p">]</span> <span class="p">[</span><span class="n">E</span><span class="p">]</span> <span class="p">[</span><span class="n">T</span><span class="o">&lt;</span><span class="p">]</span> <span class="n">cmp</span><span class="p">]</span> <span class="n">genrec</span>
 836 </pre></div>
 837 </div>
 838 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="c1"># I don&#39;t want to deal with name conflicts with the above so I&#39;m inlining everything here.</span>
 839 <span class="c1"># The original Joy system has &quot;hide&quot; which is a meta-command which allows you to use named</span>
 840 <span class="c1"># definitions that are only in scope for a given definition.  I don&#39;t want to implement</span>
 841 <span class="c1"># that (yet) so...</span>
 842
 843
 844 <span class="n">define</span><span class="p">(</span><span class="s1">&#39;&#39;&#39;</span>
 845 <span class="s1">Tree-get == [pop not] swap [] [</span>
 846 <span class="s1">  over [pop popop first] nullary</span>
 847 <span class="s1">  [[fourth] dipd i]</span>
 848 <span class="s1">  [popop second]</span>
 849 <span class="s1">  [[third] dipd i]</span>
 850 <span class="s1">  cmp</span>
 851 <span class="s1">  ] genrec</span>
 852 <span class="s1">&#39;&#39;&#39;</span><span class="p">)</span>
 853 </pre></div>
 854 </div>
 855 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;[&quot;gary&quot; 23 [] []] &quot;mike&quot; [popd &quot; not in tree&quot; +] Tree-get&#39;</span><span class="p">)</span>
 856 </pre></div>
 857 </div>
 858 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="s1">&#39;mike not in tree&#39;</span>
 859 </pre></div>
 860 </div>
 861 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;[&quot;gary&quot; 23 [] []] &quot;gary&quot; [popop &quot;err&quot;] Tree-get&#39;</span><span class="p">)</span>
 862 </pre></div>
 863 </div>
 864 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">23</span>
 865 </pre></div>
 866 </div>
 867 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;&#39;&#39;</span>
 868
 869 <span class="s1">    [] [[0 &#39;a&#39;] [1 &#39;b&#39;] [2 &#39;c&#39;]] [i Tree-add] step</span>
 870
 871 <span class="s1">    &#39;c&#39; [popop &#39;not found&#39;] Tree-get</span>
 872
 873 <span class="s1">&#39;&#39;&#39;</span><span class="p">)</span>
 874 </pre></div>
 875 </div>
 876 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">2</span>
 877 </pre></div>
 878 </div>
 879 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;&#39;&#39;</span>
 880
 881 <span class="s1">    [] [[0 &#39;a&#39;] [1 &#39;b&#39;] [2 &#39;c&#39;]] [i Tree-add] step</span>
 882
 883 <span class="s1">    &#39;d&#39; [popop &#39;not found&#39;] Tree-get</span>
 884
 885 <span class="s1">&#39;&#39;&#39;</span><span class="p">)</span>
 886 </pre></div>
 887 </div>
 888 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="s1">&#39;not found&#39;</span>
 889 </pre></div>
 890 </div>
 891 </section>
 892 </section>
 893 <section id="tree-delete">
 894 <h2>Tree-delete<a class="headerlink" href="#tree-delete" title="Permalink to this headline">¶</a></h2>
 895 <p>Now let’s write a function that can return a tree datastructure with a
 896 key, value pair deleted:</p>
 897 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>   <span class="n">tree</span> <span class="n">key</span> <span class="n">Tree</span><span class="o">-</span><span class="n">delete</span>
 898 <span class="o">---------------------------</span>
 899           <span class="n">tree</span>
 900 </pre></div>
 901 </div>
 902 <p>If the key is not in tree it just returns the tree unchanged.</p>
 903 <section id="id3">
 904 <h3>Base case<a class="headerlink" href="#id3" title="Permalink to this headline">¶</a></h3>
 905 <p>Same as above.</p>
 906 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">Tree</span><span class="o">-</span><span class="n">Delete</span> <span class="o">==</span> <span class="p">[</span><span class="n">pop</span> <span class="ow">not</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">R0</span><span class="p">]</span> <span class="p">[</span><span class="n">R1</span><span class="p">]</span> <span class="n">genrec</span>
 907 </pre></div>
 908 </div>
 909 </section>
 910 <section id="id4">
 911 <h3>Recur<a class="headerlink" href="#id4" title="Permalink to this headline">¶</a></h3>
 912 <p>Now we get to figure out the recursive case. We need the node’s key to
 913 compare and we need to carry the key into recursive branches. Let <code class="docutils literal notranslate"><span class="pre">D</span></code>
 914 be shorthand for <code class="docutils literal notranslate"><span class="pre">Tree-Delete</span></code>:</p>
 915 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>D == Tree-Delete == [pop not] [pop] [R0] [R1] genrec
 916
 917 [node_key node_value left right] key R0                   [D] R1
 918 [node_key node_value left right] key over  first swap dup [D] cons R1′
 919 [node_key node_value left right] key [...] first swap dup [D] cons R1′
 920 [node_key node_value left right] key node_key    swap dup [D] cons R1′
 921 [node_key node_value left right] node_key key         dup [D] cons R1′
 922 [node_key node_value left right] node_key key key         [D] cons R1′
 923 [node_key node_value left right] node_key key         [key D]      R1′
 924 </pre></div>
 925 </div>
 926 <p>And then:</p>
 927 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>[node_key node_value left right] node_key key [key D] R1′
 928 [node_key node_value left right] node_key key [key D] roll&gt; [T&gt;] [E] [T&lt;] cmp
 929 [node_key node_value left right] node_key key [key D] roll&gt; [T&gt;] [E] [T&lt;] cmp
 930 [node_key node_value left right] [key D] node_key key       [T&gt;] [E] [T&lt;] cmp
 931 </pre></div>
 932 </div>
 933 <p>So:</p>
 934 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">R0</span> <span class="o">==</span> <span class="n">over</span> <span class="n">first</span> <span class="n">swap</span> <span class="n">dup</span>
 935 <span class="n">R1</span> <span class="o">==</span> <span class="n">cons</span> <span class="n">roll</span><span class="o">&gt;</span> <span class="p">[</span><span class="n">T</span><span class="o">&gt;</span><span class="p">]</span> <span class="p">[</span><span class="n">E</span><span class="p">]</span> <span class="p">[</span><span class="n">T</span><span class="o">&lt;</span><span class="p">]</span> <span class="n">cmp</span>
 936 </pre></div>
 937 </div>
 938 </section>
 939 <section id="compare-keys">
 940 <h3>Compare Keys<a class="headerlink" href="#compare-keys" title="Permalink to this headline">¶</a></h3>
 941 <p>The last line above:</p>
 942 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">node_key</span> <span class="n">node_value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">key</span> <span class="n">D</span><span class="p">]</span> <span class="n">node_key</span> <span class="n">key</span> <span class="p">[</span><span class="n">T</span><span class="o">&gt;</span><span class="p">]</span> <span class="p">[</span><span class="n">E</span><span class="p">]</span> <span class="p">[</span><span class="n">T</span><span class="o">&lt;</span><span class="p">]</span> <span class="n">cmp</span>
 943 </pre></div>
 944 </div>
 945 <p>Then becomes one of these three:</p>
 946 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">node_key</span> <span class="n">node_value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">key</span> <span class="n">D</span><span class="p">]</span> <span class="n">T</span><span class="o">&gt;</span>
 947 <span class="p">[</span><span class="n">node_key</span> <span class="n">node_value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">key</span> <span class="n">D</span><span class="p">]</span> <span class="n">E</span>
 948 <span class="p">[</span><span class="n">node_key</span> <span class="n">node_value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">key</span> <span class="n">D</span><span class="p">]</span> <span class="n">T</span><span class="o">&lt;</span>
 949 </pre></div>
 950 </div>
 951 </section>
 952 <section id="greater-than-case-and-less-than-case">
 953 <h3>Greater than case and less than case<a class="headerlink" href="#greater-than-case-and-less-than-case" title="Permalink to this headline">¶</a></h3>
 954 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>   <span class="p">[</span><span class="n">node_key</span> <span class="n">node_value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">F</span><span class="p">]</span> <span class="n">T</span><span class="o">&gt;</span>
 955 <span class="o">-------------------------------------------------</span>
 956    <span class="p">[</span><span class="n">node_key</span> <span class="n">node_value</span> <span class="p">(</span><span class="n">left</span> <span class="n">F</span><span class="p">)</span> <span class="n">right</span><span class="p">]</span>
 957
 958
 959    <span class="p">[</span><span class="n">node_key</span> <span class="n">node_value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">F</span><span class="p">]</span> <span class="n">T</span><span class="o">&lt;</span>
 960 <span class="o">-------------------------------------------------</span>
 961    <span class="p">[</span><span class="n">node_key</span> <span class="n">node_value</span> <span class="n">left</span> <span class="p">(</span><span class="n">right</span> <span class="n">F</span><span class="p">)]</span>
 962 </pre></div>
 963 </div>
 964 <p>First, treating the node as a stack:</p>
 965 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">right</span> <span class="n">left</span>       <span class="n">node_value</span> <span class="n">node_key</span> <span class="p">[</span><span class="n">key</span> <span class="n">D</span><span class="p">]</span> <span class="n">dipd</span>
 966 <span class="n">right</span> <span class="n">left</span> <span class="n">key</span> <span class="n">D</span> <span class="n">node_value</span> <span class="n">node_key</span>
 967 <span class="n">right</span> <span class="n">left</span><span class="s1">&#39;      node_value node_key</span>
 968 </pre></div>
 969 </div>
 970 <p>Ergo:</p>
 971 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">node_key</span> <span class="n">node_value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">key</span> <span class="n">D</span><span class="p">]</span> <span class="p">[</span><span class="n">dipd</span><span class="p">]</span> <span class="n">cons</span> <span class="n">infra</span>
 972 </pre></div>
 973 </div>
 974 <p>So:</p>
 975 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">T</span><span class="o">&gt;</span> <span class="o">==</span> <span class="p">[</span><span class="n">dipd</span><span class="p">]</span> <span class="n">cons</span> <span class="n">infra</span>
 976 <span class="n">T</span><span class="o">&lt;</span> <span class="o">==</span> <span class="p">[</span><span class="n">dipdd</span><span class="p">]</span> <span class="n">cons</span> <span class="n">infra</span>
 977 </pre></div>
 978 </div>
 979 </section>
 980 <section id="the-else-case">
 981 <h3>The else case<a class="headerlink" href="#the-else-case" title="Permalink to this headline">¶</a></h3>
 982 <p>We have found the node in the tree where <code class="docutils literal notranslate"><span class="pre">key</span></code> equals <code class="docutils literal notranslate"><span class="pre">node_key</span></code>. We
 983 need to replace the current node with something</p>
 984 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>   <span class="p">[</span><span class="n">node_key</span> <span class="n">node_value</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">key</span> <span class="n">D</span><span class="p">]</span> <span class="n">E</span>
 985 <span class="o">------------------------------------------------</span>
 986                     <span class="n">tree</span>
 987 </pre></div>
 988 </div>
 989 <p>We have to handle three cases, so let’s use <code class="docutils literal notranslate"><span class="pre">cond</span></code>.</p>
 990 <section id="one-or-more-child-nodes-are">
 991 <h4>One or more child nodes are <code class="docutils literal notranslate"><span class="pre">[]</span></code><a class="headerlink" href="#one-or-more-child-nodes-are" title="Permalink to this headline">¶</a></h4>
 992 <p>The first two cases are symmetrical: if we only have one non-empty child
 993 node return it. If both child nodes are empty return an empty node.</p>
 994 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">E</span> <span class="o">==</span> <span class="p">[</span>
 995     <span class="p">[[</span><span class="n">pop</span> <span class="n">third</span> <span class="ow">not</span><span class="p">]</span> <span class="n">pop</span> <span class="n">fourth</span><span class="p">]</span>
 996     <span class="p">[[</span><span class="n">pop</span> <span class="n">fourth</span> <span class="ow">not</span><span class="p">]</span> <span class="n">pop</span> <span class="n">third</span><span class="p">]</span>
 997     <span class="p">[</span><span class="n">default</span><span class="p">]</span>
 998 <span class="p">]</span> <span class="n">cond</span>
 999 </pre></div>
1000 </div>
1001 </section>
1002 <section id="both-child-nodes-are-non-empty">
1003 <h4>Both child nodes are non-empty.<a class="headerlink" href="#both-child-nodes-are-non-empty" title="Permalink to this headline">¶</a></h4>
1004 <p>If both child nodes are non-empty, we find the highest node in our lower
1005 sub-tree, take its key and value to replace (delete) our own, then get
1006 rid of it by recursively calling delete() on our lower sub-node with our
1007 new key.</p>
1008 <p>(We could also find the lowest node in our higher sub-tree and take its
1009 key and value and delete it. I only implemented one of these two
1010 symmetrical options. Over a lot of deletions this might make the tree
1011 more unbalanced. Oh well.)</p>
1012 <p>The initial structure of the default function:</p>
1013 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>default == [E′] cons infra
1014
1015 [node_key node_value left right] [key D] default
1016 [node_key node_value left right] [key D] [E′] cons infra
1017 [node_key node_value left right] [[key D] E′]      infra
1018
1019 right left node_value node_key [key D] E′
1020 </pre></div>
1021 </div>
1022 <p>First things first, we no longer need this node’s key and value:</p>
1023 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>right left node_value node_key [key D] roll&gt; popop E″
1024 right left [key D] node_value node_key       popop E″
1025 right left [key D]                                 E″
1026 </pre></div>
1027 </div>
1028 </section>
1029 <section id="we-have-to-we-find-the-highest-right-most-node-in-our-lower-left-sub-tree">
1030 <h4>We have to we find the highest (right-most) node in our lower (left) sub-tree:<a class="headerlink" href="#we-have-to-we-find-the-highest-right-most-node-in-our-lower-left-sub-tree" title="Permalink to this headline">¶</a></h4>
1031 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>right left [key D] E″
1032 </pre></div>
1033 </div>
1034 <p>Ditch the key:</p>
1035 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>right left [key D] rest E‴
1036 right left     [D]      E‴
1037 </pre></div>
1038 </div>
1039 <p>Find the right-most node:</p>
1040 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>right left        [D] [dup W] dip E⁗
1041 right left dup  W [D]             E⁗
1042 right left left W [D]             E⁗
1043 </pre></div>
1044 </div>
1045 <p>Consider:</p>
1046 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">left</span> <span class="n">W</span>
1047 </pre></div>
1048 </div>
1049 <p>We know left is not empty:</p>
1050 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">L_key</span> <span class="n">L_value</span> <span class="n">L_left</span> <span class="n">L_right</span><span class="p">]</span> <span class="n">W</span>
1051 </pre></div>
1052 </div>
1053 <p>We want to keep extracting the right node as long as it is not empty:</p>
1054 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>W.rightmost == [P] [B] while
1055
1056 left W.rightmost W′
1057 </pre></div>
1058 </div>
1059 <p>The predicate:</p>
1060 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">L_key</span> <span class="n">L_value</span> <span class="n">L_left</span> <span class="n">L_right</span><span class="p">]</span> <span class="n">P</span>
1061 <span class="p">[</span><span class="n">L_key</span> <span class="n">L_value</span> <span class="n">L_left</span> <span class="n">L_right</span><span class="p">]</span> <span class="n">fourth</span>
1062                       <span class="n">L_right</span>
1063 </pre></div>
1064 </div>
1065 <p>This can run on <code class="docutils literal notranslate"><span class="pre">[]</span></code> so must be guarded:</p>
1066 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>?fourth ==  [] [fourth] [] ifte
1067 </pre></div>
1068 </div>
1069 <p>( if_not_empty == [] swap [] ifte ?fourth == [fourth] if_not_empty )</p>
1070 <p>The body is just <code class="docutils literal notranslate"><span class="pre">fourth</span></code>:</p>
1071 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>left [?fourth] [fourth] while W′
1072 rightest                      W′
1073 </pre></div>
1074 </div>
1075 <p>So:</p>
1076 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>W.rightmost == [?fourth] [fourth] while
1077 </pre></div>
1078 </div>
1079 </section>
1080 <section id="found-right-most-node-in-our-left-sub-tree">
1081 <h4>Found right-most node in our left sub-tree<a class="headerlink" href="#found-right-most-node-in-our-left-sub-tree" title="Permalink to this headline">¶</a></h4>
1082 <p>We know rightest is not empty:</p>
1083 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>[R_key R_value R_left R_right] W′
1084 [R_key R_value R_left R_right] W′
1085 [R_key R_value R_left R_right] uncons uncons pop
1086 R_key [R_value R_left R_right]        uncons pop
1087 R_key R_value [R_left R_right]               pop
1088 R_key R_value
1089 </pre></div>
1090 </div>
1091 <p>So:</p>
1092 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>W == [?fourth] [fourth] while uncons uncons pop
1093 </pre></div>
1094 </div>
1095 <p>And:</p>
1096 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>right left left W        [D] E⁗
1097 right left R_key R_value [D] E⁗
1098 </pre></div>
1099 </div>
1100 </section>
1101 <section id="replace-current-node-key-and-value-recursively-delete-rightmost">
1102 <h4>Replace current node key and value, recursively delete rightmost<a class="headerlink" href="#replace-current-node-key-and-value-recursively-delete-rightmost" title="Permalink to this headline">¶</a></h4>
1103 <p>Final stretch. We want to end up with something like:</p>
1104 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>right left [R_key D] i R_value R_key
1105 right left  R_key D    R_value R_key
1106 right left′            R_value R_key
1107 </pre></div>
1108 </div>
1109 <p>If we adjust our definition of <code class="docutils literal notranslate"><span class="pre">W</span></code> to include <code class="docutils literal notranslate"><span class="pre">over</span></code> at the end:</p>
1110 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">W</span> <span class="o">==</span> <span class="p">[</span><span class="n">fourth</span><span class="p">]</span> <span class="p">[</span><span class="n">fourth</span><span class="p">]</span> <span class="k">while</span> <span class="n">uncons</span> <span class="n">uncons</span> <span class="n">pop</span> <span class="n">over</span>
1111 </pre></div>
1112 </div>
1113 <p>That will give us:</p>
1114 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>right left R_key R_value R_key [D] E⁗
1115
1116 right left         R_key R_value R_key [D] cons dipd E⁗′
1117 right left         R_key R_value [R_key D]      dipd E⁗′
1118 right left R_key D R_key R_value                     E⁗′
1119 right left′        R_key R_value                     E⁗′
1120 right left′        R_key R_value                     swap
1121 right left′ R_value R_key
1122 </pre></div>
1123 </div>
1124 <p>So:</p>
1125 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>E′ == roll&gt; popop E″
1126
1127 E″ == rest E‴
1128
1129 E‴ == [dup W] dip E⁗
1130
1131 E⁗ == cons dipdd swap
1132 </pre></div>
1133 </div>
1134 <p>Substituting:</p>
1135 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>W == [fourth] [fourth] while uncons uncons pop over
1136 E′ == roll&gt; popop rest [dup W] dip cons dipd swap
1137 E == [
1138     [[pop third not] pop fourth]
1139     [[pop fourth not] pop third]
1140     [[E′] cons infra]
1141 ] cond
1142 </pre></div>
1143 </div>
1144 <p>Minor rearrangement, move <code class="docutils literal notranslate"><span class="pre">dup</span></code> into <code class="docutils literal notranslate"><span class="pre">W</span></code>:</p>
1145 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>W == dup [fourth] [fourth] while uncons uncons pop over
1146 E′ == roll&gt; popop rest [W] dip cons dipd swap
1147 E == [
1148     [[pop third not] pop fourth]
1149     [[pop fourth not] pop third]
1150     [[E′] cons infra]
1151 ] cond
1152 </pre></div>
1153 </div>
1154 </section>
1155 </section>
1156 <section id="refactoring">
1157 <h3>Refactoring<a class="headerlink" href="#refactoring" title="Permalink to this headline">¶</a></h3>
1158 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">W</span><span class="o">.</span><span class="n">rightmost</span> <span class="o">==</span> <span class="p">[</span><span class="n">fourth</span><span class="p">]</span> <span class="p">[</span><span class="n">fourth</span><span class="p">]</span> <span class="k">while</span>
1159 <span class="n">W</span><span class="o">.</span><span class="n">unpack</span> <span class="o">==</span> <span class="n">uncons</span> <span class="n">uncons</span> <span class="n">pop</span>
1160 <span class="n">W</span> <span class="o">==</span> <span class="n">dup</span> <span class="n">W</span><span class="o">.</span><span class="n">rightmost</span> <span class="n">W</span><span class="o">.</span><span class="n">unpack</span> <span class="n">over</span>
1161 <span class="n">E</span><span class="o">.</span><span class="n">clear_stuff</span> <span class="o">==</span> <span class="n">roll</span><span class="o">&gt;</span> <span class="n">popop</span> <span class="n">rest</span>
1162 <span class="n">E</span><span class="o">.</span><span class="n">delete</span> <span class="o">==</span> <span class="n">cons</span> <span class="n">dipd</span>
1163 <span class="n">E</span><span class="o">.</span><span class="mi">0</span> <span class="o">==</span> <span class="n">E</span><span class="o">.</span><span class="n">clear_stuff</span> <span class="p">[</span><span class="n">W</span><span class="p">]</span> <span class="n">dip</span> <span class="n">E</span><span class="o">.</span><span class="n">delete</span> <span class="n">swap</span>
1164 <span class="n">E</span> <span class="o">==</span> <span class="p">[</span>
1165     <span class="p">[[</span><span class="n">pop</span> <span class="n">third</span> <span class="ow">not</span><span class="p">]</span> <span class="n">pop</span> <span class="n">fourth</span><span class="p">]</span>
1166     <span class="p">[[</span><span class="n">pop</span> <span class="n">fourth</span> <span class="ow">not</span><span class="p">]</span> <span class="n">pop</span> <span class="n">third</span><span class="p">]</span>
1167     <span class="p">[[</span><span class="n">E</span><span class="o">.</span><span class="mi">0</span><span class="p">]</span> <span class="n">cons</span> <span class="n">infra</span><span class="p">]</span>
1168 <span class="p">]</span> <span class="n">cond</span>
1169 <span class="n">T</span><span class="o">&gt;</span> <span class="o">==</span> <span class="p">[</span><span class="n">dipd</span><span class="p">]</span> <span class="n">cons</span> <span class="n">infra</span>
1170 <span class="n">T</span><span class="o">&lt;</span> <span class="o">==</span> <span class="p">[</span><span class="n">dipdd</span><span class="p">]</span> <span class="n">cons</span> <span class="n">infra</span>
1171 <span class="n">R0</span> <span class="o">==</span> <span class="n">over</span> <span class="n">first</span> <span class="n">swap</span> <span class="n">dup</span>
1172 <span class="n">R1</span> <span class="o">==</span> <span class="n">cons</span> <span class="n">roll</span><span class="o">&gt;</span> <span class="p">[</span><span class="n">T</span><span class="o">&gt;</span><span class="p">]</span> <span class="p">[</span><span class="n">E</span><span class="p">]</span> <span class="p">[</span><span class="n">T</span><span class="o">&lt;</span><span class="p">]</span> <span class="n">cmp</span>
1173 <span class="n">BTree</span><span class="o">-</span><span class="n">Delete</span> <span class="o">==</span> <span class="p">[</span><span class="n">pop</span> <span class="ow">not</span><span class="p">]</span> <span class="n">swap</span> <span class="p">[</span><span class="n">R0</span><span class="p">]</span> <span class="p">[</span><span class="n">R1</span><span class="p">]</span> <span class="n">genrec</span>
1174 </pre></div>
1175 </div>
1176 <p>By the standards of the code I’ve written so far, this is a <em>huge</em> Joy
1177 program.</p>
1178 <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">&#39;&#39;&#39;</span>
1179 <span class="s1">first_two == uncons uncons pop</span>
1180 <span class="s1">fourth == rest rest rest first</span>
1181 <span class="s1">?fourth == [] [fourth] [] ifte</span>
1182 <span class="s1">W.rightmost == [?fourth] [fourth] while</span>
1183 <span class="s1">E.clear_stuff == roll&gt; popop rest</span>
1184 <span class="s1">E.delete == cons dipd</span>
1185 <span class="s1">W == dup W.rightmost first_two over</span>
1186 <span class="s1">E.0 == E.clear_stuff [W] dip E.delete swap</span>
1187 <span class="s1">E == [[[pop third not] pop fourth] [[pop fourth not] pop third] [[E.0] cons infra]] cond</span>
1188 <span class="s1">T&gt; == [dipd] cons infra</span>
1189 <span class="s1">T&lt; == [dipdd] cons infra</span>
1190 <span class="s1">R0 == over first swap dup</span>
1191 <span class="s1">R1 == cons roll&gt; [T&gt;] [E] [T&lt;] cmp</span>
1192 <span class="s1">Tree-Delete == [pop not] [pop] [R0] [R1] genrec</span>
1193 <span class="s1">&#39;&#39;&#39;</span><span class="p">,</span> <span class="n">D</span><span class="p">)</span>
1194 </pre></div>
1195 </div>
1196 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s2">&quot;[&#39;a&#39; 23 [] [&#39;b&#39; 88 [] [&#39;c&#39; 44 [] []]]] &#39;c&#39; Tree-Delete &quot;</span><span class="p">)</span>
1197 </pre></div>
1198 </div>
1199 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="s1">&#39;a&#39;</span> <span class="mi">23</span> <span class="p">[]</span> <span class="p">[</span><span class="s1">&#39;b&#39;</span> <span class="mi">88</span> <span class="p">[]</span> <span class="p">[]]]</span>
1200 </pre></div>
1201 </div>
1202 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s2">&quot;[&#39;a&#39; 23 [] [&#39;b&#39; 88 [] [&#39;c&#39; 44 [] []]]] &#39;b&#39; Tree-Delete &quot;</span><span class="p">)</span>
1203 </pre></div>
1204 </div>
1205 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="s1">&#39;a&#39;</span> <span class="mi">23</span> <span class="p">[]</span> <span class="p">[</span><span class="s1">&#39;c&#39;</span> <span class="mi">44</span> <span class="p">[]</span> <span class="p">[]]]</span>
1206 </pre></div>
1207 </div>
1208 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s2">&quot;[&#39;a&#39; 23 [] [&#39;b&#39; 88 [] [&#39;c&#39; 44 [] []]]] &#39;a&#39; Tree-Delete &quot;</span><span class="p">)</span>
1209 </pre></div>
1210 </div>
1211 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="s1">&#39;b&#39;</span> <span class="mi">88</span> <span class="p">[]</span> <span class="p">[</span><span class="s1">&#39;c&#39;</span> <span class="mi">44</span> <span class="p">[]</span> <span class="p">[]]]</span>
1212 </pre></div>
1213 </div>
1214 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s2">&quot;[&#39;a&#39; 23 [] [&#39;b&#39; 88 [] [&#39;c&#39; 44 [] []]]] &#39;der&#39; Tree-Delete &quot;</span><span class="p">)</span>
1215 </pre></div>
1216 </div>
1217 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="s1">&#39;a&#39;</span> <span class="mi">23</span> <span class="p">[]</span> <span class="p">[</span><span class="s1">&#39;b&#39;</span> <span class="mi">88</span> <span class="p">[]</span> <span class="p">[</span><span class="s1">&#39;c&#39;</span> <span class="mi">44</span> <span class="p">[]</span> <span class="p">[]]]]</span>
1218 </pre></div>
1219 </div>
1220 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">&#39;[] [4 2 3 1 6 7 5 ] [0 swap Tree-add] step&#39;</span><span class="p">)</span>
1221 </pre></div>
1222 </div>
1223 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="mi">4</span> <span class="mi">0</span> <span class="p">[</span><span class="mi">2</span> <span class="mi">0</span> <span class="p">[</span><span class="mi">1</span> <span class="mi">0</span> <span class="p">[]</span> <span class="p">[]]</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">0</span> <span class="p">[]</span> <span class="p">[]]]</span> <span class="p">[</span><span class="mi">6</span> <span class="mi">0</span> <span class="p">[</span><span class="mi">5</span> <span class="mi">0</span> <span class="p">[]</span> <span class="p">[]]</span> <span class="p">[</span><span class="mi">7</span> <span class="mi">0</span> <span class="p">[]</span> <span class="p">[]]]]</span>
1224 </pre></div>
1225 </div>
1226 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s2">&quot;[4 0 [2 0 [1 0 [] []] [3 0 [] []]] [6 0 [5 0 [] []] [7 0 [] []]]] 3 Tree-Delete &quot;</span><span class="p">)</span>
1227 </pre></div>
1228 </div>
1229 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="mi">4</span> <span class="mi">0</span> <span class="p">[</span><span class="mi">2</span> <span class="mi">0</span> <span class="p">[</span><span class="mi">1</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">6</span> <span class="mi">0</span> <span class="p">[</span><span class="mi">5</span> <span class="mi">0</span> <span class="p">[]</span> <span class="p">[]]</span> <span class="p">[</span><span class="mi">7</span> <span class="mi">0</span> <span class="p">[]</span> <span class="p">[]]]]</span>
1230 </pre></div>
1231 </div>
1232 <div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s2">&quot;[4 0 [2 0 [1 0 [] []] [3 0 [] []]] [6 0 [5 0 [] []] [7 0 [] []]]] 4 Tree-Delete &quot;</span><span class="p">)</span>
1233 </pre></div>
1234 </div>
1235 <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="mi">2</span> <span class="mi">0</span> <span class="p">[</span><span class="mi">1</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">6</span> <span class="mi">0</span> <span class="p">[</span><span class="mi">5</span> <span class="mi">0</span> <span class="p">[]</span> <span class="p">[]]</span> <span class="p">[</span><span class="mi">7</span> <span class="mi">0</span> <span class="p">[]</span> <span class="p">[]]]]</span>
1236 </pre></div>
1237 </div>
1238 </section>
1239 </section>
1240 <section id="appendix-the-source-code">
1241 <h2>Appendix: The source code.<a class="headerlink" href="#appendix-the-source-code" title="Permalink to this headline">¶</a></h2>
1242 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>fourth == rest_two rest first
1243 ?fourth == [] [fourth] [] ifte
1244 first_two == uncons uncons pop
1245 ccons == cons cons
1246 cinf == cons infra
1247 rest_two == rest rest
1248
1249 _Tree_T&gt; == [dipd] cinf
1250 _Tree_T&lt; == [dipdd] cinf
1251
1252 _Tree_add_P == over [popop popop first] nullary
1253 _Tree_add_T&gt; == ccons _Tree_T&lt;
1254 _Tree_add_T&lt; == ccons _Tree_T&gt;
1255 _Tree_add_Ee == pop swap roll&lt; rest_two ccons
1256 _Tree_add_R == _Tree_add_P [_Tree_add_T&gt;] [_Tree_add_Ee] [_Tree_add_T&lt;] cmp
1257 _Tree_add_E == [pop] dipd Tree-new
1258
1259 _Tree_iter_order_left == [cons dip] dupdip
1260 _Tree_iter_order_current == [[F] dupdip] dip
1261 _Tree_iter_order_right == [fourth] dip i
1262 _Tree_iter_order_R == _Tree_iter_order_left _Tree_iter_order_current _Tree_iter_order_right
1263
1264 _Tree_get_P == over [pop popop first] nullary
1265 _Tree_get_T&gt; == [fourth] dipd i
1266 _Tree_get_T&lt; == [third] dipd i
1267 _Tree_get_E == popop second
1268 _Tree_get_R == _Tree_get_P [_Tree_get_T&gt;] [_Tree_get_E] [_Tree_get_T&lt;] cmp
1269
1270 _Tree_delete_rightmost == [?fourth] [fourth] while
1271 _Tree_delete_clear_stuff == roll&gt; popop rest
1272 _Tree_delete_del == dip cons dipd swap
1273 _Tree_delete_W == dup _Tree_delete_rightmost first_two over
1274 _Tree_delete_E.0 == _Tree_delete_clear_stuff [_Tree_delete_W] _Tree_delete_del
1275 _Tree_delete_E == [[[pop third not] pop fourth] [[pop fourth not] pop third] [[_Tree_delete_E.0] cinf]] cond
1276 _Tree_delete_R0 == over first swap dup
1277 _Tree_delete_R1 == cons roll&gt; [_Tree_T&gt;] [_Tree_delete_E] [_Tree_T&lt;] cmp
1278
1279 Tree-new == swap [[] []] ccons
1280 Tree-add == [popop not] [_Tree_add_E] [] [_Tree_add_R] genrec
1281 Tree-iter == [not] [pop] roll&lt; [dupdip rest_two] cons [step] genrec
1282 Tree-iter-order == [not] [pop] [dup third] [_Tree_iter_order_R] genrec
1283 Tree-get == [pop not] swap [] [_Tree_get_R] genrec
1284 Tree-delete == [pop not] [pop] [_Tree_delete_R0] [_Tree_delete_R1] genrec
1285 </pre></div>
1286 </div>
1287 </section>
1288 </section>
1289
1290
1291           </div>
1292
1293         </div>
1294       </div>
1295       <div class="sphinxsidebar" role="navigation" aria-label="main navigation">
1296         <div class="sphinxsidebarwrapper">
1297 <h1 class="logo"><a href="../index.html">Thun</a></h1>
1298
1299
1300
1301
1302
1303
1304
1305
1306 <h3>Navigation</h3>
1307 <ul class="current">
1308 <li class="toctree-l1"><a class="reference internal" href="Intro.html">Thun: Joy in Python</a></li>
1309 <li class="toctree-l1"><a class="reference internal" href="../joy.html">Joy Interpreter</a></li>
1310 <li class="toctree-l1"><a class="reference internal" href="../stack.html">Stack or Quote or Sequence or List…</a></li>
1311 <li class="toctree-l1"><a class="reference internal" href="../parser.html">Parsing Text into Joy Expressions</a></li>
1312 <li class="toctree-l1"><a class="reference internal" href="../pretty.html">Tracing Joy Execution</a></li>
1313 <li class="toctree-l1"><a class="reference internal" href="../library.html">Function Reference</a></li>
1314 <li class="toctree-l1"><a class="reference internal" href="../lib.html">Functions Grouped by, er, Function with Examples</a></li>
1315 <li class="toctree-l1"><a class="reference internal" href="../types.html">Type Inference of Joy Expressions</a></li>
1316 <li class="toctree-l1 current"><a class="reference internal" href="index.html">Essays about Programming in Joy</a><ul class="current">
1317 <li class="toctree-l2"><a class="reference internal" href="Developing.html">Developing a Program in Joy</a></li>
1318 <li class="toctree-l2"><a class="reference internal" href="Quadratic.html">Quadratic formula</a></li>
1319 <li class="toctree-l2"><a class="reference internal" href="Replacing.html">Replacing Functions in the Dictionary</a></li>
1320 <li class="toctree-l2"><a class="reference internal" href="Recursion_Combinators.html">Recursion Combinators</a></li>
1321 <li class="toctree-l2 current"><a class="current reference internal" href="#">Treating Trees I: Ordered Binary Trees</a></li>
1322 <li class="toctree-l2"><a class="reference internal" href="Treestep.html">Treating Trees II: <code class="docutils literal notranslate"><span class="pre">treestep</span></code></a></li>
1323 <li class="toctree-l2"><a class="reference internal" href="Generator_Programs.html">Using <code class="docutils literal notranslate"><span class="pre">x</span></code> to Generate Values</a></li>
1324 <li class="toctree-l2"><a class="reference internal" href="Newton-Raphson.html">Newton’s method</a></li>
1325 <li class="toctree-l2"><a class="reference internal" href="Square_Spiral.html">Square Spiral Example Joy Code</a></li>
1326 <li class="toctree-l2"><a class="reference internal" href="Zipper.html">Traversing Datastructures with Zippers</a></li>
1327 <li class="toctree-l2"><a class="reference internal" href="Types.html">The Blissful Elegance of Typing Joy</a></li>
1328 <li class="toctree-l2"><a class="reference internal" href="TypeChecking.html">Type Checking</a></li>
1329 <li class="toctree-l2"><a class="reference internal" href="NoUpdates.html">No Updates</a></li>
1330 <li class="toctree-l2"><a class="reference internal" href="Categorical.html">Categorical Programming</a></li>
1331 <li class="toctree-l2"><a class="reference internal" href="The_Four_Operations.html">The Four Fundamental Operations of Definite Action</a></li>
1332 <li class="toctree-l2"><a class="reference internal" href="Derivatives_of_Regular_Expressions.html">∂RE</a></li>
1333 </ul>
1334 </li>
1335 </ul>
1336
1337 <div class="relations">
1338 <h3>Related Topics</h3>
1339 <ul>
1340   <li><a href="../index.html">Documentation overview</a><ul>
1341   <li><a href="index.html">Essays about Programming in Joy</a><ul>
1342       <li>Previous: <a href="Recursion_Combinators.html" title="previous chapter">Recursion Combinators</a></li>
1343       <li>Next: <a href="Treestep.html" title="next chapter">Treating Trees II: <code class="docutils literal notranslate"><span class="pre">treestep</span></code></a></li>
1344   </ul></li>
1345   </ul></li>
1346 </ul>
1347 </div>
1348 <div id="searchbox" style="display: none" role="search">
1349   <h3 id="searchlabel">Quick search</h3>
1350     <div class="searchformwrapper">
1351     <form class="search" action="../search.html" method="get">
1352       <input type="text" name="q" aria-labelledby="searchlabel" autocomplete="off" autocorrect="off" autocapitalize="off" spellcheck="false"/>
1353       <input type="submit" value="Go" />
1354     </form>
1355     </div>
1356 </div>
1357 <script>$('#searchbox').show(0);</script>
1358
1359
1360
1361
1362
1363
1364
1365
1366         </div>
1367       </div>
1368       <div class="clearer"></div>
1369     </div>
1370     <div class="footer" role="contentinfo">
1371 <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/">
1372 <img alt="Creative Commons License" style="border-width:0" src="https://i.creativecommons.org/l/by-nc-sa/4.0/88x31.png" />
1373 </a>
1374 <br />
1375 <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>.
1376       Created using <a href="http://sphinx-doc.org/">Sphinx</a> 4.3.0.
1377     </div>
1378
1379   </body>
1380 </html>