OSDN Git Service

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