<html>
<head>
<meta charset="utf-8" />
- <title>Traversing Datastructures with Zippers — Thun 0.3.0 documentation</title>
- <link rel="stylesheet" href="../_static/alabaster.css" type="text/css" />
- <link rel="stylesheet" href="../_static/pygments.css" type="text/css" />
- <script id="documentation_options" data-url_root="../" src="../_static/documentation_options.js"></script>
+ <meta name="viewport" content="width=device-width, initial-scale=1.0" /><meta name="generator" content="Docutils 0.17.1: http://docutils.sourceforge.net/" />
+
+ <title>Traversing Datastructures with Zippers — Thun 0.4.1 documentation</title>
+ <link rel="stylesheet" type="text/css" href="../_static/pygments.css" />
+ <link rel="stylesheet" type="text/css" href="../_static/alabaster.css" />
+ <script data-url_root="../" id="documentation_options" src="../_static/documentation_options.js"></script>
<script src="../_static/jquery.js"></script>
<script src="../_static/underscore.js"></script>
<script src="../_static/doctools.js"></script>
- <script src="../_static/language_data.js"></script>
- <script async="async" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/latest.js?config=TeX-AMS-MML_HTMLorMML"></script>
<link rel="index" title="Index" href="../genindex.html" />
<link rel="search" title="Search" href="../search.html" />
<link rel="next" title="The Blissful Elegance of Typing Joy" href="Types.html" />
- <link rel="prev" title="Newton’s method" href="Newton-Raphson.html" />
+ <link rel="prev" title="Square Spiral Example Joy Code" href="Square_Spiral.html" />
<link rel="stylesheet" href="../_static/custom.css" type="text/css" />
<div class="body" role="main">
- <div class="section" id="traversing-datastructures-with-zippers">
+ <section id="traversing-datastructures-with-zippers">
<h1>Traversing Datastructures with Zippers<a class="headerlink" href="#traversing-datastructures-with-zippers" title="Permalink to this headline">¶</a></h1>
<p>This notebook is about using the “zipper” with joy datastructures. See
the <a class="reference external" href="https://en.wikipedia.org/wiki/Zipper_%28data_structure%29">Zipper wikipedia
<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="kn">from</span> <span class="nn">notebook_preamble</span> <span class="kn">import</span> <span class="n">J</span><span class="p">,</span> <span class="n">V</span><span class="p">,</span> <span class="n">define</span>
</pre></div>
</div>
-<div class="section" id="trees">
+<section id="trees">
<h2>Trees<a class="headerlink" href="#trees" title="Permalink to this headline">¶</a></h2>
<p>In Joypy there aren’t any complex datastructures, just ints, floats,
strings, Symbols (strings that are names of functions) and sequences
-(aka lists, aka quoted literals, aka aggregates, etc…), but we can
-build
+(aka lists, aka quoted literals, aka aggregates, etc…), but we can build
<a class="reference external" href="https://en.wikipedia.org/wiki/Tree_%28data_structure%29">trees</a> out
of sequences.</p>
<div class="highlight-ipython2 notranslate"><div class="highlight"><pre><span></span><span class="n">J</span><span class="p">(</span><span class="s1">'[1 [2 [3 4 25 6] 7] 8]'</span><span class="p">)</span>
<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>
</pre></div>
</div>
-</div>
-<div class="section" id="zipper-in-joy">
+</section>
+<section id="zipper-in-joy">
<h2>Zipper in Joy<a class="headerlink" href="#zipper-in-joy" title="Permalink to this headline">¶</a></h2>
<p>Zippers work by keeping track of the current item, the already-seen
items, and the yet-to-be seen items as you traverse a datastructure (the
<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>
</pre></div>
</div>
-</div>
-<div class="section" id="dip-and-infra">
+</section>
+<section id="dip-and-infra">
<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>
<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”
or “address” any particular item in a Joy tree structure.</p>
the stack they are pushed into the pending expression (continuation).
When <code class="docutils literal notranslate"><span class="pre">sqr</span></code> has run the rest of the pending expression rebuilds the
datastructure.</p>
-</div>
-<div class="section" id="z">
+</section>
+<section id="z">
<h2><code class="docutils literal notranslate"><span class="pre">Z</span></code><a class="headerlink" href="#z" title="Permalink to this headline">¶</a></h2>
<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
<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
<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>
</pre></div>
</div>
-</div>
-<div class="section" id="addressing">
+</section>
+<section id="addressing">
<h2>Addressing<a class="headerlink" href="#addressing" title="Permalink to this headline">¶</a></h2>
<p>Because we are only using two combinators we could replace the list with
a string made from only two characters.</p>
</div>
<p>The string can be considered a name or address for an item in the
subject datastructure.</p>
-</div>
-<div class="section" id="determining-the-right-path-for-an-item-in-a-tree">
+</section>
+<section id="determining-the-right-path-for-an-item-in-a-tree">
<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>
<p>It’s easy to read off (in reverse) the right sequence of “d” and “i”
from the subject datastructure:</p>
i d i d i d d Bingo!
</pre></div>
</div>
-</div>
-</div>
+</section>
+</section>
</div>
<li class="toctree-l2"><a class="reference internal" href="Treestep.html">Treating Trees II: <code class="docutils literal notranslate"><span class="pre">treestep</span></code></a></li>
<li class="toctree-l2"><a class="reference internal" href="Generator_Programs.html">Using <code class="docutils literal notranslate"><span class="pre">x</span></code> to Generate Values</a></li>
<li class="toctree-l2"><a class="reference internal" href="Newton-Raphson.html">Newton’s method</a></li>
+<li class="toctree-l2"><a class="reference internal" href="Square_Spiral.html">Square Spiral Example Joy Code</a></li>
<li class="toctree-l2 current"><a class="current reference internal" href="#">Traversing Datastructures with Zippers</a></li>
<li class="toctree-l2"><a class="reference internal" href="Types.html">The Blissful Elegance of Typing Joy</a></li>
<li class="toctree-l2"><a class="reference internal" href="TypeChecking.html">Type Checking</a></li>
<ul>
<li><a href="../index.html">Documentation overview</a><ul>
<li><a href="index.html">Essays about Programming in Joy</a><ul>
- <li>Previous: <a href="Newton-Raphson.html" title="previous chapter">Newton’s method</a></li>
+ <li>Previous: <a href="Square_Spiral.html" title="previous chapter">Square Spiral Example Joy Code</a></li>
<li>Next: <a href="Types.html" title="next chapter">The Blissful Elegance of Typing Joy</a></li>
</ul></li>
</ul></li>
<h3 id="searchlabel">Quick search</h3>
<div class="searchformwrapper">
<form class="search" action="../search.html" method="get">
- <input type="text" name="q" aria-labelledby="searchlabel" />
+ <input type="text" name="q" aria-labelledby="searchlabel" autocomplete="off" autocorrect="off" autocapitalize="off" spellcheck="false"/>
<input type="submit" value="Go" />
</form>
</div>
</a>
<br />
<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>.
- Created using <a href="http://sphinx-doc.org/">Sphinx</a> 3.0.2.
+ Created using <a href="http://sphinx-doc.org/">Sphinx</a> 4.3.0.
</div>
</body>
OSDN Git Service
