ZelphirKaltstahl
/
the-seasoned-schemer-notes


			
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724
							<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="English" xml:lang="English">
<head>
<!-- 2020-08-31 Mo 21:56 -->
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>The Seasoned Schemer Notes</title>
<meta name="generator" content="Org mode" />
<meta name="author" content="Zelphir Kaltstahl" />
<style type="text/css">
 <!--/*--><![CDATA[/*><!--*/
  .title  { text-align: center;
             margin-bottom: .2em; }
  .subtitle { text-align: center;
              font-size: medium;
              font-weight: bold;
              margin-top:0; }
  .todo   { font-family: monospace; color: red; }
  .done   { font-family: monospace; color: green; }
  .priority { font-family: monospace; color: orange; }
  .tag    { background-color: #eee; font-family: monospace;
            padding: 2px; font-size: 80%; font-weight: normal; }
  .timestamp { color: #bebebe; }
  .timestamp-kwd { color: #5f9ea0; }
  .org-right  { margin-left: auto; margin-right: 0px;  text-align: right; }
  .org-left   { margin-left: 0px;  margin-right: auto; text-align: left; }
  .org-center { margin-left: auto; margin-right: auto; text-align: center; }
  .underline { text-decoration: underline; }
  #postamble p, #preamble p { font-size: 90%; margin: .2em; }
  p.verse { margin-left: 3%; }
  pre {
    border: 1px solid #ccc;
    box-shadow: 3px 3px 3px #eee;
    padding: 8pt;
    font-family: monospace;
    overflow: auto;
    margin: 1.2em;
  }
  pre.src {
    position: relative;
    overflow: visible;
    padding-top: 1.2em;
  }
  pre.src:before {
    display: none;
    position: absolute;
    background-color: white;
    top: -10px;
    right: 10px;
    padding: 3px;
    border: 1px solid black;
  }
  pre.src:hover:before { display: inline;}
  /* Languages per Org manual */
  pre.src-asymptote:before { content: 'Asymptote'; }
  pre.src-awk:before { content: 'Awk'; }
  pre.src-C:before { content: 'C'; }
  /* pre.src-C++ doesn't work in CSS */
  pre.src-clojure:before { content: 'Clojure'; }
  pre.src-css:before { content: 'CSS'; }
  pre.src-D:before { content: 'D'; }
  pre.src-ditaa:before { content: 'ditaa'; }
  pre.src-dot:before { content: 'Graphviz'; }
  pre.src-calc:before { content: 'Emacs Calc'; }
  pre.src-emacs-lisp:before { content: 'Emacs Lisp'; }
  pre.src-fortran:before { content: 'Fortran'; }
  pre.src-gnuplot:before { content: 'gnuplot'; }
  pre.src-haskell:before { content: 'Haskell'; }
  pre.src-hledger:before { content: 'hledger'; }
  pre.src-java:before { content: 'Java'; }
  pre.src-js:before { content: 'Javascript'; }
  pre.src-latex:before { content: 'LaTeX'; }
  pre.src-ledger:before { content: 'Ledger'; }
  pre.src-lisp:before { content: 'Lisp'; }
  pre.src-lilypond:before { content: 'Lilypond'; }
  pre.src-lua:before { content: 'Lua'; }
  pre.src-matlab:before { content: 'MATLAB'; }
  pre.src-mscgen:before { content: 'Mscgen'; }
  pre.src-ocaml:before { content: 'Objective Caml'; }
  pre.src-octave:before { content: 'Octave'; }
  pre.src-org:before { content: 'Org mode'; }
  pre.src-oz:before { content: 'OZ'; }
  pre.src-plantuml:before { content: 'Plantuml'; }
  pre.src-processing:before { content: 'Processing.js'; }
  pre.src-python:before { content: 'Python'; }
  pre.src-R:before { content: 'R'; }
  pre.src-ruby:before { content: 'Ruby'; }
  pre.src-sass:before { content: 'Sass'; }
  pre.src-scheme:before { content: 'Scheme'; }
  pre.src-screen:before { content: 'Gnu Screen'; }
  pre.src-sed:before { content: 'Sed'; }
  pre.src-sh:before { content: 'shell'; }
  pre.src-sql:before { content: 'SQL'; }
  pre.src-sqlite:before { content: 'SQLite'; }
  /* additional languages in org.el's org-babel-load-languages alist */
  pre.src-forth:before { content: 'Forth'; }
  pre.src-io:before { content: 'IO'; }
  pre.src-J:before { content: 'J'; }
  pre.src-makefile:before { content: 'Makefile'; }
  pre.src-maxima:before { content: 'Maxima'; }
  pre.src-perl:before { content: 'Perl'; }
  pre.src-picolisp:before { content: 'Pico Lisp'; }
  pre.src-scala:before { content: 'Scala'; }
  pre.src-shell:before { content: 'Shell Script'; }
  pre.src-ebnf2ps:before { content: 'ebfn2ps'; }
  /* additional language identifiers per "defun org-babel-execute"
       in ob-*.el */
  pre.src-cpp:before  { content: 'C++'; }
  pre.src-abc:before  { content: 'ABC'; }
  pre.src-coq:before  { content: 'Coq'; }
  pre.src-groovy:before  { content: 'Groovy'; }
  /* additional language identifiers from org-babel-shell-names in
     ob-shell.el: ob-shell is the only babel language using a lambda to put
     the execution function name together. */
  pre.src-bash:before  { content: 'bash'; }
  pre.src-csh:before  { content: 'csh'; }
  pre.src-ash:before  { content: 'ash'; }
  pre.src-dash:before  { content: 'dash'; }
  pre.src-ksh:before  { content: 'ksh'; }
  pre.src-mksh:before  { content: 'mksh'; }
  pre.src-posh:before  { content: 'posh'; }
  /* Additional Emacs modes also supported by the LaTeX listings package */
  pre.src-ada:before { content: 'Ada'; }
  pre.src-asm:before { content: 'Assembler'; }
  pre.src-caml:before { content: 'Caml'; }
  pre.src-delphi:before { content: 'Delphi'; }
  pre.src-html:before { content: 'HTML'; }
  pre.src-idl:before { content: 'IDL'; }
  pre.src-mercury:before { content: 'Mercury'; }
  pre.src-metapost:before { content: 'MetaPost'; }
  pre.src-modula-2:before { content: 'Modula-2'; }
  pre.src-pascal:before { content: 'Pascal'; }
  pre.src-ps:before { content: 'PostScript'; }
  pre.src-prolog:before { content: 'Prolog'; }
  pre.src-simula:before { content: 'Simula'; }
  pre.src-tcl:before { content: 'tcl'; }
  pre.src-tex:before { content: 'TeX'; }
  pre.src-plain-tex:before { content: 'Plain TeX'; }
  pre.src-verilog:before { content: 'Verilog'; }
  pre.src-vhdl:before { content: 'VHDL'; }
  pre.src-xml:before { content: 'XML'; }
  pre.src-nxml:before { content: 'XML'; }
  /* add a generic configuration mode; LaTeX export needs an additional
     (add-to-list 'org-latex-listings-langs '(conf " ")) in .emacs */
  pre.src-conf:before { content: 'Configuration File'; }

  table { border-collapse:collapse; }
  caption.t-above { caption-side: top; }
  caption.t-bottom { caption-side: bottom; }
  td, th { vertical-align:top;  }
  th.org-right  { text-align: center;  }
  th.org-left   { text-align: center;   }
  th.org-center { text-align: center; }
  td.org-right  { text-align: right;  }
  td.org-left   { text-align: left;   }
  td.org-center { text-align: center; }
  dt { font-weight: bold; }
  .footpara { display: inline; }
  .footdef  { margin-bottom: 1em; }
  .figure { padding: 1em; }
  .figure p { text-align: center; }
  .equation-container {
    display: table;
    text-align: center;
    width: 100%;
  }
  .equation {
    vertical-align: middle;
  }
  .equation-label {
    display: table-cell;
    text-align: right;
    vertical-align: middle;
  }
  .inlinetask {
    padding: 10px;
    border: 2px solid gray;
    margin: 10px;
    background: #ffffcc;
  }
  #org-div-home-and-up
   { text-align: right; font-size: 70%; white-space: nowrap; }
  textarea { overflow-x: auto; }
  .linenr { font-size: smaller }
  .code-highlighted { background-color: #ffff00; }
  .org-info-js_info-navigation { border-style: none; }
  #org-info-js_console-label
    { font-size: 10px; font-weight: bold; white-space: nowrap; }
  .org-info-js_search-highlight
    { background-color: #ffff00; color: #000000; font-weight: bold; }
  .org-svg { width: 90%; }
  /*]]>*/-->
</style>
<script type="text/javascript">
/*
@licstart  The following is the entire license notice for the
JavaScript code in this tag.

Copyright (C) 2012-2020 Free Software Foundation, Inc.

The JavaScript code in this tag is free software: you can
redistribute it and/or modify it under the terms of the GNU
General Public License (GNU GPL) as published by the Free Software
Foundation, either version 3 of the License, or (at your option)
any later version.  The code is distributed WITHOUT ANY WARRANTY;
without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE.  See the GNU GPL for more details.

As additional permission under GNU GPL version 3 section 7, you
may distribute non-source (e.g., minimized or compacted) forms of
that code without the copy of the GNU GPL normally required by
section 4, provided you include this license notice and a URL
through which recipients can access the Corresponding Source.


@licend  The above is the entire license notice
for the JavaScript code in this tag.
*/
<!--/*--><![CDATA[/*><!--*/
 function CodeHighlightOn(elem, id)
 {
   var target = document.getElementById(id);
   if(null != target) {
     elem.cacheClassElem = elem.className;
     elem.cacheClassTarget = target.className;
     target.className = "code-highlighted";
     elem.className   = "code-highlighted";
   }
 }
 function CodeHighlightOff(elem, id)
 {
   var target = document.getElementById(id);
   if(elem.cacheClassElem)
     elem.className = elem.cacheClassElem;
   if(elem.cacheClassTarget)
     target.className = elem.cacheClassTarget;
 }
/*]]>*///-->
</script>
</head>
<body>
<div id="content">
<h1 class="title">The Seasoned Schemer Notes
<br />
<span class="subtitle">Chapter 11</span>
</h1>
<div id="table-of-contents">
<h2>Table of Contents</h2>
<div id="text-table-of-contents">
<ul>
<li><a href="#org4b4b0a6">1. Prerequisites</a></li>
<li><a href="#org11b99b4">2. Chapter 11</a>
<ul>
<li><a href="#orgc7c9f7e">2.1. member?</a></li>
<li><a href="#org8b7ff98">2.2. two-in-a-row?</a></li>
<li><a href="#orgd050478">2.3. sum-of-prefixes</a></li>
<li><a href="#org619a6af">2.4. scramble</a></li>
</ul>
</li>
</ul>
</div>
</div>

<div id="outline-container-org4b4b0a6" class="outline-2">
<h2 id="org4b4b0a6"><span class="section-number-2">1</span> Prerequisites</h2>
<div class="outline-text-2" id="text-1">
<div class="org-src-container">
<pre class="src src-scheme" id="org7105b13">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">atom?</span>
  (<span style="color: #9FCA56;">&#955;</span> (x)
    (<span style="color: #9FCA56;">and</span> (not (pair? x))
         (not (null? x)))))

(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">one?</span>
  (<span style="color: #9FCA56;">&#955;</span> (x)
    <span style="color: #75715E;">;; </span><span style="color: #41535B;">In theory we could define other things as numbers, for example church</span>
    <span style="color: #75715E;">;; </span><span style="color: #41535B;">numerals.</span>
    (= x 1)))

(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">pick</span>
  (<span style="color: #9FCA56;">&#955;</span> (n lat)
    (<span style="color: #9FCA56;">cond</span>
     [(one? n) (car lat)]
     [<span style="color: #9FCA56;">else</span>
      (pick (- n 1) (cdr lat))])))
</pre>
</div>
</div>
</div>

<div id="outline-container-org11b99b4" class="outline-2">
<h2 id="org11b99b4"><span class="section-number-2">2</span> Chapter 11</h2>
<div class="outline-text-2" id="text-2">
</div>
<div id="outline-container-orgc7c9f7e" class="outline-3">
<h3 id="orgc7c9f7e"><span class="section-number-3">2.1</span> member?</h3>
<div class="outline-text-3" id="text-2-1">
<div class="org-src-container">
<pre class="src src-scheme" id="orgd733661">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">member?</span>
  (<span style="color: #9FCA56;">&#955;</span> (a lat)
    (<span style="color: #9FCA56;">cond</span>
     [(null? lat) #f]
     [<span style="color: #9FCA56;">else</span>
      (<span style="color: #9FCA56;">or</span> (eq? a (car lat))
          (member? a (cdr lat)))])))
</pre>
</div>

<p>
Lets test it:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orgd8f14d1">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">member?</span>
  (<span style="color: #9FCA56;">&#955;</span> (a lat)
    (<span style="color: #9FCA56;">cond</span>
     [(null? lat) #f]
     [<span style="color: #9FCA56;">else</span>
      (<span style="color: #9FCA56;">or</span> (eq? a (car lat))
          (member? a (cdr lat)))])))

(display
 (simple-format
  #f <span style="color: #55B5DB;">"(member? 1 '(3 2 1)) -&gt; ~a\n"</span>
  (member? 1 '(3 2 1))))

(display
 (simple-format
  #f <span style="color: #55B5DB;">"(member? 1 '(3 2 4)) -&gt; ~a\n"</span>
  (member? 1 '(3 2 4))))
</pre>
</div>

<pre class="example">
(member? 1 '(3 2 1)) -&gt; #t
(member? 1 '(3 2 4)) -&gt; #f
</pre>
</div>
</div>

<div id="outline-container-org8b7ff98" class="outline-3">
<h3 id="org8b7ff98"><span class="section-number-3">2.2</span> two-in-a-row?</h3>
<div class="outline-text-3" id="text-2-2">
<p>
A function shall be defined, which determines, whether there are 2 subsequent elements inside a given list, for which <code>eq?</code> is <code>#t</code>.
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orgef0c511">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">is-first?</span>
  (<span style="color: #9FCA56;">&#955;</span> (a lat)
    (<span style="color: #9FCA56;">cond</span>
     [(null? lat) #f]
     [<span style="color: #9FCA56;">else</span> (eq? a (car lat))])))

(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">two-in-a-row?</span>
  (<span style="color: #9FCA56;">&#955;</span> (lat)
    (<span style="color: #9FCA56;">cond</span>
     [(null? lat) #f]
     [<span style="color: #9FCA56;">else</span>
      (<span style="color: #9FCA56;">or</span> (is-first? (car lat) (cdr lat))
          (two-in-a-row? (cdr lat)))])))
</pre>
</div>

<p>
However, this version obscures, that in one case it performs a check twice. When it checks, whether the list is <code>null?</code> in <code>is-first?</code> and returns <code>#f</code>, <code>two-in-a-row?</code> will recur and call itself. Then it will check for a second time, whether the list it receives is <code>null?</code>. To avoid this duplicate check, the book suggests to leave the decision of whether to recur or not to the function, which checks for en empty list first. That is <code>is-first?</code>.
</p>

<p>
Let us try to leave that responsibility to <code>is-first?</code>:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org4b7e422">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">is-first-b?</span>
  (<span style="color: #9FCA56;">&#955;</span> (a lat)
    (<span style="color: #9FCA56;">cond</span>
     [(null? lat) #f]
     [<span style="color: #9FCA56;">else</span>
      (<span style="color: #9FCA56;">or</span> (eq? a (car lat))
          <span style="color: #75715E;">;; </span><span style="color: #41535B;">Not (cdr lat) here! is-first-b? is already given the cdr of the</span>
          <span style="color: #75715E;">;; </span><span style="color: #41535B;">list and the argument ~a~ is the actual car of the list!</span>
          (two-in-a-row? lat))])))

(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">two-in-a-row?</span>
  (<span style="color: #9FCA56;">&#955;</span> (lat)
    (<span style="color: #9FCA56;">cond</span>
     [(null? lat) #f]
     [<span style="color: #9FCA56;">else</span>
      (is-first? (car lat) (cdr lat))])))
</pre>
</div>

<p>
Now we have two functions which are mutually recursive.
</p>

<p>
(Note: There is also a problem of <code class="src src-scheme">(two-in-a-row? lat)</code> in <code>is-first-b?</code> not being in the tail position and thus growing the stack each call.)
</p>

<p>
There is still a duplicate check of <code class="src src-scheme">(null? lat)</code>, because when <code>two-in-a-row?</code> is called from <code>is-first-b?</code>, it checks again, whether the list is empty.
</p>

<p>
When we look at what <code>two-in-a-row?</code> actually does, when called from <code>is-first-b?</code>, we can see, that it does not actually do much. The <code>null?</code> check for the empty list will always be <code>#f</code>, because the same thing was already checked in <code>is-first-b?</code> about <code>lat</code> and <code>lat</code> is given to <code>two-in-a-row?</code>. So <code>two-in-a-row?</code> will always enter the <code>else</code> branch, when called from <code>is-first-b?</code> and the <code>null?</code> check is only useful, when <code>two-in-a-row?</code> is initially called from outside of <code>is-first-b?</code>. This observation leads to the conclusion, that one could write a single function, by modifying <code>is-first-b?</code> a little more, so that the call to <code>two-in-a-row?</code> is no longer needed.
</p>

<p>
The modified version of <code>is-first-b?</code> will be renamed to <code>two-in-a-row-b?</code> to express what it does.
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org963e81a">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">two-in-a-row-b?</span>
  (<span style="color: #9FCA56;">&#955;</span> (preceding lat)
    (<span style="color: #9FCA56;">cond</span>
     [(null? lat) #f]
     [<span style="color: #9FCA56;">else</span>
      (<span style="color: #9FCA56;">or</span> (eq? preceding (car lat))
          (two-in-a-row-b? (car lat) (cdr lat)))])))
</pre>
</div>

<p>
There is still a problem here: <code>two-in-a-row-b?</code> receives always 2 arguments. This is inconvenient and unexpected to work with. One could use <code>two-in-a-row?</code> to avoid this:
</p>

<p>
(Note: The problem of non-tail position of the call to <code>(two-in-a-row-b? (car lat) (cdr lat))</code> still persists.)
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org286f7d7">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">two-in-a-row-b?</span>
  (<span style="color: #9FCA56;">&#955;</span> (preceding lat)
    (<span style="color: #9FCA56;">cond</span>
     [(null? lat) #f]
     [<span style="color: #9FCA56;">else</span>
      (<span style="color: #9FCA56;">or</span> (eq? preceding (car lat))
          (two-in-a-row-b? (car lat) (cdr lat)))])))

(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">two-in-a-row?</span>
  (<span style="color: #9FCA56;">&#955;</span> (lat)
    (<span style="color: #9FCA56;">cond</span>
     [(null? lat) #f]
     [<span style="color: #9FCA56;">else</span>
      (two-in-a-row-b? (car lat) (cdr lat))])))
</pre>
</div>

<p>
This clears up the interface for the user.
</p>

<p>
A tail call optimized version, getting rid of the non-tail position of the recursive call, could be written as follows:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org44f573a">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">two-in-a-row?</span>
  (<span style="color: #9FCA56;">&#955;</span> (preceding lat)
    (<span style="color: #9FCA56;">cond</span>
     [(null? lat) #f]
     <span style="color: #75715E;">;; </span><span style="color: #41535B;">It is a bit meh, that we cannot simply return the result of the</span>
     <span style="color: #75715E;">;; </span><span style="color: #41535B;">expression here and need to write #t instead. Perhaps there is a better</span>
     <span style="color: #75715E;">;; </span><span style="color: #41535B;">way?</span>
     [(eq? preceding (car lat)) #t]
     [<span style="color: #9FCA56;">else</span>
      <span style="color: #75715E;">;; </span><span style="color: #41535B;">Tail-recursive.</span>
      (two-in-a-row-b? (car lat) (cdr lat))])))
</pre>
</div>
</div>
</div>

<div id="outline-container-orgd050478" class="outline-3">
<h3 id="orgd050478"><span class="section-number-3">2.3</span> sum-of-prefixes</h3>
<div class="outline-text-3" id="text-2-3">
<p>
This part introduces a function, which calculates the sum of the prefix for each element in the given list.
</p>

<p>
My first attempt:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org0bab5bf">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">sum-of-prefixes</span>
  (<span style="color: #9FCA56;">&#955;</span> (tup)

    (<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">iter</span>
      (<span style="color: #9FCA56;">&#955;</span> (tup prefix-sum)
        (<span style="color: #9FCA56;">cond</span>
         [(null? tup)
          (cons prefix-sum '())]
         [<span style="color: #9FCA56;">else</span>
          (cons prefix-sum
                (iter  (cdr tup)
                       (+ prefix-sum (car tup))))])))

    (<span style="color: #9FCA56;">cond</span>
     [(null? tup) '()]
     [<span style="color: #9FCA56;">else</span>
      (iter (cdr tup) (car tup))])))
</pre>
</div>

<p>
Let us try it:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orgad83bd4">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">sum-of-prefixes</span>
  (<span style="color: #9FCA56;">&#955;</span> (tup)

    (<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">iter</span>
      (<span style="color: #9FCA56;">&#955;</span> (tup prefix-sum)
        (<span style="color: #9FCA56;">cond</span>
         [(null? tup)
          (cons prefix-sum '())]
         [<span style="color: #9FCA56;">else</span>
          (cons prefix-sum
                (iter  (cdr tup)
                       (+ prefix-sum (car tup))))])))

    (<span style="color: #9FCA56;">cond</span>
     [(null? tup) '()]
     [<span style="color: #9FCA56;">else</span>
      (iter (cdr tup) (car tup))])))

(display
 (simple-format
  #f <span style="color: #55B5DB;">"(sum-of-prefixes '(1 1 1 1 1)) -&gt; ~a\n"</span>
  (sum-of-prefixes '(1 1 1 1 1))))
</pre>
</div>

<pre class="example">
(sum-of-prefixes '(1 1 1 1 1)) -&gt; (1 2 3 4 5)
</pre>


<p>
The book does not make use of inner definitions using <code>define</code>. Instead it uses additional functions defined separately:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org93cd06d">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">sum-of-prefixes</span>
  (<span style="color: #9FCA56;">&#955;</span> (tup)
    <span style="color: #75715E;">;; </span><span style="color: #41535B;">Start with a sum of 0, the neutral element of addition.</span>
    (sum-of-prefixes-b 0 tup)))


(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">sum-of-prefixes-b</span>
  (<span style="color: #9FCA56;">&#955;</span> (sonssf tup)
    (<span style="color: #9FCA56;">cond</span>
     [(null? tup) '()]
     [<span style="color: #9FCA56;">else</span>
      (cons (+ sonssf (car tup))
            (sum-of-prefixes-b (+ sonssf (car tup))
                               (cdr tup)))])))
</pre>
</div>

<p>
Let us try it:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org5c84de0">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">sum-of-prefixes</span>
  (<span style="color: #9FCA56;">&#955;</span> (tup)
    <span style="color: #75715E;">;; </span><span style="color: #41535B;">Start with a sum of 0, the neutral element of addition.</span>
    (sum-of-prefixes-b 0 tup)))


(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">sum-of-prefixes-b</span>
  (<span style="color: #9FCA56;">&#955;</span> (sonssf tup)
    (<span style="color: #9FCA56;">cond</span>
     [(null? tup) '()]
     [<span style="color: #9FCA56;">else</span>
      (cons (+ sonssf (car tup))
            (sum-of-prefixes-b (+ sonssf (car tup))
                               (cdr tup)))])))

(display
 (simple-format
  #f <span style="color: #55B5DB;">"(sum-of-prefixes '(1 1 1 1 1)) -&gt; ~a\n"</span>
  (sum-of-prefixes '(1 1 1 1 1))))
</pre>
</div>

<pre class="example">
(sum-of-prefixes '(1 1 1 1 1)) -&gt; (1 2 3 4 5)
</pre>


<p>
<code>sum-of-prefixes</code> just like in my own solution takes only one argument, so that the caller does not need to think about the implementation detail. The interface is simple. The definition in the book has advantages and disadvantages. An advantage is, that the code is less nested. A disadvantage is, that <code>sum-of-prefixes-b</code> pollutes the namespace of the module, in which it is defined and serves no other purpose than being called by <code>sum-of-prefixes</code>.
</p>

<p>
The point the book makes is, that for recursive functions, which need to know about previous arguments to the function, one can define a helper function, which takes additional arguments. This is stated in the Eleventh Commandment:
</p>

<blockquote>
<p>
Use additional arguments when a function needs to know what other arguments to the function have been like so far.
</p>
</blockquote>
</div>
</div>

<div id="outline-container-org619a6af" class="outline-3">
<h3 id="org619a6af"><span class="section-number-3">2.4</span> scramble</h3>
<div class="outline-text-3" id="text-2-4">
<p>
Next the book goes on to show a weird but in principle similar example <code>scramble</code>, which takes a tuple and calculates another tuple from it:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org5ad0a1f">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">one?</span>
  (<span style="color: #9FCA56;">&#955;</span> (x)
    <span style="color: #75715E;">;; </span><span style="color: #41535B;">In theory we could define other things as numbers, for example church</span>
    <span style="color: #75715E;">;; </span><span style="color: #41535B;">numerals.</span>
    (= x 1)))


(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">pick</span>
  (<span style="color: #9FCA56;">&#955;</span> (n lat)
    (<span style="color: #9FCA56;">cond</span>
     [(one? n) (car lat)]
     [<span style="color: #9FCA56;">else</span>
      (pick (- n 1) (cdr lat))])))


(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">scramble</span>
  (<span style="color: #9FCA56;">&#955;</span> (tup)
    (scramble-b tup '())))


(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">scramble-b</span>
  (<span style="color: #9FCA56;">&#955;</span> (tup rev-pre)
    (<span style="color: #9FCA56;">cond</span>
     [(null? tup) '()]
     [<span style="color: #9FCA56;">else</span>
      (cons
       (pick (car tup)
             <span style="color: #75715E;">;; </span><span style="color: #41535B;">Here we artificially make the reversed prefix longer by the</span>
             <span style="color: #75715E;">;; </span><span style="color: #41535B;">current element, so that pick will pick the correct element.</span>
             (cons (car tup) rev-pre))
       (scramble-b (cdr tup)
                   <span style="color: #75715E;">;; </span><span style="color: #41535B;">We add the current element to the reversed prefix of the</span>
                   <span style="color: #75715E;">;; </span><span style="color: #41535B;">next iteration.</span>
                   (cons (car tup) rev-pre)))])))
</pre>
</div>

<p>
The <code>scramble</code> function looks at each number in the tuple. The number at each position (position = index + 1, or "distance from the start of the list") is substracted from its position and the resulting value is the index of the value, which shall be the final result for the number in the resulting tuple.
</p>

<p>
Let us try it:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org12db267">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">one?</span>
  (<span style="color: #9FCA56;">&#955;</span> (x)
    <span style="color: #75715E;">;; </span><span style="color: #41535B;">In theory we could define other things as numbers, for example church</span>
    <span style="color: #75715E;">;; </span><span style="color: #41535B;">numerals.</span>
    (= x 1)))


(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">pick</span>
  (<span style="color: #9FCA56;">&#955;</span> (n lat)
    (<span style="color: #9FCA56;">cond</span>
     [(one? n) (car lat)]
     [<span style="color: #9FCA56;">else</span>
      (pick (- n 1) (cdr lat))])))


(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">scramble</span>
  (<span style="color: #9FCA56;">&#955;</span> (tup)
    (scramble-b tup '())))


(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">scramble-b</span>
  (<span style="color: #9FCA56;">&#955;</span> (tup rev-pre)
    (<span style="color: #9FCA56;">cond</span>
     [(null? tup) '()]
     [<span style="color: #9FCA56;">else</span>
      (cons
       (pick (car tup)
             <span style="color: #75715E;">;; </span><span style="color: #41535B;">Here we artificially make the reversed prefix longer by the</span>
             <span style="color: #75715E;">;; </span><span style="color: #41535B;">current element, so that pick will pick the correct element.</span>
             (cons (car tup) rev-pre))
       (scramble-b (cdr tup)
                   <span style="color: #75715E;">;; </span><span style="color: #41535B;">We add the current element to the reversed prefix of the</span>
                   <span style="color: #75715E;">;; </span><span style="color: #41535B;">next iteration.</span>
                   (cons (car tup) rev-pre)))])))

(display
 (simple-format
  #f <span style="color: #55B5DB;">"(scramble '(1 2 3 1 2 3 4 1 8 2 10)) -&gt; ~a\n"</span>
  (scramble '(1 2 3 1 2 3 4 1 8 2 10))))
</pre>
</div>

<pre class="example">
(scramble '(1 2 3 1 2 3 4 1 8 2 10)) -&gt; (1 1 1 1 1 1 1 1 2 8 2)
</pre>
</div>
</div>
</div>
</div>
<div id="postamble" class="status">
<p class="date">Date: 2021-08-31 Di 00:00</p>
<p class="author">Author: Zelphir Kaltstahl</p>
<p class="date">Created: 2020-08-31 Mo 21:56</p>
<p class="validation"><a href="http://validator.w3.org/check?uri=referer">Validate</a></p>
</div>
</body>
</html>