docs/sphinx_docs/_build/html/notebooks/AlsoNewton.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>within &#8212; Thun 0.1.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
  20   <link rel="stylesheet" href="../_static/custom.css" type="text/css" />
  21
  22
  23   <meta name="viewport" content="width=device-width, initial-scale=0.9, maximum-scale=0.9" />
  24
  25   </head><body>
  26
  27
  28     <div class="document">
  29       <div class="documentwrapper">
  30         <div class="bodywrapper">
  31           <div class="body" role="main">
  32
  33   <div class="section" id="within">
  34 <h1><code class="docutils literal notranslate"><span class="pre">within</span></code><a class="headerlink" href="#within" title="Permalink to this headline">¶</a></h1>
  35 <blockquote>
  36 <div>The remainder of a square root finder is a function <em>within</em>, which takes a tolerance and a list of approximations and looks down the list for two successive approximations that differ by no more than the given tolerance.</div></blockquote>
  37 <p>From <a class="reference external" href="https://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf">“Why Functional Programming Matters” by John
  38 Hughes</a></p>
  39 <p>(And note that by “list” he means a lazily-evaluated list.)</p>
  40 <p>Using a <a class="reference internal" href="Generator Programs.html"><span class="doc">generator</span></a> driven by <code class="docutils literal notranslate"><span class="pre">x</span></code> and assuming such for square root approximations (or whatever) <code class="docutils literal notranslate"><span class="pre">G</span></code>, and further assuming that the first term <code class="docutils literal notranslate"><span class="pre">a</span></code> has been generated already and epsilon <code class="docutils literal notranslate"><span class="pre">ε</span></code> is handy on the stack…</p>
  41 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>   <span class="n">a</span> <span class="p">[</span><span class="n">b</span> <span class="n">G</span><span class="p">]</span> <span class="n">ε</span> <span class="n">within</span>
  42 <span class="o">--------------------</span> <span class="n">a</span> <span class="n">b</span> <span class="o">-</span> <span class="nb">abs</span> <span class="n">ε</span> <span class="o">&lt;=</span>
  43       <span class="n">b</span>
  44
  45    <span class="n">a</span> <span class="p">[</span><span class="n">b</span> <span class="n">G</span><span class="p">]</span> <span class="n">ε</span> <span class="n">within</span>
  46 <span class="o">--------------------</span> <span class="n">a</span> <span class="n">b</span> <span class="o">-</span> <span class="nb">abs</span> <span class="n">ε</span> <span class="o">&gt;</span>
  47        <span class="o">.</span>
  48    <span class="p">[</span><span class="n">b</span> <span class="n">G</span><span class="p">]</span> <span class="n">x</span> <span class="n">ε</span> <span class="o">...</span>
  49    <span class="n">b</span> <span class="p">[</span><span class="n">c</span> <span class="n">G</span><span class="p">]</span> <span class="n">ε</span> <span class="o">...</span>
  50        <span class="o">.</span>
  51 <span class="o">--------------------</span>
  52    <span class="n">b</span> <span class="p">[</span><span class="n">c</span> <span class="n">G</span><span class="p">]</span> <span class="n">ε</span> <span class="n">within</span>
  53 </pre></div>
  54 </div>
  55 <div class="section" id="predicate">
  56 <h2>Predicate<a class="headerlink" href="#predicate" title="Permalink to this headline">¶</a></h2>
  57 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">a</span> <span class="p">[</span><span class="n">b</span> <span class="n">G</span><span class="p">]</span>             <span class="n">ε</span> <span class="p">[</span><span class="n">first</span> <span class="o">-</span> <span class="nb">abs</span><span class="p">]</span> <span class="n">dip</span> <span class="o">&lt;=</span>
  58 <span class="n">a</span> <span class="p">[</span><span class="n">b</span> <span class="n">G</span><span class="p">]</span> <span class="n">first</span> <span class="o">-</span> <span class="nb">abs</span> <span class="n">ε</span>                   <span class="o">&lt;=</span>
  59 <span class="n">a</span> <span class="n">b</span>           <span class="o">-</span> <span class="nb">abs</span> <span class="n">ε</span>                   <span class="o">&lt;=</span>
  60 <span class="n">a</span><span class="o">-</span><span class="n">b</span>             <span class="nb">abs</span> <span class="n">ε</span>                   <span class="o">&lt;=</span>
  61 <span class="nb">abs</span><span class="p">(</span><span class="n">a</span><span class="o">-</span><span class="n">b</span><span class="p">)</span>            <span class="n">ε</span>                   <span class="o">&lt;=</span>
  62 <span class="p">(</span><span class="nb">abs</span><span class="p">(</span><span class="n">a</span><span class="o">-</span><span class="n">b</span><span class="p">)</span><span class="o">&lt;=</span><span class="n">ε</span><span class="p">)</span>
  63 </pre></div>
  64 </div>
  65 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">P</span> <span class="o">==</span> <span class="p">[</span><span class="n">first</span> <span class="o">-</span> <span class="nb">abs</span><span class="p">]</span> <span class="n">dip</span> <span class="o">&lt;=</span>
  66 </pre></div>
  67 </div>
  68 </div>
  69 <div class="section" id="base-case">
  70 <h2>Base-Case<a class="headerlink" href="#base-case" title="Permalink to this headline">¶</a></h2>
  71 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">a</span> <span class="p">[</span><span class="n">b</span> <span class="n">G</span><span class="p">]</span> <span class="n">ε</span> <span class="n">roll</span><span class="o">&lt;</span> <span class="n">popop</span> <span class="n">first</span>
  72   <span class="p">[</span><span class="n">b</span> <span class="n">G</span><span class="p">]</span> <span class="n">ε</span> <span class="n">a</span>     <span class="n">popop</span> <span class="n">first</span>
  73   <span class="p">[</span><span class="n">b</span> <span class="n">G</span><span class="p">]</span>               <span class="n">first</span>
  74    <span class="n">b</span>
  75 </pre></div>
  76 </div>
  77 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">B</span> <span class="o">==</span> <span class="n">roll</span><span class="o">&lt;</span> <span class="n">popop</span> <span class="n">first</span>
  78 </pre></div>
  79 </div>
  80 </div>
  81 <div class="section" id="recur">
  82 <h2>Recur<a class="headerlink" href="#recur" title="Permalink to this headline">¶</a></h2>
  83 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">a</span> <span class="p">[</span><span class="n">b</span> <span class="n">G</span><span class="p">]</span> <span class="n">ε</span> <span class="n">R0</span> <span class="p">[</span><span class="n">within</span><span class="p">]</span> <span class="n">R1</span>
  84 </pre></div>
  85 </div>
  86 <ol class="arabic simple">
  87 <li>Discard <code class="docutils literal notranslate"><span class="pre">a</span></code>.</li>
  88 <li>Use <code class="docutils literal notranslate"><span class="pre">x</span></code> combinator to generate next term from G.</li>
  89 <li>Run <code class="docutils literal notranslate"><span class="pre">within</span></code> with <code class="docutils literal notranslate"><span class="pre">i</span></code> (it is a <code class="docutils literal notranslate"><span class="pre">primrec</span></code> function.)</li>
  90 </ol>
  91 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">a</span> <span class="p">[</span><span class="n">b</span> <span class="n">G</span><span class="p">]</span>        <span class="n">ε</span> <span class="n">R0</span>           <span class="p">[</span><span class="n">within</span><span class="p">]</span> <span class="n">R1</span>
  92 <span class="n">a</span> <span class="p">[</span><span class="n">b</span> <span class="n">G</span><span class="p">]</span>        <span class="n">ε</span> <span class="p">[</span><span class="n">popd</span> <span class="n">x</span><span class="p">]</span> <span class="n">dip</span> <span class="p">[</span><span class="n">within</span><span class="p">]</span> <span class="n">i</span>
  93 <span class="n">a</span> <span class="p">[</span><span class="n">b</span> <span class="n">G</span><span class="p">]</span> <span class="n">popd</span> <span class="n">x</span> <span class="n">ε</span>              <span class="p">[</span><span class="n">within</span><span class="p">]</span> <span class="n">i</span>
  94   <span class="p">[</span><span class="n">b</span> <span class="n">G</span><span class="p">]</span>      <span class="n">x</span> <span class="n">ε</span>              <span class="p">[</span><span class="n">within</span><span class="p">]</span> <span class="n">i</span>
  95 <span class="n">b</span> <span class="p">[</span><span class="n">c</span> <span class="n">G</span><span class="p">]</span>        <span class="n">ε</span>              <span class="p">[</span><span class="n">within</span><span class="p">]</span> <span class="n">i</span>
  96 <span class="n">b</span> <span class="p">[</span><span class="n">c</span> <span class="n">G</span><span class="p">]</span>        <span class="n">ε</span>               <span class="n">within</span>
  97
  98 <span class="n">b</span> <span class="p">[</span><span class="n">c</span> <span class="n">G</span><span class="p">]</span> <span class="n">ε</span> <span class="n">within</span>
  99 </pre></div>
 100 </div>
 101 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">R0</span> <span class="o">==</span> <span class="p">[</span><span class="n">popd</span> <span class="n">x</span><span class="p">]</span> <span class="n">dip</span>
 102 </pre></div>
 103 </div>
 104 </div>
 105 <div class="section" id="setting-up">
 106 <h2>Setting up<a class="headerlink" href="#setting-up" title="Permalink to this headline">¶</a></h2>
 107 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="n">a</span> <span class="n">G</span><span class="p">]</span> <span class="n">x</span> <span class="n">ε</span>
 108 <span class="n">a</span> <span class="p">[</span><span class="n">b</span> <span class="n">G</span><span class="p">]</span> <span class="n">ε</span>
 109 </pre></div>
 110 </div>
 111 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">within</span> <span class="o">==</span> <span class="n">x</span> <span class="n">ε</span> <span class="p">[[</span><span class="n">first</span> <span class="o">-</span> <span class="nb">abs</span><span class="p">]</span> <span class="n">dip</span> <span class="o">&lt;=</span><span class="p">]</span> <span class="p">[</span><span class="n">roll</span><span class="o">&lt;</span> <span class="n">popop</span> <span class="n">first</span><span class="p">]</span> <span class="p">[[</span><span class="n">popd</span> <span class="n">x</span><span class="p">]</span> <span class="n">dip</span><span class="p">]</span> <span class="n">primrec</span>
 112 </pre></div>
 113 </div>
 114 </div>
 115 </div>
 116
 117
 118           </div>
 119         </div>
 120       </div>
 121       <div class="sphinxsidebar" role="navigation" aria-label="main navigation">
 122         <div class="sphinxsidebarwrapper">
 123   <h3><a href="../index.html">Table Of Contents</a></h3>
 124   <ul>
 125 <li><a class="reference internal" href="#"><code class="docutils literal notranslate"><span class="pre">within</span></code></a><ul>
 126 <li><a class="reference internal" href="#predicate">Predicate</a></li>
 127 <li><a class="reference internal" href="#base-case">Base-Case</a></li>
 128 <li><a class="reference internal" href="#recur">Recur</a></li>
 129 <li><a class="reference internal" href="#setting-up">Setting up</a></li>
 130 </ul>
 131 </li>
 132 </ul>
 133 <div class="relations">
 134 <h3>Related Topics</h3>
 135 <ul>
 136   <li><a href="../index.html">Documentation overview</a><ul>
 137   </ul></li>
 138 </ul>
 139 </div>
 140   <div role="note" aria-label="source link">
 141     <h3>This Page</h3>
 142     <ul class="this-page-menu">
 143       <li><a href="../_sources/notebooks/AlsoNewton.rst.txt"
 144             rel="nofollow">Show Source</a></li>
 145     </ul>
 146    </div>
 147 <div id="searchbox" style="display: none" role="search">
 148   <h3>Quick search</h3>
 149     <div class="searchformwrapper">
 150     <form class="search" action="../search.html" method="get">
 151       <input type="text" name="q" />
 152       <input type="submit" value="Go" />
 153       <input type="hidden" name="check_keywords" value="yes" />
 154       <input type="hidden" name="area" value="default" />
 155     </form>
 156     </div>
 157 </div>
 158 <script type="text/javascript">$('#searchbox').show(0);</script>
 159         </div>
 160       </div>
 161       <div class="clearer"></div>
 162     </div>
 163     <div class="footer" role="contentinfo">
 164 <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/">
 165 <img alt="Creative Commons License" style="border-width:0" src="https://i.creativecommons.org/l/by-nc-sa/4.0/88x31.png" />
 166 </a>
 167 <br />
 168 <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>.
 169       Created using <a href="http://sphinx-doc.org/">Sphinx</a> 1.7.3.
 170     </div>
 171
 172   </body>
 173 </html>