docs/sphinx_docs/_build/html/notebooks/Zipper.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>Traversing Datastructures with Zippers &#8212; Thun 0.2.0 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="The Blissful Elegance of Typing Joy" href="Types.html" />
  20     <link rel="prev" title="Newton’s method" href="Newton-Raphson.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="traversing-datastructures-with-zippers">
  36 <h1>Traversing Datastructures with Zippers<a class="headerlink" href="#traversing-datastructures-with-zippers" title="Permalink to this headline">¶</a></h1>
  37 <p>This notebook is about using the “zipper” with joy datastructures. See
  38 the <a class="reference external" href="https://en.wikipedia.org/wiki/Zipper_%28data_structure%29">Zipper wikipedia
  39 entry</a> or
  40 the original paper: <a class="reference external" href="https://www.st.cs.uni-saarland.de/edu/seminare/2005/advanced-fp/docs/huet-zipper.pdf">“FUNCTIONAL PEARL The Zipper” by Gérard
  41 Huet</a></p>
  42 <p>Given a datastructure on the stack we can navigate through it, modify
  43 it, and rebuild it using the “zipper” technique.</p>
  44 <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">J</span><span class="p">,</span> <span class="n">V</span><span class="p">,</span> <span class="n">define</span>
  45 </pre></div>
  46 </div>
  47 <div class="section" id="trees">
  48 <h2>Trees<a class="headerlink" href="#trees" title="Permalink to this headline">¶</a></h2>
  49 <p>In Joypy there aren’t any complex datastructures, just ints, floats,
  50 strings, Symbols (strings that are names of functions) and sequences
  51 (aka lists, aka quoted literals, aka aggregates, etc…), but we can
  52 build
  53 <a class="reference external" href="https://en.wikipedia.org/wiki/Tree_%28data_structure%29">trees</a> out
  54 of sequences.</p>
  55 <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;[1 [2 [3 4 25 6] 7] 8]&#39;</span><span class="p">)</span>
  56 </pre></div>
  57 </div>
  58 <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">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">8</span><span class="p">]</span>
  59 </pre></div>
  60 </div>
  61 </div>
  62 <div class="section" id="zipper-in-joy">
  63 <h2>Zipper in Joy<a class="headerlink" href="#zipper-in-joy" title="Permalink to this headline">¶</a></h2>
  64 <p>Zippers work by keeping track of the current item, the already-seen
  65 items, and the yet-to-be seen items as you traverse a datastructure (the
  66 datastructure used to keep track of these items is the zipper.)</p>
  67 <p>In Joy we can do this with the following words:</p>
  68 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">z</span><span class="o">-</span><span class="n">down</span> <span class="o">==</span> <span class="p">[]</span> <span class="n">swap</span> <span class="n">uncons</span> <span class="n">swap</span>
  69 <span class="n">z</span><span class="o">-</span><span class="n">up</span> <span class="o">==</span> <span class="n">swons</span> <span class="n">swap</span> <span class="n">shunt</span>
  70 <span class="n">z</span><span class="o">-</span><span class="n">right</span> <span class="o">==</span> <span class="p">[</span><span class="n">swons</span><span class="p">]</span> <span class="n">cons</span> <span class="n">dip</span> <span class="n">uncons</span> <span class="n">swap</span>
  71 <span class="n">z</span><span class="o">-</span><span class="n">left</span> <span class="o">==</span> <span class="n">swons</span> <span class="p">[</span><span class="n">uncons</span> <span class="n">swap</span><span class="p">]</span> <span class="n">dip</span> <span class="n">swap</span>
  72 </pre></div>
  73 </div>
  74 <p>Let’s use them to change 25 into 625. The first time a word is used I
  75 show the trace so you can see how it works. If we were going to use
  76 these a lot it would make sense to write Python versions for efficiency,
  77 but see below.</p>
  78 <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;z-down == [] swap uncons swap&#39;</span><span class="p">)</span>
  79 <span class="n">define</span><span class="p">(</span><span class="s1">&#39;z-up == swons swap shunt&#39;</span><span class="p">)</span>
  80 <span class="n">define</span><span class="p">(</span><span class="s1">&#39;z-right == [swons] cons dip uncons swap&#39;</span><span class="p">)</span>
  81 <span class="n">define</span><span class="p">(</span><span class="s1">&#39;z-left == swons [uncons swap] dip swap&#39;</span><span class="p">)</span>
  82 </pre></div>
  83 </div>
  84 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">V</span><span class="p">(</span><span class="s1">&#39;[1 [2 [3 4 25 6] 7] 8] z-down&#39;</span><span class="p">)</span>
  85 </pre></div>
  86 </div>
  87 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>                          <span class="o">.</span> <span class="p">[</span><span class="mi">1</span> <span class="p">[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">8</span><span class="p">]</span> <span class="n">z</span><span class="o">-</span><span class="n">down</span>
  88    <span class="p">[</span><span class="mi">1</span> <span class="p">[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">8</span><span class="p">]</span> <span class="o">.</span> <span class="n">z</span><span class="o">-</span><span class="n">down</span>
  89    <span class="p">[</span><span class="mi">1</span> <span class="p">[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">8</span><span class="p">]</span> <span class="o">.</span> <span class="p">[]</span> <span class="n">swap</span> <span class="n">uncons</span> <span class="n">swap</span>
  90 <span class="p">[</span><span class="mi">1</span> <span class="p">[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">8</span><span class="p">]</span> <span class="p">[]</span> <span class="o">.</span> <span class="n">swap</span> <span class="n">uncons</span> <span class="n">swap</span>
  91 <span class="p">[]</span> <span class="p">[</span><span class="mi">1</span> <span class="p">[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">8</span><span class="p">]</span> <span class="o">.</span> <span class="n">uncons</span> <span class="n">swap</span>
  92 <span class="p">[]</span> <span class="mi">1</span> <span class="p">[[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">8</span><span class="p">]</span> <span class="o">.</span> <span class="n">swap</span>
  93 <span class="p">[]</span> <span class="p">[[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">8</span><span class="p">]</span> <span class="mi">1</span> <span class="o">.</span>
  94 </pre></div>
  95 </div>
  96 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">V</span><span class="p">(</span><span class="s1">&#39;[] [[2 [3 4 25 6] 7] 8] 1 z-right&#39;</span><span class="p">)</span>
  97 </pre></div>
  98 </div>
  99 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>                                  <span class="o">.</span> <span class="p">[]</span> <span class="p">[[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">8</span><span class="p">]</span> <span class="mi">1</span> <span class="n">z</span><span class="o">-</span><span class="n">right</span>
 100                                <span class="p">[]</span> <span class="o">.</span> <span class="p">[[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">8</span><span class="p">]</span> <span class="mi">1</span> <span class="n">z</span><span class="o">-</span><span class="n">right</span>
 101           <span class="p">[]</span> <span class="p">[[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">8</span><span class="p">]</span> <span class="o">.</span> <span class="mi">1</span> <span class="n">z</span><span class="o">-</span><span class="n">right</span>
 102         <span class="p">[]</span> <span class="p">[[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">8</span><span class="p">]</span> <span class="mi">1</span> <span class="o">.</span> <span class="n">z</span><span class="o">-</span><span class="n">right</span>
 103         <span class="p">[]</span> <span class="p">[[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">8</span><span class="p">]</span> <span class="mi">1</span> <span class="o">.</span> <span class="p">[</span><span class="n">swons</span><span class="p">]</span> <span class="n">cons</span> <span class="n">dip</span> <span class="n">uncons</span> <span class="n">swap</span>
 104 <span class="p">[]</span> <span class="p">[[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">8</span><span class="p">]</span> <span class="mi">1</span> <span class="p">[</span><span class="n">swons</span><span class="p">]</span> <span class="o">.</span> <span class="n">cons</span> <span class="n">dip</span> <span class="n">uncons</span> <span class="n">swap</span>
 105 <span class="p">[]</span> <span class="p">[[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">8</span><span class="p">]</span> <span class="p">[</span><span class="mi">1</span> <span class="n">swons</span><span class="p">]</span> <span class="o">.</span> <span class="n">dip</span> <span class="n">uncons</span> <span class="n">swap</span>
 106                                <span class="p">[]</span> <span class="o">.</span> <span class="mi">1</span> <span class="n">swons</span> <span class="p">[[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">8</span><span class="p">]</span> <span class="n">uncons</span> <span class="n">swap</span>
 107                              <span class="p">[]</span> <span class="mi">1</span> <span class="o">.</span> <span class="n">swons</span> <span class="p">[[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">8</span><span class="p">]</span> <span class="n">uncons</span> <span class="n">swap</span>
 108                              <span class="p">[]</span> <span class="mi">1</span> <span class="o">.</span> <span class="n">swap</span> <span class="n">cons</span> <span class="p">[[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">8</span><span class="p">]</span> <span class="n">uncons</span> <span class="n">swap</span>
 109                              <span class="mi">1</span> <span class="p">[]</span> <span class="o">.</span> <span class="n">cons</span> <span class="p">[[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">8</span><span class="p">]</span> <span class="n">uncons</span> <span class="n">swap</span>
 110                               <span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">.</span> <span class="p">[[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">8</span><span class="p">]</span> <span class="n">uncons</span> <span class="n">swap</span>
 111          <span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="p">[[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">8</span><span class="p">]</span> <span class="o">.</span> <span class="n">uncons</span> <span class="n">swap</span>
 112          <span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="p">[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="o">.</span> <span class="n">swap</span>
 113          <span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="p">[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="o">.</span>
 114 </pre></div>
 115 </div>
 116 <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;[1] [8] [2 [3 4 25 6] 7] z-down&#39;</span><span class="p">)</span>
 117 </pre></div>
 118 </div>
 119 <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="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="p">[]</span> <span class="p">[[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">2</span>
 120 </pre></div>
 121 </div>
 122 <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;[1] [8] [] [[3 4 25 6] 7] 2 z-right&#39;</span><span class="p">)</span>
 123 </pre></div>
 124 </div>
 125 <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="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="p">[</span><span class="mi">7</span><span class="p">]</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span>
 126 </pre></div>
 127 </div>
 128 <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;[1] [8] [2] [7] [3 4 25 6] z-down&#39;</span><span class="p">)</span>
 129 </pre></div>
 130 </div>
 131 <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="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="p">[</span><span class="mi">7</span><span class="p">]</span> <span class="p">[]</span> <span class="p">[</span><span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">3</span>
 132 </pre></div>
 133 </div>
 134 <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;[1] [8] [2] [7] [] [4 25 6] 3 z-right&#39;</span><span class="p">)</span>
 135 </pre></div>
 136 </div>
 137 <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="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="p">[</span><span class="mi">7</span><span class="p">]</span> <span class="p">[</span><span class="mi">3</span><span class="p">]</span> <span class="p">[</span><span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">4</span>
 138 </pre></div>
 139 </div>
 140 <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;[1] [8] [2] [7] [3] [25 6] 4 z-right&#39;</span><span class="p">)</span>
 141 </pre></div>
 142 </div>
 143 <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="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="p">[</span><span class="mi">7</span><span class="p">]</span> <span class="p">[</span><span class="mi">4</span> <span class="mi">3</span><span class="p">]</span> <span class="p">[</span><span class="mi">6</span><span class="p">]</span> <span class="mi">25</span>
 144 </pre></div>
 145 </div>
 146 <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;[1] [8] [2] [7] [4 3] [6] 25 sqr&#39;</span><span class="p">)</span>
 147 </pre></div>
 148 </div>
 149 <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="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="p">[</span><span class="mi">7</span><span class="p">]</span> <span class="p">[</span><span class="mi">4</span> <span class="mi">3</span><span class="p">]</span> <span class="p">[</span><span class="mi">6</span><span class="p">]</span> <span class="mi">625</span>
 150 </pre></div>
 151 </div>
 152 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">V</span><span class="p">(</span><span class="s1">&#39;[1] [8] [2] [7] [4 3] [6] 625 z-up&#39;</span><span class="p">)</span>
 153 </pre></div>
 154 </div>
 155 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>                              <span class="o">.</span> <span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="p">[</span><span class="mi">7</span><span class="p">]</span> <span class="p">[</span><span class="mi">4</span> <span class="mi">3</span><span class="p">]</span> <span class="p">[</span><span class="mi">6</span><span class="p">]</span> <span class="mi">625</span> <span class="n">z</span><span class="o">-</span><span class="n">up</span>
 156                           <span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">.</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="p">[</span><span class="mi">7</span><span class="p">]</span> <span class="p">[</span><span class="mi">4</span> <span class="mi">3</span><span class="p">]</span> <span class="p">[</span><span class="mi">6</span><span class="p">]</span> <span class="mi">625</span> <span class="n">z</span><span class="o">-</span><span class="n">up</span>
 157                       <span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="o">.</span> <span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="p">[</span><span class="mi">7</span><span class="p">]</span> <span class="p">[</span><span class="mi">4</span> <span class="mi">3</span><span class="p">]</span> <span class="p">[</span><span class="mi">6</span><span class="p">]</span> <span class="mi">625</span> <span class="n">z</span><span class="o">-</span><span class="n">up</span>
 158                   <span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="o">.</span> <span class="p">[</span><span class="mi">7</span><span class="p">]</span> <span class="p">[</span><span class="mi">4</span> <span class="mi">3</span><span class="p">]</span> <span class="p">[</span><span class="mi">6</span><span class="p">]</span> <span class="mi">625</span> <span class="n">z</span><span class="o">-</span><span class="n">up</span>
 159               <span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="p">[</span><span class="mi">7</span><span class="p">]</span> <span class="o">.</span> <span class="p">[</span><span class="mi">4</span> <span class="mi">3</span><span class="p">]</span> <span class="p">[</span><span class="mi">6</span><span class="p">]</span> <span class="mi">625</span> <span class="n">z</span><span class="o">-</span><span class="n">up</span>
 160         <span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="p">[</span><span class="mi">7</span><span class="p">]</span> <span class="p">[</span><span class="mi">4</span> <span class="mi">3</span><span class="p">]</span> <span class="o">.</span> <span class="p">[</span><span class="mi">6</span><span class="p">]</span> <span class="mi">625</span> <span class="n">z</span><span class="o">-</span><span class="n">up</span>
 161     <span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="p">[</span><span class="mi">7</span><span class="p">]</span> <span class="p">[</span><span class="mi">4</span> <span class="mi">3</span><span class="p">]</span> <span class="p">[</span><span class="mi">6</span><span class="p">]</span> <span class="o">.</span> <span class="mi">625</span> <span class="n">z</span><span class="o">-</span><span class="n">up</span>
 162 <span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="p">[</span><span class="mi">7</span><span class="p">]</span> <span class="p">[</span><span class="mi">4</span> <span class="mi">3</span><span class="p">]</span> <span class="p">[</span><span class="mi">6</span><span class="p">]</span> <span class="mi">625</span> <span class="o">.</span> <span class="n">z</span><span class="o">-</span><span class="n">up</span>
 163 <span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="p">[</span><span class="mi">7</span><span class="p">]</span> <span class="p">[</span><span class="mi">4</span> <span class="mi">3</span><span class="p">]</span> <span class="p">[</span><span class="mi">6</span><span class="p">]</span> <span class="mi">625</span> <span class="o">.</span> <span class="n">swons</span> <span class="n">swap</span> <span class="n">shunt</span>
 164 <span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="p">[</span><span class="mi">7</span><span class="p">]</span> <span class="p">[</span><span class="mi">4</span> <span class="mi">3</span><span class="p">]</span> <span class="p">[</span><span class="mi">6</span><span class="p">]</span> <span class="mi">625</span> <span class="o">.</span> <span class="n">swap</span> <span class="n">cons</span> <span class="n">swap</span> <span class="n">shunt</span>
 165 <span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="p">[</span><span class="mi">7</span><span class="p">]</span> <span class="p">[</span><span class="mi">4</span> <span class="mi">3</span><span class="p">]</span> <span class="mi">625</span> <span class="p">[</span><span class="mi">6</span><span class="p">]</span> <span class="o">.</span> <span class="n">cons</span> <span class="n">swap</span> <span class="n">shunt</span>
 166 <span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="p">[</span><span class="mi">7</span><span class="p">]</span> <span class="p">[</span><span class="mi">4</span> <span class="mi">3</span><span class="p">]</span> <span class="p">[</span><span class="mi">625</span> <span class="mi">6</span><span class="p">]</span> <span class="o">.</span> <span class="n">swap</span> <span class="n">shunt</span>
 167 <span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="p">[</span><span class="mi">7</span><span class="p">]</span> <span class="p">[</span><span class="mi">625</span> <span class="mi">6</span><span class="p">]</span> <span class="p">[</span><span class="mi">4</span> <span class="mi">3</span><span class="p">]</span> <span class="o">.</span> <span class="n">shunt</span>
 168   <span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="p">[</span><span class="mi">7</span><span class="p">]</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">625</span> <span class="mi">6</span><span class="p">]</span> <span class="o">.</span>
 169 </pre></div>
 170 </div>
 171 <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;[1] [8] [2] [7] [3 4 625 6] z-up&#39;</span><span class="p">)</span>
 172 </pre></div>
 173 </div>
 174 <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="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="p">[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">625</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span>
 175 </pre></div>
 176 </div>
 177 <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;[1] [8] [2 [3 4 625 6] 7] z-up&#39;</span><span class="p">)</span>
 178 </pre></div>
 179 </div>
 180 <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">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">625</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">8</span><span class="p">]</span>
 181 </pre></div>
 182 </div>
 183 </div>
 184 <div class="section" id="dip-and-infra">
 185 <h2><code class="docutils literal notranslate"><span class="pre">dip</span></code> and <code class="docutils literal notranslate"><span class="pre">infra</span></code><a class="headerlink" href="#dip-and-infra" title="Permalink to this headline">¶</a></h2>
 186 <p>In Joy we have the <code class="docutils literal notranslate"><span class="pre">dip</span></code> and <code class="docutils literal notranslate"><span class="pre">infra</span></code> combinators which can “target”
 187 or “address” any particular item in a Joy tree structure.</p>
 188 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">V</span><span class="p">(</span><span class="s1">&#39;[1 [2 [3 4 25 6] 7] 8] [[[[[[sqr] dipd] infra] dip] infra] dip] infra&#39;</span><span class="p">)</span>
 189 </pre></div>
 190 </div>
 191 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>                                                                <span class="o">.</span> <span class="p">[</span><span class="mi">1</span> <span class="p">[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">8</span><span class="p">]</span> <span class="p">[[[[[[</span><span class="n">sqr</span><span class="p">]</span> <span class="n">dipd</span><span class="p">]</span> <span class="n">infra</span><span class="p">]</span> <span class="n">dip</span><span class="p">]</span> <span class="n">infra</span><span class="p">]</span> <span class="n">dip</span><span class="p">]</span> <span class="n">infra</span>
 192                                          <span class="p">[</span><span class="mi">1</span> <span class="p">[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">8</span><span class="p">]</span> <span class="o">.</span> <span class="p">[[[[[[</span><span class="n">sqr</span><span class="p">]</span> <span class="n">dipd</span><span class="p">]</span> <span class="n">infra</span><span class="p">]</span> <span class="n">dip</span><span class="p">]</span> <span class="n">infra</span><span class="p">]</span> <span class="n">dip</span><span class="p">]</span> <span class="n">infra</span>
 193 <span class="p">[</span><span class="mi">1</span> <span class="p">[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">8</span><span class="p">]</span> <span class="p">[[[[[[</span><span class="n">sqr</span><span class="p">]</span> <span class="n">dipd</span><span class="p">]</span> <span class="n">infra</span><span class="p">]</span> <span class="n">dip</span><span class="p">]</span> <span class="n">infra</span><span class="p">]</span> <span class="n">dip</span><span class="p">]</span> <span class="o">.</span> <span class="n">infra</span>
 194                                            <span class="mi">8</span> <span class="p">[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">1</span> <span class="o">.</span> <span class="p">[[[[[</span><span class="n">sqr</span><span class="p">]</span> <span class="n">dipd</span><span class="p">]</span> <span class="n">infra</span><span class="p">]</span> <span class="n">dip</span><span class="p">]</span> <span class="n">infra</span><span class="p">]</span> <span class="n">dip</span> <span class="p">[]</span> <span class="n">swaack</span>
 195         <span class="mi">8</span> <span class="p">[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">1</span> <span class="p">[[[[[</span><span class="n">sqr</span><span class="p">]</span> <span class="n">dipd</span><span class="p">]</span> <span class="n">infra</span><span class="p">]</span> <span class="n">dip</span><span class="p">]</span> <span class="n">infra</span><span class="p">]</span> <span class="o">.</span> <span class="n">dip</span> <span class="p">[]</span> <span class="n">swaack</span>
 196                                              <span class="mi">8</span> <span class="p">[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="o">.</span> <span class="p">[[[[</span><span class="n">sqr</span><span class="p">]</span> <span class="n">dipd</span><span class="p">]</span> <span class="n">infra</span><span class="p">]</span> <span class="n">dip</span><span class="p">]</span> <span class="n">infra</span> <span class="mi">1</span> <span class="p">[]</span> <span class="n">swaack</span>
 197                   <span class="mi">8</span> <span class="p">[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="p">[[[[</span><span class="n">sqr</span><span class="p">]</span> <span class="n">dipd</span><span class="p">]</span> <span class="n">infra</span><span class="p">]</span> <span class="n">dip</span><span class="p">]</span> <span class="o">.</span> <span class="n">infra</span> <span class="mi">1</span> <span class="p">[]</span> <span class="n">swaack</span>
 198                                                  <span class="mi">7</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">2</span> <span class="o">.</span> <span class="p">[[[</span><span class="n">sqr</span><span class="p">]</span> <span class="n">dipd</span><span class="p">]</span> <span class="n">infra</span><span class="p">]</span> <span class="n">dip</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="n">swaack</span> <span class="mi">1</span> <span class="p">[]</span> <span class="n">swaack</span>
 199                             <span class="mi">7</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">2</span> <span class="p">[[[</span><span class="n">sqr</span><span class="p">]</span> <span class="n">dipd</span><span class="p">]</span> <span class="n">infra</span><span class="p">]</span> <span class="o">.</span> <span class="n">dip</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="n">swaack</span> <span class="mi">1</span> <span class="p">[]</span> <span class="n">swaack</span>
 200                                                    <span class="mi">7</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="o">.</span> <span class="p">[[</span><span class="n">sqr</span><span class="p">]</span> <span class="n">dipd</span><span class="p">]</span> <span class="n">infra</span> <span class="mi">2</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="n">swaack</span> <span class="mi">1</span> <span class="p">[]</span> <span class="n">swaack</span>
 201                                       <span class="mi">7</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">25</span> <span class="mi">6</span><span class="p">]</span> <span class="p">[[</span><span class="n">sqr</span><span class="p">]</span> <span class="n">dipd</span><span class="p">]</span> <span class="o">.</span> <span class="n">infra</span> <span class="mi">2</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="n">swaack</span> <span class="mi">1</span> <span class="p">[]</span> <span class="n">swaack</span>
 202                                                        <span class="mi">6</span> <span class="mi">25</span> <span class="mi">4</span> <span class="mi">3</span> <span class="o">.</span> <span class="p">[</span><span class="n">sqr</span><span class="p">]</span> <span class="n">dipd</span> <span class="p">[</span><span class="mi">7</span><span class="p">]</span> <span class="n">swaack</span> <span class="mi">2</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="n">swaack</span> <span class="mi">1</span> <span class="p">[]</span> <span class="n">swaack</span>
 203                                                  <span class="mi">6</span> <span class="mi">25</span> <span class="mi">4</span> <span class="mi">3</span> <span class="p">[</span><span class="n">sqr</span><span class="p">]</span> <span class="o">.</span> <span class="n">dipd</span> <span class="p">[</span><span class="mi">7</span><span class="p">]</span> <span class="n">swaack</span> <span class="mi">2</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="n">swaack</span> <span class="mi">1</span> <span class="p">[]</span> <span class="n">swaack</span>
 204                                                            <span class="mi">6</span> <span class="mi">25</span> <span class="o">.</span> <span class="n">sqr</span> <span class="mi">4</span> <span class="mi">3</span> <span class="p">[</span><span class="mi">7</span><span class="p">]</span> <span class="n">swaack</span> <span class="mi">2</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="n">swaack</span> <span class="mi">1</span> <span class="p">[]</span> <span class="n">swaack</span>
 205                                                            <span class="mi">6</span> <span class="mi">25</span> <span class="o">.</span> <span class="n">dup</span> <span class="n">mul</span> <span class="mi">4</span> <span class="mi">3</span> <span class="p">[</span><span class="mi">7</span><span class="p">]</span> <span class="n">swaack</span> <span class="mi">2</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="n">swaack</span> <span class="mi">1</span> <span class="p">[]</span> <span class="n">swaack</span>
 206                                                         <span class="mi">6</span> <span class="mi">25</span> <span class="mi">25</span> <span class="o">.</span> <span class="n">mul</span> <span class="mi">4</span> <span class="mi">3</span> <span class="p">[</span><span class="mi">7</span><span class="p">]</span> <span class="n">swaack</span> <span class="mi">2</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="n">swaack</span> <span class="mi">1</span> <span class="p">[]</span> <span class="n">swaack</span>
 207                                                           <span class="mi">6</span> <span class="mi">625</span> <span class="o">.</span> <span class="mi">4</span> <span class="mi">3</span> <span class="p">[</span><span class="mi">7</span><span class="p">]</span> <span class="n">swaack</span> <span class="mi">2</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="n">swaack</span> <span class="mi">1</span> <span class="p">[]</span> <span class="n">swaack</span>
 208                                                         <span class="mi">6</span> <span class="mi">625</span> <span class="mi">4</span> <span class="o">.</span> <span class="mi">3</span> <span class="p">[</span><span class="mi">7</span><span class="p">]</span> <span class="n">swaack</span> <span class="mi">2</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="n">swaack</span> <span class="mi">1</span> <span class="p">[]</span> <span class="n">swaack</span>
 209                                                       <span class="mi">6</span> <span class="mi">625</span> <span class="mi">4</span> <span class="mi">3</span> <span class="o">.</span> <span class="p">[</span><span class="mi">7</span><span class="p">]</span> <span class="n">swaack</span> <span class="mi">2</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="n">swaack</span> <span class="mi">1</span> <span class="p">[]</span> <span class="n">swaack</span>
 210                                                   <span class="mi">6</span> <span class="mi">625</span> <span class="mi">4</span> <span class="mi">3</span> <span class="p">[</span><span class="mi">7</span><span class="p">]</span> <span class="o">.</span> <span class="n">swaack</span> <span class="mi">2</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="n">swaack</span> <span class="mi">1</span> <span class="p">[]</span> <span class="n">swaack</span>
 211                                                   <span class="mi">7</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">625</span> <span class="mi">6</span><span class="p">]</span> <span class="o">.</span> <span class="mi">2</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="n">swaack</span> <span class="mi">1</span> <span class="p">[]</span> <span class="n">swaack</span>
 212                                                 <span class="mi">7</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">625</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">2</span> <span class="o">.</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="n">swaack</span> <span class="mi">1</span> <span class="p">[]</span> <span class="n">swaack</span>
 213                                             <span class="mi">7</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">625</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">2</span> <span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="o">.</span> <span class="n">swaack</span> <span class="mi">1</span> <span class="p">[]</span> <span class="n">swaack</span>
 214                                             <span class="mi">8</span> <span class="p">[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">625</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="o">.</span> <span class="mi">1</span> <span class="p">[]</span> <span class="n">swaack</span>
 215                                           <span class="mi">8</span> <span class="p">[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">625</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">1</span> <span class="o">.</span> <span class="p">[]</span> <span class="n">swaack</span>
 216                                        <span class="mi">8</span> <span class="p">[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">625</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">1</span> <span class="p">[]</span> <span class="o">.</span> <span class="n">swaack</span>
 217                                         <span class="p">[</span><span class="mi">1</span> <span class="p">[</span><span class="mi">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">625</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">8</span><span class="p">]</span> <span class="o">.</span>
 218 </pre></div>
 219 </div>
 220 <p>If you read the trace carefully you’ll see that about half of it is the
 221 <code class="docutils literal notranslate"><span class="pre">dip</span></code> and <code class="docutils literal notranslate"><span class="pre">infra</span></code> combinators de-quoting programs and “digging” into
 222 the subject datastructure. Instead of maintaining temporary results on
 223 the stack they are pushed into the pending expression (continuation).
 224 When <code class="docutils literal notranslate"><span class="pre">sqr</span></code> has run the rest of the pending expression rebuilds the
 225 datastructure.</p>
 226 </div>
 227 <div class="section" id="z">
 228 <h2><code class="docutils literal notranslate"><span class="pre">Z</span></code><a class="headerlink" href="#z" title="Permalink to this headline">¶</a></h2>
 229 <p>Imagine a function <code class="docutils literal notranslate"><span class="pre">Z</span></code> that accepts a sequence of <code class="docutils literal notranslate"><span class="pre">dip</span></code> and
 230 <code class="docutils literal notranslate"><span class="pre">infra</span></code> combinators, a quoted program <code class="docutils literal notranslate"><span class="pre">[Q]</span></code>, and a datastructure to
 231 work on. It would effectively execute the quoted program as if it had
 232 been embedded in a nested series of quoted programs, e.g.:</p>
 233 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>   <span class="p">[</span><span class="o">...</span><span class="p">]</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="p">[</span><span class="n">dip</span> <span class="n">dip</span> <span class="n">infra</span> <span class="n">dip</span> <span class="n">infra</span> <span class="n">dip</span> <span class="n">infra</span><span class="p">]</span> <span class="n">Z</span>
 234 <span class="o">-------------------------------------------------------------</span>
 235    <span class="p">[</span><span class="o">...</span><span class="p">]</span> <span class="p">[[[[[[[</span><span class="n">Q</span><span class="p">]</span> <span class="n">dip</span><span class="p">]</span> <span class="n">dip</span><span class="p">]</span> <span class="n">infra</span><span class="p">]</span> <span class="n">dip</span><span class="p">]</span> <span class="n">infra</span><span class="p">]</span> <span class="n">dip</span><span class="p">]</span> <span class="n">infra</span>
 236 </pre></div>
 237 </div>
 238 <p>The <code class="docutils literal notranslate"><span class="pre">Z</span></code> function isn’t hard to make.</p>
 239 <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;Z == [[] cons cons] step i&#39;</span><span class="p">)</span>
 240 </pre></div>
 241 </div>
 242 <p>Here it is in action in a simplified scenario.</p>
 243 <div class="code ipython2 highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">V</span><span class="p">(</span><span class="s1">&#39;1 [2 3 4] Z&#39;</span><span class="p">)</span>
 244 </pre></div>
 245 </div>
 246 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>                             <span class="o">.</span> <span class="mi">1</span> <span class="p">[</span><span class="mi">2</span> <span class="mi">3</span> <span class="mi">4</span><span class="p">]</span> <span class="n">Z</span>
 247                            <span class="mi">1</span> <span class="o">.</span> <span class="p">[</span><span class="mi">2</span> <span class="mi">3</span> <span class="mi">4</span><span class="p">]</span> <span class="n">Z</span>
 248                    <span class="mi">1</span> <span class="p">[</span><span class="mi">2</span> <span class="mi">3</span> <span class="mi">4</span><span class="p">]</span> <span class="o">.</span> <span class="n">Z</span>
 249                    <span class="mi">1</span> <span class="p">[</span><span class="mi">2</span> <span class="mi">3</span> <span class="mi">4</span><span class="p">]</span> <span class="o">.</span> <span class="p">[[]</span> <span class="n">cons</span> <span class="n">cons</span><span class="p">]</span> <span class="n">step</span> <span class="n">i</span>
 250     <span class="mi">1</span> <span class="p">[</span><span class="mi">2</span> <span class="mi">3</span> <span class="mi">4</span><span class="p">]</span> <span class="p">[[]</span> <span class="n">cons</span> <span class="n">cons</span><span class="p">]</span> <span class="o">.</span> <span class="n">step</span> <span class="n">i</span>
 251           <span class="mi">1</span> <span class="mi">2</span> <span class="p">[[]</span> <span class="n">cons</span> <span class="n">cons</span><span class="p">]</span> <span class="o">.</span> <span class="n">i</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span><span class="p">]</span> <span class="p">[[]</span> <span class="n">cons</span> <span class="n">cons</span><span class="p">]</span> <span class="n">step</span> <span class="n">i</span>
 252                          <span class="mi">1</span> <span class="mi">2</span> <span class="o">.</span> <span class="p">[]</span> <span class="n">cons</span> <span class="n">cons</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span><span class="p">]</span> <span class="p">[[]</span> <span class="n">cons</span> <span class="n">cons</span><span class="p">]</span> <span class="n">step</span> <span class="n">i</span>
 253                       <span class="mi">1</span> <span class="mi">2</span> <span class="p">[]</span> <span class="o">.</span> <span class="n">cons</span> <span class="n">cons</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span><span class="p">]</span> <span class="p">[[]</span> <span class="n">cons</span> <span class="n">cons</span><span class="p">]</span> <span class="n">step</span> <span class="n">i</span>
 254                        <span class="mi">1</span> <span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="o">.</span> <span class="n">cons</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span><span class="p">]</span> <span class="p">[[]</span> <span class="n">cons</span> <span class="n">cons</span><span class="p">]</span> <span class="n">step</span> <span class="n">i</span>
 255                        <span class="p">[</span><span class="mi">1</span> <span class="mi">2</span><span class="p">]</span> <span class="o">.</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span><span class="p">]</span> <span class="p">[[]</span> <span class="n">cons</span> <span class="n">cons</span><span class="p">]</span> <span class="n">step</span> <span class="n">i</span>
 256                  <span class="p">[</span><span class="mi">1</span> <span class="mi">2</span><span class="p">]</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span><span class="p">]</span> <span class="o">.</span> <span class="p">[[]</span> <span class="n">cons</span> <span class="n">cons</span><span class="p">]</span> <span class="n">step</span> <span class="n">i</span>
 257   <span class="p">[</span><span class="mi">1</span> <span class="mi">2</span><span class="p">]</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span><span class="p">]</span> <span class="p">[[]</span> <span class="n">cons</span> <span class="n">cons</span><span class="p">]</span> <span class="o">.</span> <span class="n">step</span> <span class="n">i</span>
 258       <span class="p">[</span><span class="mi">1</span> <span class="mi">2</span><span class="p">]</span> <span class="mi">3</span> <span class="p">[[]</span> <span class="n">cons</span> <span class="n">cons</span><span class="p">]</span> <span class="o">.</span> <span class="n">i</span> <span class="p">[</span><span class="mi">4</span><span class="p">]</span> <span class="p">[[]</span> <span class="n">cons</span> <span class="n">cons</span><span class="p">]</span> <span class="n">step</span> <span class="n">i</span>
 259                      <span class="p">[</span><span class="mi">1</span> <span class="mi">2</span><span class="p">]</span> <span class="mi">3</span> <span class="o">.</span> <span class="p">[]</span> <span class="n">cons</span> <span class="n">cons</span> <span class="p">[</span><span class="mi">4</span><span class="p">]</span> <span class="p">[[]</span> <span class="n">cons</span> <span class="n">cons</span><span class="p">]</span> <span class="n">step</span> <span class="n">i</span>
 260                   <span class="p">[</span><span class="mi">1</span> <span class="mi">2</span><span class="p">]</span> <span class="mi">3</span> <span class="p">[]</span> <span class="o">.</span> <span class="n">cons</span> <span class="n">cons</span> <span class="p">[</span><span class="mi">4</span><span class="p">]</span> <span class="p">[[]</span> <span class="n">cons</span> <span class="n">cons</span><span class="p">]</span> <span class="n">step</span> <span class="n">i</span>
 261                    <span class="p">[</span><span class="mi">1</span> <span class="mi">2</span><span class="p">]</span> <span class="p">[</span><span class="mi">3</span><span class="p">]</span> <span class="o">.</span> <span class="n">cons</span> <span class="p">[</span><span class="mi">4</span><span class="p">]</span> <span class="p">[[]</span> <span class="n">cons</span> <span class="n">cons</span><span class="p">]</span> <span class="n">step</span> <span class="n">i</span>
 262                    <span class="p">[[</span><span class="mi">1</span> <span class="mi">2</span><span class="p">]</span> <span class="mi">3</span><span class="p">]</span> <span class="o">.</span> <span class="p">[</span><span class="mi">4</span><span class="p">]</span> <span class="p">[[]</span> <span class="n">cons</span> <span class="n">cons</span><span class="p">]</span> <span class="n">step</span> <span class="n">i</span>
 263                <span class="p">[[</span><span class="mi">1</span> <span class="mi">2</span><span class="p">]</span> <span class="mi">3</span><span class="p">]</span> <span class="p">[</span><span class="mi">4</span><span class="p">]</span> <span class="o">.</span> <span class="p">[[]</span> <span class="n">cons</span> <span class="n">cons</span><span class="p">]</span> <span class="n">step</span> <span class="n">i</span>
 264 <span class="p">[[</span><span class="mi">1</span> <span class="mi">2</span><span class="p">]</span> <span class="mi">3</span><span class="p">]</span> <span class="p">[</span><span class="mi">4</span><span class="p">]</span> <span class="p">[[]</span> <span class="n">cons</span> <span class="n">cons</span><span class="p">]</span> <span class="o">.</span> <span class="n">step</span> <span class="n">i</span>
 265   <span class="p">[[</span><span class="mi">1</span> <span class="mi">2</span><span class="p">]</span> <span class="mi">3</span><span class="p">]</span> <span class="mi">4</span> <span class="p">[[]</span> <span class="n">cons</span> <span class="n">cons</span><span class="p">]</span> <span class="o">.</span> <span class="n">i</span> <span class="n">i</span>
 266                  <span class="p">[[</span><span class="mi">1</span> <span class="mi">2</span><span class="p">]</span> <span class="mi">3</span><span class="p">]</span> <span class="mi">4</span> <span class="o">.</span> <span class="p">[]</span> <span class="n">cons</span> <span class="n">cons</span> <span class="n">i</span>
 267               <span class="p">[[</span><span class="mi">1</span> <span class="mi">2</span><span class="p">]</span> <span class="mi">3</span><span class="p">]</span> <span class="mi">4</span> <span class="p">[]</span> <span class="o">.</span> <span class="n">cons</span> <span class="n">cons</span> <span class="n">i</span>
 268                <span class="p">[[</span><span class="mi">1</span> <span class="mi">2</span><span class="p">]</span> <span class="mi">3</span><span class="p">]</span> <span class="p">[</span><span class="mi">4</span><span class="p">]</span> <span class="o">.</span> <span class="n">cons</span> <span class="n">i</span>
 269                <span class="p">[[[</span><span class="mi">1</span> <span class="mi">2</span><span class="p">]</span> <span class="mi">3</span><span class="p">]</span> <span class="mi">4</span><span class="p">]</span> <span class="o">.</span> <span class="n">i</span>
 270                              <span class="o">.</span> <span class="p">[[</span><span class="mi">1</span> <span class="mi">2</span><span class="p">]</span> <span class="mi">3</span><span class="p">]</span> <span class="mi">4</span>
 271                    <span class="p">[[</span><span class="mi">1</span> <span class="mi">2</span><span class="p">]</span> <span class="mi">3</span><span class="p">]</span> <span class="o">.</span> <span class="mi">4</span>
 272                  <span class="p">[[</span><span class="mi">1</span> <span class="mi">2</span><span class="p">]</span> <span class="mi">3</span><span class="p">]</span> <span class="mi">4</span> <span class="o">.</span>
 273 </pre></div>
 274 </div>
 275 <p>And here it is doing the main thing.</p>
 276 <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;[1 [2 [3 4 25 6] 7] 8] [sqr] [dip dip infra dip infra dip infra] Z&#39;</span><span class="p">)</span>
 277 </pre></div>
 278 </div>
 279 <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">2</span> <span class="p">[</span><span class="mi">3</span> <span class="mi">4</span> <span class="mi">625</span> <span class="mi">6</span><span class="p">]</span> <span class="mi">7</span><span class="p">]</span> <span class="mi">8</span><span class="p">]</span>
 280 </pre></div>
 281 </div>
 282 </div>
 283 <div class="section" id="addressing">
 284 <h2>Addressing<a class="headerlink" href="#addressing" title="Permalink to this headline">¶</a></h2>
 285 <p>Because we are only using two combinators we could replace the list with
 286 a string made from only two characters.</p>
 287 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>   <span class="p">[</span><span class="o">...</span><span class="p">]</span> <span class="p">[</span><span class="n">Q</span><span class="p">]</span> <span class="s1">&#39;ddididi&#39;</span> <span class="n">Zstr</span>
 288 <span class="o">-------------------------------------------------------------</span>
 289    <span class="p">[</span><span class="o">...</span><span class="p">]</span> <span class="p">[[[[[[[</span><span class="n">Q</span><span class="p">]</span> <span class="n">dip</span><span class="p">]</span> <span class="n">dip</span><span class="p">]</span> <span class="n">infra</span><span class="p">]</span> <span class="n">dip</span><span class="p">]</span> <span class="n">infra</span><span class="p">]</span> <span class="n">dip</span><span class="p">]</span> <span class="n">infra</span>
 290 </pre></div>
 291 </div>
 292 <p>The string can be considered a name or address for an item in the
 293 subject datastructure.</p>
 294 </div>
 295 <div class="section" id="determining-the-right-path-for-an-item-in-a-tree">
 296 <h2>Determining the right “path” for an item in a tree.<a class="headerlink" href="#determining-the-right-path-for-an-item-in-a-tree" title="Permalink to this headline">¶</a></h2>
 297 <p>It’s easy to read off (in reverse) the right sequence of “d” and “i”
 298 from the subject datastructure:</p>
 299 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>[ n [ n [ n n x ...
 300 i d i d i d d Bingo!
 301 </pre></div>
 302 </div>
 303 </div>
 304 </div>
 305
 306
 307           </div>
 308         </div>
 309       </div>
 310       <div class="sphinxsidebar" role="navigation" aria-label="main navigation">
 311         <div class="sphinxsidebarwrapper">
 312   <h3><a href="../index.html">Table Of Contents</a></h3>
 313   <ul>
 314 <li><a class="reference internal" href="#">Traversing Datastructures with Zippers</a><ul>
 315 <li><a class="reference internal" href="#trees">Trees</a></li>
 316 <li><a class="reference internal" href="#zipper-in-joy">Zipper in Joy</a></li>
 317 <li><a class="reference internal" href="#dip-and-infra"><code class="docutils literal notranslate"><span class="pre">dip</span></code> and <code class="docutils literal notranslate"><span class="pre">infra</span></code></a></li>
 318 <li><a class="reference internal" href="#z"><code class="docutils literal notranslate"><span class="pre">Z</span></code></a></li>
 319 <li><a class="reference internal" href="#addressing">Addressing</a></li>
 320 <li><a class="reference internal" href="#determining-the-right-path-for-an-item-in-a-tree">Determining the right “path” for an item in a tree.</a></li>
 321 </ul>
 322 </li>
 323 </ul>
 324 <div class="relations">
 325 <h3>Related Topics</h3>
 326 <ul>
 327   <li><a href="../index.html">Documentation overview</a><ul>
 328   <li><a href="index.html">Essays about Programming in Joy</a><ul>
 329       <li>Previous: <a href="Newton-Raphson.html" title="previous chapter">Newton’s method</a></li>
 330       <li>Next: <a href="Types.html" title="next chapter">The Blissful Elegance of Typing Joy</a></li>
 331   </ul></li>
 332   </ul></li>
 333 </ul>
 334 </div>
 335   <div role="note" aria-label="source link">
 336     <h3>This Page</h3>
 337     <ul class="this-page-menu">
 338       <li><a href="../_sources/notebooks/Zipper.rst.txt"
 339             rel="nofollow">Show Source</a></li>
 340     </ul>
 341    </div>
 342 <div id="searchbox" style="display: none" role="search">
 343   <h3>Quick search</h3>
 344     <div class="searchformwrapper">
 345     <form class="search" action="../search.html" method="get">
 346       <input type="text" name="q" />
 347       <input type="submit" value="Go" />
 348       <input type="hidden" name="check_keywords" value="yes" />
 349       <input type="hidden" name="area" value="default" />
 350     </form>
 351     </div>
 352 </div>
 353 <script type="text/javascript">$('#searchbox').show(0);</script>
 354         </div>
 355       </div>
 356       <div class="clearer"></div>
 357     </div>
 358     <div class="footer" role="contentinfo">
 359 <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/">
 360 <img alt="Creative Commons License" style="border-width:0" src="https://i.creativecommons.org/l/by-nc-sa/4.0/88x31.png" />
 361 </a>
 362 <br />
 363 <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>.
 364       Created using <a href="http://sphinx-doc.org/">Sphinx</a> 1.7.3.
 365     </div>
 366
 367   </body>
 368 </html>