code.html 22 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651
  1. <?xml version="1.0" encoding="utf-8"?>
  2. <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
  3. "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
  4. <html xmlns="http://www.w3.org/1999/xhtml" lang="English" xml:lang="English">
  5. <head>
  6. <!-- 2023-02-21 Di 18:07 -->
  7. <meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
  8. <meta name="viewport" content="width=device-width, initial-scale=1" />
  9. <title>The Seasoned Schemer Notes</title>
  10. <meta name="author" content="Zelphir Kaltstahl" />
  11. <meta name="generator" content="Org Mode" />
  12. <style>
  13. #content { max-width: 60em; margin: auto; }
  14. .title { text-align: center;
  15. margin-bottom: .2em; }
  16. .subtitle { text-align: center;
  17. font-size: medium;
  18. font-weight: bold;
  19. margin-top:0; }
  20. .todo { font-family: monospace; color: red; }
  21. .done { font-family: monospace; color: green; }
  22. .priority { font-family: monospace; color: orange; }
  23. .tag { background-color: #eee; font-family: monospace;
  24. padding: 2px; font-size: 80%; font-weight: normal; }
  25. .timestamp { color: #bebebe; }
  26. .timestamp-kwd { color: #5f9ea0; }
  27. .org-right { margin-left: auto; margin-right: 0px; text-align: right; }
  28. .org-left { margin-left: 0px; margin-right: auto; text-align: left; }
  29. .org-center { margin-left: auto; margin-right: auto; text-align: center; }
  30. .underline { text-decoration: underline; }
  31. #postamble p, #preamble p { font-size: 90%; margin: .2em; }
  32. p.verse { margin-left: 3%; }
  33. pre {
  34. border: 1px solid #e6e6e6;
  35. border-radius: 3px;
  36. background-color: #f2f2f2;
  37. padding: 8pt;
  38. font-family: monospace;
  39. overflow: auto;
  40. margin: 1.2em;
  41. }
  42. pre.src {
  43. position: relative;
  44. overflow: auto;
  45. }
  46. pre.src:before {
  47. display: none;
  48. position: absolute;
  49. top: -8px;
  50. right: 12px;
  51. padding: 3px;
  52. color: #555;
  53. background-color: #f2f2f299;
  54. }
  55. pre.src:hover:before { display: inline; margin-top: 14px;}
  56. /* Languages per Org manual */
  57. pre.src-asymptote:before { content: 'Asymptote'; }
  58. pre.src-awk:before { content: 'Awk'; }
  59. pre.src-authinfo::before { content: 'Authinfo'; }
  60. pre.src-C:before { content: 'C'; }
  61. /* pre.src-C++ doesn't work in CSS */
  62. pre.src-clojure:before { content: 'Clojure'; }
  63. pre.src-css:before { content: 'CSS'; }
  64. pre.src-D:before { content: 'D'; }
  65. pre.src-ditaa:before { content: 'ditaa'; }
  66. pre.src-dot:before { content: 'Graphviz'; }
  67. pre.src-calc:before { content: 'Emacs Calc'; }
  68. pre.src-emacs-lisp:before { content: 'Emacs Lisp'; }
  69. pre.src-fortran:before { content: 'Fortran'; }
  70. pre.src-gnuplot:before { content: 'gnuplot'; }
  71. pre.src-haskell:before { content: 'Haskell'; }
  72. pre.src-hledger:before { content: 'hledger'; }
  73. pre.src-java:before { content: 'Java'; }
  74. pre.src-js:before { content: 'Javascript'; }
  75. pre.src-latex:before { content: 'LaTeX'; }
  76. pre.src-ledger:before { content: 'Ledger'; }
  77. pre.src-lisp:before { content: 'Lisp'; }
  78. pre.src-lilypond:before { content: 'Lilypond'; }
  79. pre.src-lua:before { content: 'Lua'; }
  80. pre.src-matlab:before { content: 'MATLAB'; }
  81. pre.src-mscgen:before { content: 'Mscgen'; }
  82. pre.src-ocaml:before { content: 'Objective Caml'; }
  83. pre.src-octave:before { content: 'Octave'; }
  84. pre.src-org:before { content: 'Org mode'; }
  85. pre.src-oz:before { content: 'OZ'; }
  86. pre.src-plantuml:before { content: 'Plantuml'; }
  87. pre.src-processing:before { content: 'Processing.js'; }
  88. pre.src-python:before { content: 'Python'; }
  89. pre.src-R:before { content: 'R'; }
  90. pre.src-ruby:before { content: 'Ruby'; }
  91. pre.src-sass:before { content: 'Sass'; }
  92. pre.src-scheme:before { content: 'Scheme'; }
  93. pre.src-screen:before { content: 'Gnu Screen'; }
  94. pre.src-sed:before { content: 'Sed'; }
  95. pre.src-sh:before { content: 'shell'; }
  96. pre.src-sql:before { content: 'SQL'; }
  97. pre.src-sqlite:before { content: 'SQLite'; }
  98. /* additional languages in org.el's org-babel-load-languages alist */
  99. pre.src-forth:before { content: 'Forth'; }
  100. pre.src-io:before { content: 'IO'; }
  101. pre.src-J:before { content: 'J'; }
  102. pre.src-makefile:before { content: 'Makefile'; }
  103. pre.src-maxima:before { content: 'Maxima'; }
  104. pre.src-perl:before { content: 'Perl'; }
  105. pre.src-picolisp:before { content: 'Pico Lisp'; }
  106. pre.src-scala:before { content: 'Scala'; }
  107. pre.src-shell:before { content: 'Shell Script'; }
  108. pre.src-ebnf2ps:before { content: 'ebfn2ps'; }
  109. /* additional language identifiers per "defun org-babel-execute"
  110. in ob-*.el */
  111. pre.src-cpp:before { content: 'C++'; }
  112. pre.src-abc:before { content: 'ABC'; }
  113. pre.src-coq:before { content: 'Coq'; }
  114. pre.src-groovy:before { content: 'Groovy'; }
  115. /* additional language identifiers from org-babel-shell-names in
  116. ob-shell.el: ob-shell is the only babel language using a lambda to put
  117. the execution function name together. */
  118. pre.src-bash:before { content: 'bash'; }
  119. pre.src-csh:before { content: 'csh'; }
  120. pre.src-ash:before { content: 'ash'; }
  121. pre.src-dash:before { content: 'dash'; }
  122. pre.src-ksh:before { content: 'ksh'; }
  123. pre.src-mksh:before { content: 'mksh'; }
  124. pre.src-posh:before { content: 'posh'; }
  125. /* Additional Emacs modes also supported by the LaTeX listings package */
  126. pre.src-ada:before { content: 'Ada'; }
  127. pre.src-asm:before { content: 'Assembler'; }
  128. pre.src-caml:before { content: 'Caml'; }
  129. pre.src-delphi:before { content: 'Delphi'; }
  130. pre.src-html:before { content: 'HTML'; }
  131. pre.src-idl:before { content: 'IDL'; }
  132. pre.src-mercury:before { content: 'Mercury'; }
  133. pre.src-metapost:before { content: 'MetaPost'; }
  134. pre.src-modula-2:before { content: 'Modula-2'; }
  135. pre.src-pascal:before { content: 'Pascal'; }
  136. pre.src-ps:before { content: 'PostScript'; }
  137. pre.src-prolog:before { content: 'Prolog'; }
  138. pre.src-simula:before { content: 'Simula'; }
  139. pre.src-tcl:before { content: 'tcl'; }
  140. pre.src-tex:before { content: 'TeX'; }
  141. pre.src-plain-tex:before { content: 'Plain TeX'; }
  142. pre.src-verilog:before { content: 'Verilog'; }
  143. pre.src-vhdl:before { content: 'VHDL'; }
  144. pre.src-xml:before { content: 'XML'; }
  145. pre.src-nxml:before { content: 'XML'; }
  146. /* add a generic configuration mode; LaTeX export needs an additional
  147. (add-to-list 'org-latex-listings-langs '(conf " ")) in .emacs */
  148. pre.src-conf:before { content: 'Configuration File'; }
  149. table { border-collapse:collapse; }
  150. caption.t-above { caption-side: top; }
  151. caption.t-bottom { caption-side: bottom; }
  152. td, th { vertical-align:top; }
  153. th.org-right { text-align: center; }
  154. th.org-left { text-align: center; }
  155. th.org-center { text-align: center; }
  156. td.org-right { text-align: right; }
  157. td.org-left { text-align: left; }
  158. td.org-center { text-align: center; }
  159. dt { font-weight: bold; }
  160. .footpara { display: inline; }
  161. .footdef { margin-bottom: 1em; }
  162. .figure { padding: 1em; }
  163. .figure p { text-align: center; }
  164. .equation-container {
  165. display: table;
  166. text-align: center;
  167. width: 100%;
  168. }
  169. .equation {
  170. vertical-align: middle;
  171. }
  172. .equation-label {
  173. display: table-cell;
  174. text-align: right;
  175. vertical-align: middle;
  176. }
  177. .inlinetask {
  178. padding: 10px;
  179. border: 2px solid gray;
  180. margin: 10px;
  181. background: #ffffcc;
  182. }
  183. #org-div-home-and-up
  184. { text-align: right; font-size: 70%; white-space: nowrap; }
  185. textarea { overflow-x: auto; }
  186. .linenr { font-size: smaller }
  187. .code-highlighted { background-color: #ffff00; }
  188. .org-info-js_info-navigation { border-style: none; }
  189. #org-info-js_console-label
  190. { font-size: 10px; font-weight: bold; white-space: nowrap; }
  191. .org-info-js_search-highlight
  192. { background-color: #ffff00; color: #000000; font-weight: bold; }
  193. .org-svg { }
  194. </style>
  195. </head>
  196. <body>
  197. <div id="content" class="content">
  198. <h1 class="title">The Seasoned Schemer Notes
  199. <br />
  200. <span class="subtitle">Chapter 12</span>
  201. </h1>
  202. <div id="table-of-contents" role="doc-toc">
  203. <h2>Table of Contents</h2>
  204. <div id="text-table-of-contents" role="doc-toc">
  205. <ul>
  206. <li><a href="#org62281e9">1. Prerequisites</a>
  207. <ul>
  208. <li><a href="#org1002358">1.1. Y-combinator</a></li>
  209. </ul>
  210. </li>
  211. <li><a href="#org3ba08b7">2. Chapter 12</a>
  212. <ul>
  213. <li><a href="#org7d9c57a">2.1. Recap of Y</a></li>
  214. <li><a href="#org7bdbb9d">2.2. Introduction of <code>letrec</code></a></li>
  215. <li><a href="#orgc07ab58">2.3. <code>multirember</code> with configurable <code>test?</code> predicate</a></li>
  216. <li><a href="#org3d9907f">2.4. Set union implementation</a></li>
  217. </ul>
  218. </li>
  219. </ul>
  220. </div>
  221. </div>
  222. <div id="outline-container-org62281e9" class="outline-2">
  223. <h2 id="org62281e9"><span class="section-number-2">1.</span> Prerequisites</h2>
  224. <div class="outline-text-2" id="text-1">
  225. <div class="org-src-container">
  226. <pre class="src src-scheme" id="org73733f4">(define atom?
  227. (λ (x)
  228. (and (not (pair? x))
  229. (not (null? x)))))
  230. </pre>
  231. </div>
  232. <p>
  233. In theory we could define other things as numbers, for example church numerals.
  234. </p>
  235. <div class="org-src-container">
  236. <pre class="src src-scheme" id="orgb701474">(define one?
  237. (λ (x)
  238. (= x 1)))
  239. </pre>
  240. </div>
  241. <div class="org-src-container">
  242. <pre class="src src-scheme" id="org266a651">(define pick
  243. (λ (n lat)
  244. (cond
  245. [(one? n) (car lat)]
  246. [else
  247. (pick (- n 1) (cdr lat))])))
  248. </pre>
  249. </div>
  250. </div>
  251. <div id="outline-container-org1002358" class="outline-3">
  252. <h3 id="org1002358"><span class="section-number-3">1.1.</span> Y-combinator</h3>
  253. <div class="outline-text-3" id="text-1-1">
  254. <p>
  255. In the first book the Y-combinator was derived. It is again:
  256. </p>
  257. <div class="org-src-container">
  258. <pre class="src src-scheme" id="org3ae2c04">(define Y
  259. (λ (proc)
  260. ((λ (f) (f f))
  261. (λ (f)
  262. (proc
  263. (λ (x) ((f f) x)))))))
  264. </pre>
  265. </div>
  266. </div>
  267. </div>
  268. </div>
  269. <div id="outline-container-org3ba08b7" class="outline-2">
  270. <h2 id="org3ba08b7"><span class="section-number-2">2.</span> Chapter 12</h2>
  271. <div class="outline-text-2" id="text-2">
  272. </div>
  273. <div id="outline-container-org7d9c57a" class="outline-3">
  274. <h3 id="org7d9c57a"><span class="section-number-3">2.1.</span> Recap of Y</h3>
  275. <div class="outline-text-3" id="text-2-1">
  276. </div>
  277. <div id="outline-container-org45f1193" class="outline-4">
  278. <h4 id="org45f1193"><span class="section-number-4">2.1.1.</span> Recursive <code>length</code> function using <code>Y</code></h4>
  279. <div class="outline-text-4" id="text-2-1-1">
  280. <p>
  281. The length function is injected as an argument. Thus the expression is not referring to itself, but only ever to its argument.
  282. </p>
  283. <p>
  284. The inner part looks just like the usual recursive length function. It is using an argument (<code>length</code>) as the thing it calls in the recursive case though.
  285. </p>
  286. <div class="org-src-container">
  287. <pre class="src src-scheme" id="org5d558ae">(define Y
  288. (λ (proc)
  289. ((λ (f) (f f))
  290. (λ (f)
  291. (proc
  292. (λ (x) ((f f) x)))))))
  293. (define length
  294. (Y (λ (length)
  295. (λ (lst)
  296. (cond
  297. [(null? lst) 0]
  298. [else
  299. (+ (length (cdr lst)) 1)])))))
  300. (simple-format #t "(length '(a b c d)) = ~a\n" (length '(a b c d)))
  301. </pre>
  302. </div>
  303. <pre class="example" id="orgf052f54">
  304. (length '(a b c d)) = 4
  305. </pre>
  306. </div>
  307. </div>
  308. <div id="outline-container-org7bbcf85" class="outline-4">
  309. <h4 id="org7bbcf85"><span class="section-number-4">2.1.2.</span> <code>multirember</code> (remove member multiple times) function using <code>Y</code></h4>
  310. <div class="outline-text-4" id="text-2-1-2">
  311. <p>
  312. The argument of <code>Y</code> is always a lambda expression, which takes as argument the function to be called in the recursive case. That function itself returns a function, which takes the actual input. In this example that is a list of atoms.
  313. </p>
  314. <div class="org-src-container">
  315. <pre class="src src-scheme" id="orga94e6ec">(define Y
  316. (λ (proc)
  317. ((λ (f) (f f))
  318. (λ (f)
  319. (proc
  320. (λ (x) ((f f) x)))))))
  321. (define multirember
  322. (λ (a lat)
  323. ((Y (λ (mr)
  324. (λ (lat)
  325. (cond
  326. [(null? lat) '()]
  327. [(eq? a (car lat))
  328. (mr (cdr lat))]
  329. [else
  330. (cons (car lat)
  331. (mr (cdr lat)))]))))
  332. lat)))
  333. </pre>
  334. </div>
  335. </div>
  336. <div id="outline-container-orga7cdd06" class="outline-5">
  337. <h5 id="orga7cdd06"><span class="section-number-5">2.1.2.1.</span> Usage</h5>
  338. <div class="outline-text-5" id="text-2-1-2-1">
  339. <div class="org-src-container">
  340. <pre class="src src-scheme" id="orgefe9736">(multirember 'a '(a b c a d))
  341. </pre>
  342. </div>
  343. </div>
  344. </div>
  345. <div id="outline-container-orgc6a6ae5" class="outline-5">
  346. <h5 id="orgc6a6ae5"><span class="section-number-5">2.1.2.2.</span> Results</h5>
  347. <div class="outline-text-5" id="text-2-1-2-2">
  348. <pre class="example" id="orgbb0d937">
  349. (b c d)
  350. </pre>
  351. </div>
  352. </div>
  353. </div>
  354. </div>
  355. <div id="outline-container-org7bdbb9d" class="outline-3">
  356. <h3 id="org7bdbb9d"><span class="section-number-3">2.2.</span> Introduction of <code>letrec</code></h3>
  357. <div class="outline-text-3" id="text-2-2">
  358. <p>
  359. <code>letrec</code> offers a way to avoid using <code>Y</code> and possibly get a more easily understandable definition of recursive functions.
  360. </p>
  361. </div>
  362. <div id="outline-container-org7e21e3c" class="outline-4">
  363. <h4 id="org7e21e3c"><span class="section-number-4">2.2.1.</span> <code>multirember</code> (remove member multiple times) function using <code>letrec</code></h4>
  364. <div class="outline-text-4" id="text-2-2-1">
  365. <p>
  366. The following definition of <code>multirember</code> makes use of <code>letrec</code> instead of <code>Y</code>, because the definition of <code>mr</code> inside makes use of <code>mr</code> recursively itself. A normal <code>let</code> would not work here. The recursive <code>mr</code> is then returned and applied to <code>lat</code>, a list of atoms. This chapter introduces <code>letrec</code>.
  367. </p>
  368. <div class="org-src-container">
  369. <pre class="src src-scheme" id="org28e8458">(define multirember
  370. (λ (a lat)
  371. ((letrec
  372. ([mr (λ (lat)
  373. (cond
  374. [(null? lat) '()]
  375. [(eq? a (car lat))
  376. (mr (cdr lat))]
  377. [else
  378. (cons (car lat)
  379. (mr (cdr lat)))]))])
  380. mr)
  381. lat)))
  382. </pre>
  383. </div>
  384. </div>
  385. <div id="outline-container-orge588824" class="outline-5">
  386. <h5 id="orge588824"><span class="section-number-5">2.2.1.1.</span> Usage</h5>
  387. <div class="outline-text-5" id="text-2-2-1-1">
  388. <div class="org-src-container">
  389. <pre class="src src-scheme" id="orgdca6b96">(multirember 'a '(a b c a d))
  390. </pre>
  391. </div>
  392. </div>
  393. </div>
  394. <div id="outline-container-orgfbe4282" class="outline-5">
  395. <h5 id="orgfbe4282"><span class="section-number-5">2.2.1.2.</span> Result</h5>
  396. <div class="outline-text-5" id="text-2-2-1-2">
  397. <pre class="example" id="org601f624">
  398. (b c d)
  399. </pre>
  400. </div>
  401. </div>
  402. <div id="outline-container-org2145402" class="outline-5">
  403. <h5 id="org2145402"><span class="section-number-5">2.2.1.3.</span> A more readable version</h5>
  404. <div class="outline-text-5" id="text-2-2-1-3">
  405. <p>
  406. Using the following definition, one can avoid 1 wrapping of parentheses of the <code>letrec</code> expression and move it into the value part of the <code>letrec</code> expression:
  407. </p>
  408. <div class="org-src-container">
  409. <pre class="src src-scheme" id="org7cb3947">(define multirember
  410. (λ (a lat)
  411. (letrec
  412. ([mr (λ (lat)
  413. (cond
  414. [(null? lat) '()]
  415. [(eq? a (car lat))
  416. (mr (cdr lat))]
  417. [else
  418. (cons (car lat)
  419. (mr (cdr lat)))]))])
  420. (mr lat))))
  421. </pre>
  422. </div>
  423. <p>
  424. This seems a bit more readable to me.
  425. </p>
  426. </div>
  427. </div>
  428. </div>
  429. </div>
  430. <div id="outline-container-orgc07ab58" class="outline-3">
  431. <h3 id="orgc07ab58"><span class="section-number-3">2.3.</span> <code>multirember</code> with configurable <code>test?</code> predicate</h3>
  432. <div class="outline-text-3" id="text-2-3">
  433. <p>
  434. We can use 1 layer of currying to make a "factory" of <code>multirember</code> functions, which know how to test for whether an element should be removed from a list.
  435. </p>
  436. <div class="org-src-container">
  437. <pre class="src src-scheme" id="org3f2689d">(define make-multirember
  438. (λ (test?)
  439. (λ (a lat)
  440. (letrec
  441. ([mr (λ (lat)
  442. (cond
  443. [(null? lat) '()]
  444. [(test? a (car lat))
  445. (mr (cdr lat))]
  446. [else
  447. (cons (car lat)
  448. (mr (cdr lat)))]))])
  449. (mr lat)))))
  450. </pre>
  451. </div>
  452. <div class="org-src-container">
  453. <pre class="src src-scheme" id="org58b2036">(simple-format
  454. #t "~a\n"
  455. ((make-multirember =) 1 '(2 4 6 12 1 2)))
  456. </pre>
  457. </div>
  458. <pre class="example" id="org5adaccb">
  459. (2 4 6 12 2)
  460. </pre>
  461. </div>
  462. </div>
  463. <div id="outline-container-org3d9907f" class="outline-3">
  464. <h3 id="org3d9907f"><span class="section-number-3">2.4.</span> Set union implementation</h3>
  465. <div class="outline-text-3" id="text-2-4">
  466. </div>
  467. <div id="outline-container-org421f055" class="outline-4">
  468. <h4 id="org421f055"><span class="section-number-4">2.4.1.</span> First version</h4>
  469. <div class="outline-text-4" id="text-2-4-1">
  470. <div class="org-src-container">
  471. <pre class="src src-scheme" id="org8a26843">(define member? member)
  472. (define union
  473. (λ (set1 set2)
  474. (cond
  475. [(null? set1) set2]
  476. [(member? (car set1) set2)
  477. (union (cdr set1) set2)]
  478. [else
  479. (cons (car set1)
  480. (union (cdr set1) set2))])))
  481. (simple-format
  482. #t "~a\n"
  483. (union '(a b c d) '(s b a e)))
  484. </pre>
  485. </div>
  486. <pre class="example" id="orgfbb2bd4">
  487. (c d s b a e)
  488. </pre>
  489. </div>
  490. </div>
  491. <div id="outline-container-org55c30ea" class="outline-4">
  492. <h4 id="org55c30ea"><span class="section-number-4">2.4.2.</span> Second version with captured <code>set2</code></h4>
  493. <div class="outline-text-4" id="text-2-4-2">
  494. <p>
  495. The text has objections about the fact, that <code>union</code> is always called with 2 arguments, the 2 sets to build the union of, although <code>set2</code> never changes. It argues, that one can make the recursive calls simpler, by capturing <code>set2</code> outside of the recursive part.
  496. </p>
  497. <div class="org-src-container">
  498. <pre class="src src-scheme" id="org2963c82">(define member? member)
  499. (define union
  500. (λ (set1 set2)
  501. (letrec ([U
  502. (λ (set1°)
  503. (cond
  504. [(null? set1°) set2]
  505. [(member? (car set1°) set2)
  506. (U (cdr set1°))]
  507. [else
  508. (cons (car set1°)
  509. (U (cdr set1°)))]))])
  510. (U set1))))
  511. (simple-format
  512. #t "~a\n"
  513. (union '(a b c d) '(s b a e)))
  514. </pre>
  515. </div>
  516. <pre class="example" id="orgbd9a07f">
  517. (c d s b a e)
  518. </pre>
  519. </div>
  520. </div>
  521. <div id="outline-container-org5b59857" class="outline-4">
  522. <h4 id="org5b59857"><span class="section-number-4">2.4.3.</span> Third version with protected <code>member?</code></h4>
  523. <div class="outline-text-4" id="text-2-4-3">
  524. <p>
  525. The text also notes, that <code>union</code> relies on <code>member?</code>, which is implemented elsewhere. <code>union</code> serves as an example. <code>member?</code> or <code>member</code> is usually implemented in Scheme dialects, so it will not suddenly change. However, if it were a function, which were to change for example the order of its arguments, then we would have to adapt <code>union</code> and all other functions depending on <code>member?</code> as well. For this reason, the text argues for internalizing the definition of <code>member?</code> inside of <code>union</code>.
  526. </p>
  527. <div class="org-src-container">
  528. <pre class="src src-scheme" id="org0854a57">(define union
  529. (λ (set1 set2)
  530. (letrec ([U
  531. (λ (set1°)
  532. (cond
  533. [(null? set1°) set2]
  534. [(member? (car set1°) set2)
  535. (U (cdr set1°))]
  536. [else
  537. (cons (car set1°)
  538. (U (cdr set1°)))]))]
  539. [member?
  540. (λ (elem lst)
  541. (letrec ([M?
  542. (λ (lst°)
  543. (cond
  544. [(null? lst°) #f]
  545. [(eq? elem (car lst°)) #t]
  546. [else (M? (cdr lst°))]))])
  547. (M? lst)))])
  548. (U set1))))
  549. (simple-format
  550. #t "~a\n"
  551. (union '(a b c d) '(s b a e)))
  552. </pre>
  553. </div>
  554. <pre class="example" id="orgc1c53da">
  555. (c d s b a e)
  556. </pre>
  557. </div>
  558. </div>
  559. <div id="outline-container-org568277c" class="outline-4">
  560. <h4 id="org568277c"><span class="section-number-4">2.4.4.</span> Fourth version</h4>
  561. <div class="outline-text-4" id="text-2-4-4">
  562. <p>
  563. Maybe instead of defining a whole <code>member?</code> inside <code>letrec</code> one could make a minimalistic wrapper for the <code>member</code> function already defined in Scheme. This way we would not reimplement things which are already in our language:
  564. </p>
  565. <div class="org-src-container">
  566. <pre class="src src-scheme" id="orgfe921f4">(define union
  567. (λ (set1 set2)
  568. (letrec ([U
  569. (λ (set1°)
  570. (cond
  571. [(null? set1°) set2]
  572. [(member? (car set1°) set2)
  573. (U (cdr set1°))]
  574. [else
  575. (cons (car set1°)
  576. (U (cdr set1°)))]))]
  577. [member?
  578. (λ (elem lst)
  579. (letrec ([M?
  580. (λ (lst°)
  581. (not (null? (member elem lst))))])
  582. (M? lst)))])
  583. (U set1))))
  584. (simple-format
  585. #t "~a\n"
  586. (union '(a b c d) '(s b a e)))
  587. </pre>
  588. </div>
  589. <p>
  590. The book has a bootstrapping approach, so it opts to implement <code>member?</code> inside <code>union</code>. A disadvantage of that is, that it cannot be separately unit-tested. Perhaps the philosophy there is, that encapsulation is more important than tests.
  591. </p>
  592. </div>
  593. </div>
  594. </div>
  595. </div>
  596. </div>
  597. <div id="postamble" class="status">
  598. <p class="date">Date: 2021-08-31 Di 00:00</p>
  599. <p class="author">Author: Zelphir Kaltstahl</p>
  600. <p class="date">Created: 2023-02-21 Di 18:07</p>
  601. <p class="validation"><a href="https://validator.w3.org/check?uri=referer">Validate</a></p>
  602. </div>
  603. </body>
  604. </html>