2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
3 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
5 <html xmlns="http://www.w3.org/1999/xhtml">
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 II: treestep — 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="Using x to Generate Values" href="Generator_Programs.html" />
20 <link rel="prev" title="Treating Trees I: Ordered Binary Trees" href="Ordered_Binary_Trees.html" />
22 <link rel="stylesheet" href="../_static/custom.css" type="text/css" />
25 <meta name="viewport" content="width=device-width, initial-scale=0.9, maximum-scale=0.9" />
30 <div class="document">
31 <div class="documentwrapper">
32 <div class="bodywrapper">
33 <div class="body" role="main">
35 <div class="section" id="treating-trees-ii-treestep">
36 <h1>Treating Trees II: <code class="docutils literal notranslate"><span class="pre">treestep</span></code><a class="headerlink" href="#treating-trees-ii-treestep" title="Permalink to this headline">¶</a></h1>
37 <p>Let’s consider a tree structure, similar to one described <a class="reference external" href="https://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf">“Why
38 functional programming matters” by John
40 that consists of a node value followed by zero or more child trees. (The
41 asterisk is meant to indicate the <a class="reference external" href="https://en.wikipedia.org/wiki/Kleene_star">Kleene
43 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">tree</span> <span class="o">=</span> <span class="p">[]</span> <span class="o">|</span> <span class="p">[</span><span class="n">node</span> <span class="n">tree</span><span class="o">*</span><span class="p">]</span>
46 <p>In the spirit of <code class="docutils literal notranslate"><span class="pre">step</span></code> we are going to define a combinator
47 <code class="docutils literal notranslate"><span class="pre">treestep</span></code> which expects a tree and three additional items: a
48 base-case function <code class="docutils literal notranslate"><span class="pre">[B]</span></code>, and two quoted programs <code class="docutils literal notranslate"><span class="pre">[N]</span></code> and <code class="docutils literal notranslate"><span class="pre">[C]</span></code>.</p>
49 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">tree</span> <span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="p">[</span><span class="n">N</span><span class="p">]</span> <span class="p">[</span><span class="n">C</span><span class="p">]</span> <span class="n">treestep</span>
52 <p>If the current tree node is empty then just execute <code class="docutils literal notranslate"><span class="pre">B</span></code>:</p>
53 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span> <span class="p">[]</span> <span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="p">[</span><span class="n">N</span><span class="p">]</span> <span class="p">[</span><span class="n">C</span><span class="p">]</span> <span class="n">treestep</span>
54 <span class="o">---------------------------</span>
55 <span class="p">[]</span> <span class="n">B</span>
58 <p>Otherwise, evaluate <code class="docutils literal notranslate"><span class="pre">N</span></code> on the node value, <code class="docutils literal notranslate"><span class="pre">map</span></code> the whole function
59 (abbreviated here as <code class="docutils literal notranslate"><span class="pre">K</span></code>) over the child trees recursively, and then
60 combine the result with <code class="docutils literal notranslate"><span class="pre">C</span></code>.</p>
61 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span> <span class="p">[</span><span class="n">node</span> <span class="n">tree</span><span class="o">*</span><span class="p">]</span> <span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="p">[</span><span class="n">N</span><span class="p">]</span> <span class="p">[</span><span class="n">C</span><span class="p">]</span> <span class="n">treestep</span>
62 <span class="o">---------------------------------------</span> <span class="n">w</span><span class="o">/</span> <span class="n">K</span> <span class="o">==</span> <span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="p">[</span><span class="n">N</span><span class="p">]</span> <span class="p">[</span><span class="n">C</span><span class="p">]</span> <span class="n">treestep</span>
63 <span class="n">node</span> <span class="n">N</span> <span class="p">[</span><span class="n">tree</span><span class="o">*</span><span class="p">]</span> <span class="p">[</span><span class="n">K</span><span class="p">]</span> <span class="nb">map</span> <span class="n">C</span>
66 <p>(Later on we’ll experiment with making <code class="docutils literal notranslate"><span class="pre">map</span></code> part of <code class="docutils literal notranslate"><span class="pre">C</span></code> so you can
67 use other combinators.)</p>
68 <div class="section" id="derive-the-recursive-function">
69 <h2>Derive the recursive function.<a class="headerlink" href="#derive-the-recursive-function" title="Permalink to this headline">¶</a></h2>
70 <p>We can begin to derive it by finding the <code class="docutils literal notranslate"><span class="pre">ifte</span></code> stage that <code class="docutils literal notranslate"><span class="pre">genrec</span></code>
72 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">K</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">B</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>
73 <span class="o">==</span> <span class="p">[</span><span class="ow">not</span><span class="p">]</span> <span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="p">[</span><span class="n">R0</span> <span class="p">[</span><span class="n">K</span><span class="p">]</span> <span class="n">R1</span><span class="p">]</span> <span class="n">ifte</span>
76 <p>So we just have to derive <code class="docutils literal notranslate"><span class="pre">J</span></code>:</p>
77 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">J</span> <span class="o">==</span> <span class="n">R0</span> <span class="p">[</span><span class="n">K</span><span class="p">]</span> <span class="n">R1</span>
80 <p>The behavior of <code class="docutils literal notranslate"><span class="pre">J</span></code> is to accept a (non-empty) tree node and arrive at
81 the desired outcome.</p>
82 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span> <span class="p">[</span><span class="n">node</span> <span class="n">tree</span><span class="o">*</span><span class="p">]</span> <span class="n">J</span>
83 <span class="o">------------------------------</span>
84 <span class="n">node</span> <span class="n">N</span> <span class="p">[</span><span class="n">tree</span><span class="o">*</span><span class="p">]</span> <span class="p">[</span><span class="n">K</span><span class="p">]</span> <span class="nb">map</span> <span class="n">C</span>
87 <p>So <code class="docutils literal notranslate"><span class="pre">J</span></code> will have some form like:</p>
88 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">J</span> <span class="o">==</span> <span class="o">...</span> <span class="p">[</span><span class="n">N</span><span class="p">]</span> <span class="o">...</span> <span class="p">[</span><span class="n">K</span><span class="p">]</span> <span class="o">...</span> <span class="p">[</span><span class="n">C</span><span class="p">]</span> <span class="o">...</span>
91 <p>Let’s dive in. First, unquote the node and <code class="docutils literal notranslate"><span class="pre">dip</span></code> <code class="docutils literal notranslate"><span class="pre">N</span></code>.</p>
92 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">node</span> <span class="n">tree</span><span class="o">*</span><span class="p">]</span> <span class="n">uncons</span> <span class="p">[</span><span class="n">N</span><span class="p">]</span> <span class="n">dip</span>
93 <span class="n">node</span> <span class="p">[</span><span class="n">tree</span><span class="o">*</span><span class="p">]</span> <span class="p">[</span><span class="n">N</span><span class="p">]</span> <span class="n">dip</span>
94 <span class="n">node</span> <span class="n">N</span> <span class="p">[</span><span class="n">tree</span><span class="o">*</span><span class="p">]</span>
97 <p>Next, <code class="docutils literal notranslate"><span class="pre">map</span></code> <code class="docutils literal notranslate"><span class="pre">K</span></code> over the child trees and combine with <code class="docutils literal notranslate"><span class="pre">C</span></code>.</p>
98 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">node</span> <span class="n">N</span> <span class="p">[</span><span class="n">tree</span><span class="o">*</span><span class="p">]</span> <span class="p">[</span><span class="n">K</span><span class="p">]</span> <span class="nb">map</span> <span class="n">C</span>
99 <span class="n">node</span> <span class="n">N</span> <span class="p">[</span><span class="n">tree</span><span class="o">*</span><span class="p">]</span> <span class="p">[</span><span class="n">K</span><span class="p">]</span> <span class="nb">map</span> <span class="n">C</span>
100 <span class="n">node</span> <span class="n">N</span> <span class="p">[</span><span class="n">K</span><span class="o">.</span><span class="n">tree</span><span class="o">*</span><span class="p">]</span> <span class="n">C</span>
104 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">J</span> <span class="o">==</span> <span class="n">uncons</span> <span class="p">[</span><span class="n">N</span><span class="p">]</span> <span class="n">dip</span> <span class="p">[</span><span class="n">K</span><span class="p">]</span> <span class="nb">map</span> <span class="n">C</span>
107 <p>Plug it in and convert to <code class="docutils literal notranslate"><span class="pre">genrec</span></code>:</p>
108 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">K</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">B</span><span class="p">]</span> <span class="p">[</span><span class="n">J</span> <span class="p">]</span> <span class="n">ifte</span>
109 <span class="o">==</span> <span class="p">[</span><span class="ow">not</span><span class="p">]</span> <span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="p">[</span><span class="n">uncons</span> <span class="p">[</span><span class="n">N</span><span class="p">]</span> <span class="n">dip</span> <span class="p">[</span><span class="n">K</span><span class="p">]</span> <span class="nb">map</span> <span class="n">C</span><span class="p">]</span> <span class="n">ifte</span>
110 <span class="o">==</span> <span class="p">[</span><span class="ow">not</span><span class="p">]</span> <span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="p">[</span><span class="n">uncons</span> <span class="p">[</span><span class="n">N</span><span class="p">]</span> <span class="n">dip</span><span class="p">]</span> <span class="p">[</span><span class="nb">map</span> <span class="n">C</span><span class="p">]</span> <span class="n">genrec</span>
114 <div class="section" id="extract-the-givens-to-parameterize-the-program">
115 <h2>Extract the givens to parameterize the program.<a class="headerlink" href="#extract-the-givens-to-parameterize-the-program" title="Permalink to this headline">¶</a></h2>
116 <p>Working backwards:</p>
117 <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">B</span><span class="p">]</span> <span class="p">[</span><span class="n">uncons</span> <span class="p">[</span><span class="n">N</span><span class="p">]</span> <span class="n">dip</span><span class="p">]</span> <span class="p">[</span><span class="nb">map</span> <span class="n">C</span><span class="p">]</span> <span class="n">genrec</span>
118 <span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="p">[</span><span class="ow">not</span><span class="p">]</span> <span class="n">swap</span> <span class="p">[</span><span class="n">uncons</span> <span class="p">[</span><span class="n">N</span><span class="p">]</span> <span class="n">dip</span><span class="p">]</span> <span class="p">[</span><span class="nb">map</span> <span class="n">C</span><span class="p">]</span> <span class="n">genrec</span>
119 <span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="p">[</span><span class="n">uncons</span> <span class="p">[</span><span class="n">N</span><span class="p">]</span> <span class="n">dip</span><span class="p">]</span> <span class="p">[[</span><span class="ow">not</span><span class="p">]</span> <span class="n">swap</span><span class="p">]</span> <span class="n">dip</span> <span class="p">[</span><span class="nb">map</span> <span class="n">C</span><span class="p">]</span> <span class="n">genrec</span>
120 <span class="o">^^^^^^^^^^^^^^^^</span>
121 <span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="p">[[</span><span class="n">N</span><span class="p">]</span> <span class="n">dip</span><span class="p">]</span> <span class="p">[</span><span class="n">uncons</span><span class="p">]</span> <span class="n">swoncat</span> <span class="p">[[</span><span class="ow">not</span><span class="p">]</span> <span class="n">swap</span><span class="p">]</span> <span class="n">dip</span> <span class="p">[</span><span class="nb">map</span> <span class="n">C</span><span class="p">]</span> <span class="n">genrec</span>
122 <span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="p">[</span><span class="n">N</span><span class="p">]</span> <span class="p">[</span><span class="n">dip</span><span class="p">]</span> <span class="n">cons</span> <span class="p">[</span><span class="n">uncons</span><span class="p">]</span> <span class="n">swoncat</span> <span class="p">[[</span><span class="ow">not</span><span class="p">]</span> <span class="n">swap</span><span class="p">]</span> <span class="n">dip</span> <span class="p">[</span><span class="nb">map</span> <span class="n">C</span><span class="p">]</span> <span class="n">genrec</span>
123 <span class="o">^^^^^^^^^^^^^^^^^^^^^^^^^^^</span>
126 <p>Extract a couple of auxiliary definitions:</p>
127 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">TS</span><span class="o">.</span><span class="mi">0</span> <span class="o">==</span> <span class="p">[[</span><span class="ow">not</span><span class="p">]</span> <span class="n">swap</span><span class="p">]</span> <span class="n">dip</span>
128 <span class="n">TS</span><span class="o">.</span><span class="mi">1</span> <span class="o">==</span> <span class="p">[</span><span class="n">dip</span><span class="p">]</span> <span class="n">cons</span> <span class="p">[</span><span class="n">uncons</span><span class="p">]</span> <span class="n">swoncat</span>
131 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="p">[</span><span class="n">N</span><span class="p">]</span> <span class="n">TS</span><span class="o">.</span><span class="mi">1</span> <span class="n">TS</span><span class="o">.</span><span class="mi">0</span> <span class="p">[</span><span class="nb">map</span> <span class="n">C</span><span class="p">]</span> <span class="n">genrec</span>
132 <span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="p">[</span><span class="n">N</span><span class="p">]</span> <span class="p">[</span><span class="nb">map</span> <span class="n">C</span><span class="p">]</span> <span class="p">[</span><span class="n">TS</span><span class="o">.</span><span class="mi">1</span> <span class="n">TS</span><span class="o">.</span><span class="mi">0</span><span class="p">]</span> <span class="n">dip</span> <span class="n">genrec</span>
133 <span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="p">[</span><span class="n">N</span><span class="p">]</span> <span class="p">[</span><span class="n">C</span><span class="p">]</span> <span class="p">[</span><span class="nb">map</span><span class="p">]</span> <span class="n">swoncat</span> <span class="p">[</span><span class="n">TS</span><span class="o">.</span><span class="mi">1</span> <span class="n">TS</span><span class="o">.</span><span class="mi">0</span><span class="p">]</span> <span class="n">dip</span> <span class="n">genrec</span>
136 <p>The givens are all to the left so we have our definition.</p>
137 <div class="section" id="alternate-extract-the-givens-to-parameterize-the-program">
138 <h3>(alternate) Extract the givens to parameterize the program.<a class="headerlink" href="#alternate-extract-the-givens-to-parameterize-the-program" title="Permalink to this headline">¶</a></h3>
139 <p>Working backwards:</p>
140 <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">B</span><span class="p">]</span> <span class="p">[</span><span class="n">uncons</span> <span class="p">[</span><span class="n">N</span><span class="p">]</span> <span class="n">dip</span><span class="p">]</span> <span class="p">[</span><span class="nb">map</span> <span class="n">C</span><span class="p">]</span> <span class="n">genrec</span>
141 <span class="p">[</span><span class="ow">not</span><span class="p">]</span> <span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="p">[</span><span class="n">N</span><span class="p">]</span> <span class="p">[</span><span class="n">dip</span><span class="p">]</span> <span class="n">cons</span> <span class="p">[</span><span class="n">uncons</span><span class="p">]</span> <span class="n">swoncat</span> <span class="p">[</span><span class="nb">map</span> <span class="n">C</span><span class="p">]</span> <span class="n">genrec</span>
142 <span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="p">[</span><span class="n">N</span><span class="p">]</span> <span class="p">[</span><span class="ow">not</span><span class="p">]</span> <span class="n">roll</span><span class="o">></span> <span class="p">[</span><span class="n">dip</span><span class="p">]</span> <span class="n">cons</span> <span class="p">[</span><span class="n">uncons</span><span class="p">]</span> <span class="n">swoncat</span> <span class="p">[</span><span class="nb">map</span> <span class="n">C</span><span class="p">]</span> <span class="n">genrec</span>
143 <span class="o">^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^</span>
148 <div class="section" id="define-treestep">
149 <h2>Define <code class="docutils literal notranslate"><span class="pre">treestep</span></code><a class="headerlink" href="#define-treestep" title="Permalink to this headline">¶</a></h2>
150 <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>
153 <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">'''</span>
155 <span class="s1"> _treestep_0 == [[not] swap] dip</span>
156 <span class="s1"> _treestep_1 == [dip] cons [uncons] swoncat</span>
157 <span class="s1"> treegrind == [_treestep_1 _treestep_0] dip genrec</span>
158 <span class="s1"> treestep == [map] swoncat treegrind</span>
160 <span class="s1">'''</span><span class="p">,</span> <span class="n">D</span><span class="p">)</span>
164 <div class="section" id="examples">
165 <h2>Examples<a class="headerlink" href="#examples" title="Permalink to this headline">¶</a></h2>
166 <p>Consider trees, the nodes of which are integers. We can find the sum of
167 all nodes in a tree with this function:</p>
168 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">sumtree</span> <span class="o">==</span> <span class="p">[</span><span class="n">pop</span> <span class="mi">0</span><span class="p">]</span> <span class="p">[]</span> <span class="p">[</span><span class="nb">sum</span> <span class="o">+</span><span class="p">]</span> <span class="n">treestep</span>
171 <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">'sumtree == [pop 0] [] [sum +] treestep'</span><span class="p">)</span>
174 <p>Running this function on an empty tree value gives zero:</p>
175 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span> <span class="p">[]</span> <span class="p">[</span><span class="n">pop</span> <span class="mi">0</span><span class="p">]</span> <span class="p">[]</span> <span class="p">[</span><span class="nb">sum</span> <span class="o">+</span><span class="p">]</span> <span class="n">treestep</span>
176 <span class="o">------------------------------------</span>
177 <span class="mi">0</span>
180 <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">'[] sumtree'</span><span class="p">)</span> <span class="c1"># Empty tree.</span>
183 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">0</span>
186 <p>Running it on a non-empty node:</p>
187 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">n</span> <span class="n">tree</span><span class="o">*</span><span class="p">]</span> <span class="p">[</span><span class="n">pop</span> <span class="mi">0</span><span class="p">]</span> <span class="p">[]</span> <span class="p">[</span><span class="nb">sum</span> <span class="o">+</span><span class="p">]</span> <span class="n">treestep</span>
188 <span class="n">n</span> <span class="p">[</span><span class="n">tree</span><span class="o">*</span><span class="p">]</span> <span class="p">[[</span><span class="n">pop</span> <span class="mi">0</span><span class="p">]</span> <span class="p">[]</span> <span class="p">[</span><span class="nb">sum</span> <span class="o">+</span><span class="p">]</span> <span class="n">treestep</span><span class="p">]</span> <span class="nb">map</span> <span class="nb">sum</span> <span class="o">+</span>
189 <span class="n">n</span> <span class="p">[</span> <span class="o">...</span> <span class="p">]</span> <span class="nb">sum</span> <span class="o">+</span>
190 <span class="n">n</span> <span class="n">m</span> <span class="o">+</span>
191 <span class="n">n</span><span class="o">+</span><span class="n">m</span>
194 <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">'[23] sumtree'</span><span class="p">)</span> <span class="c1"># No child trees.</span>
197 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">23</span>
200 <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">'[23 []] sumtree'</span><span class="p">)</span> <span class="c1"># Child tree, empty.</span>
203 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">23</span>
206 <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">'[23 [2 [4]] [3]] sumtree'</span><span class="p">)</span> <span class="c1"># Non-empty child trees.</span>
209 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">32</span>
212 <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">'[23 [2 [8] [9]] [3] [4 []]] sumtree'</span><span class="p">)</span> <span class="c1"># Etc...</span>
215 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">49</span>
218 <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">'[23 [2 [8] [9]] [3] [4 []]] [pop 0] [] [cons sum] treestep'</span><span class="p">)</span> <span class="c1"># Alternate "spelling".</span>
221 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">49</span>
224 <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">'[23 [2 [8] [9]] [3] [4 []]] [] [pop 23] [cons] treestep'</span><span class="p">)</span> <span class="c1"># Replace each node.</span>
227 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="mi">23</span> <span class="p">[</span><span class="mi">23</span> <span class="p">[</span><span class="mi">23</span><span class="p">]</span> <span class="p">[</span><span class="mi">23</span><span class="p">]]</span> <span class="p">[</span><span class="mi">23</span><span class="p">]</span> <span class="p">[</span><span class="mi">23</span> <span class="p">[]]]</span>
230 <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">'[23 [2 [8] [9]] [3] [4 []]] [] [pop 1] [cons] treestep'</span><span class="p">)</span>
233 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="mi">1</span> <span class="p">[</span><span class="mi">1</span> <span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="p">[</span><span class="mi">1</span><span class="p">]]</span> <span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="p">[</span><span class="mi">1</span> <span class="p">[]]]</span>
236 <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">'[23 [2 [8] [9]] [3] [4 []]] [] [pop 1] [cons] treestep sumtree'</span><span class="p">)</span>
239 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">6</span>
242 <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">'[23 [2 [8] [9]] [3] [4 []]] [pop 0] [pop 1] [sum +] treestep'</span><span class="p">)</span> <span class="c1"># Combine replace and sum into one function.</span>
245 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">6</span>
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">'[4 [3 [] [7]]] [pop 0] [pop 1] [sum +] treestep'</span><span class="p">)</span> <span class="c1"># Combine replace and sum into one function.</span>
251 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">3</span>
255 <div class="section" id="redefining-the-ordered-binary-tree-in-terms-of-treestep">
256 <h2>Redefining the Ordered Binary Tree in terms of <code class="docutils literal notranslate"><span class="pre">treestep</span></code>.<a class="headerlink" href="#redefining-the-ordered-binary-tree-in-terms-of-treestep" title="Permalink to this headline">¶</a></h2>
257 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">Tree</span> <span class="o">=</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="p">]</span> <span class="n">left</span> <span class="n">right</span><span class="p">]</span>
260 <p>What kind of functions can we write for this with our <code class="docutils literal notranslate"><span class="pre">treestep</span></code>?</p>
261 <p>The pattern for processing a non-empty node is:</p>
262 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">node</span> <span class="n">N</span> <span class="p">[</span><span class="n">tree</span><span class="o">*</span><span class="p">]</span> <span class="p">[</span><span class="n">K</span><span class="p">]</span> <span class="nb">map</span> <span class="n">C</span>
265 <p>Plugging in our BTree structure:</p>
266 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">key</span> <span class="n">value</span><span class="p">]</span> <span class="n">N</span> <span class="p">[</span><span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">K</span><span class="p">]</span> <span class="nb">map</span> <span class="n">C</span>
269 <div class="section" id="traversal">
270 <h3>Traversal<a class="headerlink" href="#traversal" title="Permalink to this headline">¶</a></h3>
271 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">key</span> <span class="n">value</span><span class="p">]</span> <span class="n">first</span> <span class="p">[</span><span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">K</span><span class="p">]</span> <span class="nb">map</span> <span class="n">i</span>
272 <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">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">K</span><span class="p">]</span> <span class="nb">map</span> <span class="n">i</span>
273 <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">K</span><span class="p">]</span> <span class="nb">map</span> <span class="n">i</span>
274 <span class="n">key</span> <span class="p">[</span><span class="n">lkey</span> <span class="n">rkey</span> <span class="p">]</span> <span class="n">i</span>
275 <span class="n">key</span> <span class="n">lkey</span> <span class="n">rkey</span>
278 <p>This doesn’t quite work:</p>
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">'[[3 0] [[2 0] [][]] [[9 0] [[5 0] [[4 0] [][]] [[8 0] [[6 0] [] [[7 0] [][]]][]]][]]] ["B"] [first] [i] treestep'</span><span class="p">)</span>
282 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">3</span> <span class="s1">'B'</span> <span class="s1">'B'</span>
285 <p>Doesn’t work because <code class="docutils literal notranslate"><span class="pre">map</span></code> extracts the <code class="docutils literal notranslate"><span class="pre">first</span></code> item of whatever its
286 mapped function produces. We have to return a list, rather than
287 depositing our results directly on the stack.</p>
288 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">key</span> <span class="n">value</span><span class="p">]</span> <span class="n">N</span> <span class="p">[</span><span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">K</span><span class="p">]</span> <span class="nb">map</span> <span class="n">C</span>
290 <span class="p">[</span><span class="n">key</span> <span class="n">value</span><span class="p">]</span> <span class="n">first</span> <span class="p">[</span><span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">K</span><span class="p">]</span> <span class="nb">map</span> <span class="n">flatten</span> <span class="n">cons</span>
291 <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">K</span><span class="p">]</span> <span class="nb">map</span> <span class="n">flatten</span> <span class="n">cons</span>
292 <span class="n">key</span> <span class="p">[[</span><span class="n">lk</span><span class="p">]</span> <span class="p">[</span><span class="n">rk</span><span class="p">]</span> <span class="p">]</span> <span class="n">flatten</span> <span class="n">cons</span>
293 <span class="n">key</span> <span class="p">[</span> <span class="n">lk</span> <span class="n">rk</span> <span class="p">]</span> <span class="n">cons</span>
294 <span class="p">[</span><span class="n">key</span> <span class="n">lk</span> <span class="n">rk</span> <span class="p">]</span>
298 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[]</span> <span class="p">[</span><span class="n">first</span><span class="p">]</span> <span class="p">[</span><span class="n">flatten</span> <span class="n">cons</span><span class="p">]</span> <span class="n">treestep</span>
301 <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">'[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]] [] [first] [flatten cons] treestep'</span><span class="p">)</span>
304 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="mi">3</span> <span class="mi">2</span> <span class="mi">9</span> <span class="mi">5</span> <span class="mi">4</span> <span class="mi">8</span> <span class="mi">6</span> <span class="mi">7</span><span class="p">]</span>
309 <div class="section" id="in-order-traversal">
310 <h3>In-order traversal<a class="headerlink" href="#in-order-traversal" title="Permalink to this headline">¶</a></h3>
312 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">key</span> <span class="p">[[</span><span class="n">lk</span><span class="p">]</span> <span class="p">[</span><span class="n">rk</span><span class="p">]]</span> <span class="n">C</span>
313 <span class="n">key</span> <span class="p">[[</span><span class="n">lk</span><span class="p">]</span> <span class="p">[</span><span class="n">rk</span><span class="p">]]</span> <span class="n">i</span>
314 <span class="n">key</span> <span class="p">[</span><span class="n">lk</span><span class="p">]</span> <span class="p">[</span><span class="n">rk</span><span class="p">]</span> <span class="n">roll</span><span class="o"><</span>
315 <span class="p">[</span><span class="n">lk</span><span class="p">]</span> <span class="p">[</span><span class="n">rk</span><span class="p">]</span> <span class="n">key</span> <span class="n">swons</span> <span class="n">concat</span>
316 <span class="p">[</span><span class="n">lk</span><span class="p">]</span> <span class="p">[</span><span class="n">key</span> <span class="n">rk</span><span class="p">]</span> <span class="n">concat</span>
317 <span class="p">[</span><span class="n">lk</span> <span class="n">key</span> <span class="n">rk</span><span class="p">]</span>
321 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[]</span> <span class="p">[</span><span class="n">i</span> <span class="n">roll</span><span class="o"><</span> <span class="n">swons</span> <span class="n">concat</span><span class="p">]</span> <span class="p">[</span><span class="n">first</span><span class="p">]</span> <span class="n">treestep</span>
324 <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">'[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]] [] [uncons pop] [i roll< swons concat] treestep'</span><span class="p">)</span>
327 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="mi">2</span> <span class="mi">3</span> <span class="mi">4</span> <span class="mi">5</span> <span class="mi">6</span> <span class="mi">7</span> <span class="mi">8</span> <span class="mi">9</span><span class="p">]</span>
332 <div class="section" id="with-treegrind">
333 <h2>With <code class="docutils literal notranslate"><span class="pre">treegrind</span></code>?<a class="headerlink" href="#with-treegrind" title="Permalink to this headline">¶</a></h2>
334 <p>The <code class="docutils literal notranslate"><span class="pre">treegrind</span></code> function doesn’t include the <code class="docutils literal notranslate"><span class="pre">map</span></code> combinator, so
335 the <code class="docutils literal notranslate"><span class="pre">[C]</span></code> function must arrange to use some combinator on the quoted
336 recursive copy <code class="docutils literal notranslate"><span class="pre">[K]</span></code>. With this function, the pattern for processing a
337 non-empty node is:</p>
338 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">node</span> <span class="n">N</span> <span class="p">[</span><span class="n">tree</span><span class="o">*</span><span class="p">]</span> <span class="p">[</span><span class="n">K</span><span class="p">]</span> <span class="n">C</span>
341 <p>Plugging in our BTree structure:</p>
342 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">key</span> <span class="n">value</span><span class="p">]</span> <span class="n">N</span> <span class="p">[</span><span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">K</span><span class="p">]</span> <span class="n">C</span>
345 <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">'[["key" "value"] ["left"] ["right"] ] ["B"] ["N"] ["C"] treegrind'</span><span class="p">)</span>
348 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="s1">'key'</span> <span class="s1">'value'</span><span class="p">]</span> <span class="s1">'N'</span> <span class="p">[[</span><span class="s1">'left'</span><span class="p">]</span> <span class="p">[</span><span class="s1">'right'</span><span class="p">]]</span> <span class="p">[[</span><span class="ow">not</span><span class="p">]</span> <span class="p">[</span><span class="s1">'B'</span><span class="p">]</span> <span class="p">[</span><span class="n">uncons</span> <span class="p">[</span><span class="s1">'N'</span><span class="p">]</span> <span class="n">dip</span><span class="p">]</span> <span class="p">[</span><span class="s1">'C'</span><span class="p">]</span> <span class="n">genrec</span><span class="p">]</span> <span class="s1">'C'</span>
352 <div class="section" id="treegrind-with-step">
353 <h2><code class="docutils literal notranslate"><span class="pre">treegrind</span></code> with <code class="docutils literal notranslate"><span class="pre">step</span></code><a class="headerlink" href="#treegrind-with-step" title="Permalink to this headline">¶</a></h2>
354 <p>Iteration through the nodes</p>
355 <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">'[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]] [pop] ["N"] [step] treegrind'</span><span class="p">)</span>
358 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="mi">3</span> <span class="mi">0</span><span class="p">]</span> <span class="s1">'N'</span> <span class="p">[</span><span class="mi">2</span> <span class="mi">0</span><span class="p">]</span> <span class="s1">'N'</span> <span class="p">[</span><span class="mi">9</span> <span class="mi">0</span><span class="p">]</span> <span class="s1">'N'</span> <span class="p">[</span><span class="mi">5</span> <span class="mi">0</span><span class="p">]</span> <span class="s1">'N'</span> <span class="p">[</span><span class="mi">4</span> <span class="mi">0</span><span class="p">]</span> <span class="s1">'N'</span> <span class="p">[</span><span class="mi">8</span> <span class="mi">0</span><span class="p">]</span> <span class="s1">'N'</span> <span class="p">[</span><span class="mi">6</span> <span class="mi">0</span><span class="p">]</span> <span class="s1">'N'</span> <span class="p">[</span><span class="mi">7</span> <span class="mi">0</span><span class="p">]</span> <span class="s1">'N'</span>
361 <p>Sum the nodes’ keys.</p>
362 <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">'0 [[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]] [pop] [first +] [step] treegrind'</span><span class="p">)</span>
365 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">44</span>
368 <p>Rebuild the tree using <code class="docutils literal notranslate"><span class="pre">map</span></code> (imitating <code class="docutils literal notranslate"><span class="pre">treestep</span></code>.)</p>
369 <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">'[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]] [] [[100 +] infra] [map cons] treegrind'</span><span class="p">)</span>
372 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[[</span><span class="mi">103</span> <span class="mi">0</span><span class="p">]</span> <span class="p">[[</span><span class="mi">102</span> <span class="mi">0</span><span class="p">]</span> <span class="p">[]</span> <span class="p">[]]</span> <span class="p">[[</span><span class="mi">109</span> <span class="mi">0</span><span class="p">]</span> <span class="p">[[</span><span class="mi">105</span> <span class="mi">0</span><span class="p">]</span> <span class="p">[[</span><span class="mi">104</span> <span class="mi">0</span><span class="p">]</span> <span class="p">[]</span> <span class="p">[]]</span> <span class="p">[[</span><span class="mi">108</span> <span class="mi">0</span><span class="p">]</span> <span class="p">[[</span><span class="mi">106</span> <span class="mi">0</span><span class="p">]</span> <span class="p">[]</span> <span class="p">[[</span><span class="mi">107</span> <span class="mi">0</span><span class="p">]</span> <span class="p">[]</span> <span class="p">[]]]</span> <span class="p">[]]]</span> <span class="p">[]]]</span>
376 <div class="section" id="do-we-have-the-flexibility-to-reimplement-tree-get">
377 <h2>Do we have the flexibility to reimplement <code class="docutils literal notranslate"><span class="pre">Tree-get</span></code>?<a class="headerlink" href="#do-we-have-the-flexibility-to-reimplement-tree-get" title="Permalink to this headline">¶</a></h2>
378 <p>I think we do:</p>
379 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="p">[</span><span class="n">N</span><span class="p">]</span> <span class="p">[</span><span class="n">C</span><span class="p">]</span> <span class="n">treegrind</span>
382 <p>We’ll start by saying that the base-case (the key is not in the tree) is
383 user defined, and the per-node function is just the query key literal:</p>
384 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">B</span><span class="p">]</span> <span class="p">[</span><span class="n">query_key</span><span class="p">]</span> <span class="p">[</span><span class="n">C</span><span class="p">]</span> <span class="n">treegrind</span>
387 <p>This means we just have to define <code class="docutils literal notranslate"><span class="pre">C</span></code> from:</p>
388 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">key</span> <span class="n">value</span><span class="p">]</span> <span class="n">query_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">K</span><span class="p">]</span> <span class="n">C</span>
391 <p>Let’s try <code class="docutils literal notranslate"><span class="pre">cmp</span></code>:</p>
392 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">C</span> <span class="o">==</span> <span class="n">P</span> <span class="p">[</span><span class="n">T</span><span class="o">></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"><</span><span class="p">]</span> <span class="nb">cmp</span>
394 <span class="p">[</span><span class="n">key</span> <span class="n">value</span><span class="p">]</span> <span class="n">query_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">K</span><span class="p">]</span> <span class="n">P</span> <span class="p">[</span><span class="n">T</span><span class="o">></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"><</span><span class="p">]</span> <span class="nb">cmp</span>
397 <div class="section" id="the-predicate-p">
398 <h3>The predicate <code class="docutils literal notranslate"><span class="pre">P</span></code><a class="headerlink" href="#the-predicate-p" title="Permalink to this headline">¶</a></h3>
399 <p>Seems pretty easy (we must preserve the value in case the keys are
401 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">key</span> <span class="n">value</span><span class="p">]</span> <span class="n">query_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">K</span><span class="p">]</span> <span class="n">P</span>
402 <span class="p">[</span><span class="n">key</span> <span class="n">value</span><span class="p">]</span> <span class="n">query_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">K</span><span class="p">]</span> <span class="n">roll</span><span class="o"><</span>
403 <span class="p">[</span><span class="n">key</span> <span class="n">value</span><span class="p">]</span> <span class="p">[</span><span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">K</span><span class="p">]</span> <span class="n">query_key</span> <span class="p">[</span><span class="n">roll</span><span class="o"><</span> <span class="n">uncons</span> <span class="n">swap</span><span class="p">]</span> <span class="n">dip</span>
405 <span class="p">[</span><span class="n">key</span> <span class="n">value</span><span class="p">]</span> <span class="p">[</span><span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">K</span><span class="p">]</span> <span class="n">roll</span><span class="o"><</span> <span class="n">uncons</span> <span class="n">swap</span> <span class="n">query_key</span>
406 <span class="p">[</span><span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">K</span><span class="p">]</span> <span class="p">[</span><span class="n">key</span> <span class="n">value</span><span class="p">]</span> <span class="n">uncons</span> <span class="n">swap</span> <span class="n">query_key</span>
407 <span class="p">[</span><span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">K</span><span class="p">]</span> <span class="n">key</span> <span class="p">[</span><span class="n">value</span><span class="p">]</span> <span class="n">swap</span> <span class="n">query_key</span>
408 <span class="p">[</span><span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">K</span><span class="p">]</span> <span class="p">[</span><span class="n">value</span><span class="p">]</span> <span class="n">key</span> <span class="n">query_key</span>
410 <span class="n">P</span> <span class="o">==</span> <span class="n">roll</span><span class="o"><</span> <span class="p">[</span><span class="n">roll</span><span class="o"><</span> <span class="n">uncons</span> <span class="n">swap</span><span class="p">]</span> <span class="n">dip</span>
413 <p>(Possibly with a swap at the end? Or just swap <code class="docutils literal notranslate"><span class="pre">T<</span></code> and <code class="docutils literal notranslate"><span class="pre">T></span></code>.)</p>
415 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">K</span><span class="p">]</span> <span class="p">[</span><span class="n">value</span><span class="p">]</span> <span class="n">key</span> <span class="n">query_key</span> <span class="p">[</span><span class="n">T</span><span class="o">></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"><</span><span class="p">]</span> <span class="nb">cmp</span>
418 <p>Becomes one of these three:</p>
419 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">K</span><span class="p">]</span> <span class="p">[</span><span class="n">value</span><span class="p">]</span> <span class="n">T</span><span class="o">></span>
420 <span class="p">[</span><span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">K</span><span class="p">]</span> <span class="p">[</span><span class="n">value</span><span class="p">]</span> <span class="n">E</span>
421 <span class="p">[</span><span class="n">left</span> <span class="n">right</span><span class="p">]</span> <span class="p">[</span><span class="n">K</span><span class="p">]</span> <span class="p">[</span><span class="n">value</span><span class="p">]</span> <span class="n">T</span><span class="o"><</span>
425 <div class="section" id="e">
426 <h3><code class="docutils literal notranslate"><span class="pre">E</span></code><a class="headerlink" href="#e" title="Permalink to this headline">¶</a></h3>
428 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">E</span> <span class="o">==</span> <span class="n">roll</span><span class="o">></span> <span class="n">popop</span> <span class="n">first</span>
432 <div class="section" id="t-and-t">
433 <h3><code class="docutils literal notranslate"><span class="pre">T<</span></code> and <code class="docutils literal notranslate"><span class="pre">T></span></code><a class="headerlink" href="#t-and-t" title="Permalink to this headline">¶</a></h3>
434 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">T</span><span class="o"><</span> <span class="o">==</span> <span class="n">pop</span> <span class="p">[</span><span class="n">first</span><span class="p">]</span> <span class="n">dip</span> <span class="n">i</span>
435 <span class="n">T</span><span class="o">></span> <span class="o">==</span> <span class="n">pop</span> <span class="p">[</span><span class="n">second</span><span class="p">]</span> <span class="n">dip</span> <span class="n">i</span>
440 <div class="section" id="putting-it-together">
441 <h2>Putting it together<a class="headerlink" href="#putting-it-together" title="Permalink to this headline">¶</a></h2>
442 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">T</span><span class="o">></span> <span class="o">==</span> <span class="n">pop</span> <span class="p">[</span><span class="n">first</span><span class="p">]</span> <span class="n">dip</span> <span class="n">i</span>
443 <span class="n">T</span><span class="o"><</span> <span class="o">==</span> <span class="n">pop</span> <span class="p">[</span><span class="n">second</span><span class="p">]</span> <span class="n">dip</span> <span class="n">i</span>
444 <span class="n">E</span> <span class="o">==</span> <span class="n">roll</span><span class="o">></span> <span class="n">popop</span> <span class="n">first</span>
445 <span class="n">P</span> <span class="o">==</span> <span class="n">roll</span><span class="o"><</span> <span class="p">[</span><span class="n">roll</span><span class="o"><</span> <span class="n">uncons</span> <span class="n">swap</span><span class="p">]</span> <span class="n">dip</span>
447 <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">P</span> <span class="p">[</span><span class="n">T</span><span class="o">></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"><</span><span class="p">]</span> <span class="nb">cmp</span><span class="p">]</span> <span class="n">treegrind</span>
450 <p>To me, that seems simpler than the <code class="docutils literal notranslate"><span class="pre">genrec</span></code> version.</p>
451 <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">'''</span>
453 <span class="s1"> T> == pop [first] dip i</span>
454 <span class="s1"> T< == pop [second] dip i</span>
455 <span class="s1"> E == roll> popop first</span>
456 <span class="s1"> P == roll< [roll< uncons swap] dip</span>
458 <span class="s1"> Tree-get == [P [T>] [E] [T<] cmp] treegrind</span>
460 <span class="s1">'''</span><span class="p">,</span> <span class="n">D</span><span class="p">)</span>
463 <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">'''</span><span class="se">\</span>
465 <span class="s1">[[3 13] [[2 12] [] []] [[9 19] [[5 15] [[4 14] [] []] [[8 18] [[6 16] [] [[7 17] [] []]] []]] []]]</span>
467 <span class="s1">[] [5] Tree-get</span>
469 <span class="s1">'''</span><span class="p">)</span>
472 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="mi">15</span>
475 <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">'''</span><span class="se">\</span>
477 <span class="s1">[[3 13] [[2 12] [] []] [[9 19] [[5 15] [[4 14] [] []] [[8 18] [[6 16] [] [[7 17] [] []]] []]] []]]</span>
479 <span class="s1">[pop "nope"] [25] Tree-get</span>
481 <span class="s1">'''</span><span class="p">)</span>
484 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="s1">'nope'</span>
494 <div class="sphinxsidebar" role="navigation" aria-label="main navigation">
495 <div class="sphinxsidebarwrapper">
496 <h3><a href="../index.html">Table Of Contents</a></h3>
498 <li><a class="reference internal" href="#">Treating Trees II: <code class="docutils literal notranslate"><span class="pre">treestep</span></code></a><ul>
499 <li><a class="reference internal" href="#derive-the-recursive-function">Derive the recursive function.</a></li>
500 <li><a class="reference internal" href="#extract-the-givens-to-parameterize-the-program">Extract the givens to parameterize the program.</a><ul>
501 <li><a class="reference internal" href="#alternate-extract-the-givens-to-parameterize-the-program">(alternate) Extract the givens to parameterize the program.</a></li>
504 <li><a class="reference internal" href="#define-treestep">Define <code class="docutils literal notranslate"><span class="pre">treestep</span></code></a></li>
505 <li><a class="reference internal" href="#examples">Examples</a></li>
506 <li><a class="reference internal" href="#redefining-the-ordered-binary-tree-in-terms-of-treestep">Redefining the Ordered Binary Tree in terms of <code class="docutils literal notranslate"><span class="pre">treestep</span></code>.</a><ul>
507 <li><a class="reference internal" href="#traversal">Traversal</a></li>
508 <li><a class="reference internal" href="#in-order-traversal">In-order traversal</a></li>
511 <li><a class="reference internal" href="#with-treegrind">With <code class="docutils literal notranslate"><span class="pre">treegrind</span></code>?</a></li>
512 <li><a class="reference internal" href="#treegrind-with-step"><code class="docutils literal notranslate"><span class="pre">treegrind</span></code> with <code class="docutils literal notranslate"><span class="pre">step</span></code></a></li>
513 <li><a class="reference internal" href="#do-we-have-the-flexibility-to-reimplement-tree-get">Do we have the flexibility to reimplement <code class="docutils literal notranslate"><span class="pre">Tree-get</span></code>?</a><ul>
514 <li><a class="reference internal" href="#the-predicate-p">The predicate <code class="docutils literal notranslate"><span class="pre">P</span></code></a></li>
515 <li><a class="reference internal" href="#e"><code class="docutils literal notranslate"><span class="pre">E</span></code></a></li>
516 <li><a class="reference internal" href="#t-and-t"><code class="docutils literal notranslate"><span class="pre">T<</span></code> and <code class="docutils literal notranslate"><span class="pre">T></span></code></a></li>
519 <li><a class="reference internal" href="#putting-it-together">Putting it together</a></li>
523 <div class="relations">
524 <h3>Related Topics</h3>
526 <li><a href="../index.html">Documentation overview</a><ul>
527 <li><a href="index.html">Essays about Programming in Joy</a><ul>
528 <li>Previous: <a href="Ordered_Binary_Trees.html" title="previous chapter">Treating Trees I: Ordered Binary Trees</a></li>
529 <li>Next: <a href="Generator_Programs.html" title="next chapter">Using <code class="docutils literal notranslate"><span class="pre">x</span></code> to Generate Values</a></li>
534 <div role="note" aria-label="source link">
536 <ul class="this-page-menu">
537 <li><a href="../_sources/notebooks/Treestep.rst.txt"
538 rel="nofollow">Show Source</a></li>
541 <div id="searchbox" style="display: none" role="search">
542 <h3>Quick search</h3>
543 <div class="searchformwrapper">
544 <form class="search" action="../search.html" method="get">
545 <input type="text" name="q" />
546 <input type="submit" value="Go" />
547 <input type="hidden" name="check_keywords" value="yes" />
548 <input type="hidden" name="area" value="default" />
552 <script type="text/javascript">$('#searchbox').show(0);</script>
555 <div class="clearer"></div>
557 <div class="footer" role="contentinfo">
558 <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/">
559 <img alt="Creative Commons License" style="border-width:0" src="https://i.creativecommons.org/l/by-nc-sa/4.0/88x31.png" />
562 <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>.
563 Created using <a href="http://sphinx-doc.org/">Sphinx</a> 1.7.3.