• R/O
  • HTTP
  • SSH
  • HTTPS

Thun: Commit

Interpreter and library.


Commit MetaInfo

Révision2cc0ea054869e10750743cd6dfe6c7fb310f1d17 (tree)
l'heure2021-12-24 12:08:30
AuteurSimon Forman <sforman@hush...>
CommiterSimon Forman

Message de Log

Some work on docs.

Change Summary

Modification

--- a/docs/Advent_of_Code_2017_December_2nd.ipynb
+++ b/docs/Advent_of_Code_2017_December_2nd.ipynb
@@ -20,22 +20,8 @@
2020 "* The second row's largest and smallest values are 7 and 3, and their difference is 4.\n",
2121 "* The third row's difference is 6.\n",
2222 "\n",
23- "In this example, the spreadsheet's checksum would be 8 + 4 + 6 = 18."
24- ]
25- },
26- {
27- "cell_type": "code",
28- "execution_count": 1,
29- "metadata": {},
30- "outputs": [],
31- "source": [
32- "from notebook_preamble import J, V, define"
33- ]
34- },
35- {
36- "cell_type": "markdown",
37- "metadata": {},
38- "source": [
23+ "In this example, the spreadsheet's checksum would be 8 + 4 + 6 = 18.\n",
24+ "\n",
3925 "I'll assume the input is a Joy sequence of sequences of integers.\n",
4026 "\n",
4127 " [[5 1 9 5]\n",
@@ -44,40 +30,41 @@
4430 "\n",
4531 "So, obviously, the initial form will be a `step` function:\n",
4632 "\n",
47- " AoC2017.2 == 0 swap [F +] step"
48- ]
49- },
50- {
51- "cell_type": "markdown",
52- "metadata": {},
53- "source": [
33+ " AoC2017.2 == 0 swap [F +] step\n",
34+ "\n",
5435 "This function `F` must get the `max` and `min` of a row of numbers and subtract. We can define a helper function `maxmin` which does this:"
5536 ]
5637 },
5738 {
5839 "cell_type": "code",
59- "execution_count": 2,
40+ "execution_count": 1,
6041 "metadata": {},
61- "outputs": [],
42+ "outputs": [
43+ {
44+ "name": "stdout",
45+ "output_type": "stream",
46+ "text": []
47+ }
48+ ],
6249 "source": [
63- "define('maxmin [max] [min] cleave')"
50+ "[maxmin [max] [min] cleave] inscribe"
6451 ]
6552 },
6653 {
6754 "cell_type": "code",
68- "execution_count": 3,
55+ "execution_count": 2,
6956 "metadata": {},
7057 "outputs": [
7158 {
7259 "name": "stdout",
7360 "output_type": "stream",
7461 "text": [
75- "3 1\n"
62+ "3 1"
7663 ]
7764 }
7865 ],
7966 "source": [
80- "J('[1 2 3] maxmin')"
67+ "[1 2 3] maxmin"
8168 ]
8269 },
8370 {
@@ -93,34 +80,40 @@
9380 },
9481 {
9582 "cell_type": "code",
96- "execution_count": 4,
83+ "execution_count": 3,
9784 "metadata": {},
98- "outputs": [],
85+ "outputs": [
86+ {
87+ "name": "stdout",
88+ "output_type": "stream",
89+ "text": [
90+ "3 1"
91+ ]
92+ }
93+ ],
9994 "source": [
100- "define('AoC2017.2 [maxmin - +] step_zero')"
95+ "[AoC2017.2 [maxmin - +] step_zero] inscribe"
10196 ]
10297 },
10398 {
10499 "cell_type": "code",
105- "execution_count": 5,
100+ "execution_count": 4,
106101 "metadata": {},
107102 "outputs": [
108103 {
109104 "name": "stdout",
110105 "output_type": "stream",
111106 "text": [
112- "18\n"
107+ "18"
113108 ]
114109 }
115110 ],
116111 "source": [
117- "J('''\n",
112+ "clear\n",
118113 "\n",
119114 "[[5 1 9 5]\n",
120115 " [7 5 3]\n",
121- " [2 4 6 8]] AoC2017.2\n",
122- "\n",
123- "''')"
116+ " [2 4 6 8]] AoC2017.2"
124117 ]
125118 },
126119 {
@@ -146,36 +139,327 @@
146139 },
147140 {
148141 "cell_type": "code",
149- "execution_count": 6,
142+ "execution_count": 24,
143+ "metadata": {},
144+ "outputs": [
145+ {
146+ "name": "stdout",
147+ "output_type": "stream",
148+ "text": []
149+ }
150+ ],
151+ "source": [
152+ "clear"
153+ ]
154+ },
155+ {
156+ "cell_type": "code",
157+ "execution_count": 25,
158+ "metadata": {},
159+ "outputs": [
160+ {
161+ "name": "stdout",
162+ "output_type": "stream",
163+ "text": [
164+ "[2 5 8 9]"
165+ ]
166+ }
167+ ],
168+ "source": [
169+ "[5 9 2 8] sort"
170+ ]
171+ },
172+ {
173+ "cell_type": "code",
174+ "execution_count": 26,
175+ "metadata": {},
176+ "outputs": [
177+ {
178+ "name": "stdout",
179+ "output_type": "stream",
180+ "text": [
181+ "[5 8 9] [2 mod not]"
182+ ]
183+ }
184+ ],
185+ "source": [
186+ "uncons swap [mod not] cons"
187+ ]
188+ },
189+ {
190+ "cell_type": "code",
191+ "execution_count": 23,
192+ "metadata": {},
193+ "outputs": [
194+ {
195+ "name": "stdout",
196+ "output_type": "stream",
197+ "text": [
198+ "[false true false]"
199+ ]
200+ }
201+ ],
202+ "source": [
203+ "map"
204+ ]
205+ },
206+ {
207+ "cell_type": "code",
208+ "execution_count": 27,
209+ "metadata": {},
210+ "outputs": [
211+ {
212+ "name": "stdout",
213+ "output_type": "stream",
214+ "text": [
215+ "false true false"
216+ ]
217+ }
218+ ],
219+ "source": [
220+ "step"
221+ ]
222+ },
223+ {
224+ "cell_type": "code",
225+ "execution_count": 28,
226+ "metadata": {},
227+ "outputs": [
228+ {
229+ "name": "stdout",
230+ "output_type": "stream",
231+ "text": [
232+ "false true false"
233+ ]
234+ }
235+ ],
236+ "source": [
237+ "[P 2 mod not] inscribe"
238+ ]
239+ },
240+ {
241+ "cell_type": "code",
242+ "execution_count": 31,
243+ "metadata": {},
244+ "outputs": [
245+ {
246+ "name": "stdout",
247+ "output_type": "stream",
248+ "text": [
249+ "[4 5 6 7]"
250+ ]
251+ }
252+ ],
253+ "source": [
254+ "clear\n",
255+ "[4 5 6 7]"
256+ ]
257+ },
258+ {
259+ "cell_type": "code",
260+ "execution_count": 30,
261+ "metadata": {},
262+ "outputs": [
263+ {
264+ "name": "stdout",
265+ "output_type": "stream",
266+ "text": [
267+ "[true false true false]"
268+ ]
269+ }
270+ ],
271+ "source": [
272+ "[P] map"
273+ ]
274+ },
275+ {
276+ "cell_type": "code",
277+ "execution_count": 32,
278+ "metadata": {},
279+ "outputs": [
280+ {
281+ "name": "stdout",
282+ "output_type": "stream",
283+ "text": [
284+ "[] [4 5 6 7]"
285+ ]
286+ }
287+ ],
288+ "source": [
289+ "[] swap"
290+ ]
291+ },
292+ {
293+ "cell_type": "code",
294+ "execution_count": 33,
295+ "metadata": {},
296+ "outputs": [
297+ {
298+ "name": "stdout",
299+ "output_type": "stream",
300+ "text": [
301+ "[] 4"
302+ ]
303+ }
304+ ],
305+ "source": [
306+ "first"
307+ ]
308+ },
309+ {
310+ "cell_type": "code",
311+ "execution_count": 34,
312+ "metadata": {},
313+ "outputs": [
314+ {
315+ "name": "stdout",
316+ "output_type": "stream",
317+ "text": [
318+ "[4]"
319+ ]
320+ }
321+ ],
322+ "source": [
323+ "[P][swons][pop]ifte"
324+ ]
325+ },
326+ {
327+ "cell_type": "code",
328+ "execution_count": 35,
329+ "metadata": {},
330+ "outputs": [
331+ {
332+ "name": "stdout",
333+ "output_type": "stream",
334+ "text": [
335+ "[4] 5"
336+ ]
337+ }
338+ ],
339+ "source": [
340+ "5"
341+ ]
342+ },
343+ {
344+ "cell_type": "code",
345+ "execution_count": 36,
346+ "metadata": {},
347+ "outputs": [
348+ {
349+ "name": "stdout",
350+ "output_type": "stream",
351+ "text": [
352+ "[4]"
353+ ]
354+ }
355+ ],
356+ "source": [
357+ "[P][swons][pop]ifte"
358+ ]
359+ },
360+ {
361+ "cell_type": "code",
362+ "execution_count": null,
363+ "metadata": {},
364+ "outputs": [],
365+ "source": []
366+ },
367+ {
368+ "cell_type": "code",
369+ "execution_count": 37,
370+ "metadata": {},
371+ "outputs": [
372+ {
373+ "name": "stdout",
374+ "output_type": "stream",
375+ "text": [
376+ "[4 5 6 7]"
377+ ]
378+ }
379+ ],
380+ "source": [
381+ "clear\n",
382+ "[4 5 6 7]"
383+ ]
384+ },
385+ {
386+ "cell_type": "code",
387+ "execution_count": 38,
150388 "metadata": {},
151389 "outputs": [
152390 {
153391 "name": "stdout",
154392 "output_type": "stream",
155393 "text": [
156- "[9 8 5 2]\n"
394+ "[6 4]"
157395 ]
158396 }
159397 ],
160398 "source": [
161- "J('[5 9 2 8] sort reverse')"
399+ "[] swap [[P][swons][pop]ifte] step"
400+ ]
401+ },
402+ {
403+ "cell_type": "markdown",
404+ "metadata": {},
405+ "source": [
406+ " [...] [P] filter\n",
407+ " -----------------------------------------\n",
408+ " [] [...] [[P][swons][pop]ifte] step\n",
409+ "\n",
410+ "But that `[]` could get in the way of `P`, no?"
162411 ]
163412 },
164413 {
165414 "cell_type": "code",
166- "execution_count": 7,
415+ "execution_count": null,
416+ "metadata": {},
417+ "outputs": [],
418+ "source": []
419+ },
420+ {
421+ "cell_type": "code",
422+ "execution_count": null,
423+ "metadata": {},
424+ "outputs": [],
425+ "source": []
426+ },
427+ {
428+ "cell_type": "code",
429+ "execution_count": null,
430+ "metadata": {},
431+ "outputs": [],
432+ "source": []
433+ },
434+ {
435+ "cell_type": "code",
436+ "execution_count": null,
437+ "metadata": {},
438+ "outputs": [],
439+ "source": []
440+ },
441+ {
442+ "cell_type": "code",
443+ "execution_count": null,
444+ "metadata": {},
445+ "outputs": [],
446+ "source": []
447+ },
448+ {
449+ "cell_type": "code",
450+ "execution_count": 9,
167451 "metadata": {},
168452 "outputs": [
169453 {
170454 "name": "stdout",
171455 "output_type": "stream",
172456 "text": [
173- "[8 5 2] [9 divmod] [8 5 2]\n"
457+ "[8 5 2] [9 divmod] [8 5 2]"
174458 ]
175459 }
176460 ],
177461 "source": [
178- "J('[9 8 5 2] uncons [swap [divmod] cons] dupdip')"
462+ "uncons [swap [divmod] cons] dupdip"
179463 ]
180464 },
181465 {
@@ -532,21 +816,14 @@
532816 ],
533817 "metadata": {
534818 "kernelspec": {
535- "display_name": "Python 2",
536- "language": "python",
537- "name": "python2"
819+ "display_name": "Joypy",
820+ "language": "",
821+ "name": "thun"
538822 },
539823 "language_info": {
540- "codemirror_mode": {
541- "name": "ipython",
542- "version": 3
543- },
544- "file_extension": ".py",
545- "mimetype": "text/x-python",
546- "name": "python",
547- "nbconvert_exporter": "python",
548- "pygments_lexer": "ipython3",
549- "version": "3.8.3"
824+ "file_extension": ".joy",
825+ "mimetype": "text/plain",
826+ "name": "Joy"
550827 }
551828 },
552829 "nbformat": 4,
--- a/docs/Quadratic.ipynb
+++ b/docs/Quadratic.ipynb
@@ -219,21 +219,21 @@
219219 ],
220220 "metadata": {
221221 "kernelspec": {
222- "display_name": "Python 2",
222+ "display_name": "Python 3 (ipykernel)",
223223 "language": "python",
224- "name": "python2"
224+ "name": "python3"
225225 },
226226 "language_info": {
227227 "codemirror_mode": {
228228 "name": "ipython",
229- "version": 2
229+ "version": 3
230230 },
231231 "file_extension": ".py",
232232 "mimetype": "text/x-python",
233233 "name": "python",
234234 "nbconvert_exporter": "python",
235- "pygments_lexer": "ipython2",
236- "version": "2.7.15"
235+ "pygments_lexer": "ipython3",
236+ "version": "3.7.10"
237237 }
238238 },
239239 "nbformat": 4,
--- a/docs/Recursion_Combinators.ipynb
+++ b/docs/Recursion_Combinators.ipynb
@@ -6,22 +6,25 @@
66 "source": [
77 "# Recursion Combinators\n",
88 "\n",
9- "This article describes the `genrec` combinator and how to use it, then several generic specializations.\n",
10- "\n",
9+ "This article describes the `genrec` combinator and how to use it, and then gives several specializations.\n",
10+ "The `genrec` combinator isn't the only way to make recursive functions in Joy, you can also use the `x` combinator with a `branch` to create recursive functions. (Because definitions aren't checked for self-reference you can also define recursive functions directly in definitions, but this, I believe, should be considered bad form.)"
11+ ]
12+ },
13+ {
14+ "cell_type": "markdown",
15+ "metadata": {},
16+ "source": [
1117 "## General Recursive Function\n",
1218 "\n",
13- "In Joy recursive functions are defined by four quoted programs and the `genrec` combinator.\n",
19+ "In Joy recursive functions are defined by the `genrec` combinator which accepts four quoted programs:\n",
1420 "\n",
1521 " F == [if] [then] [rec1] [rec2] genrec\n",
1622 "\n",
1723 "This can be thought of as transforming into an \"if..then..else\" expression using the `ifte` combinator and containing a quoted copy of itself in the \"else\" branch:\n",
1824 "\n",
19- " [if] [then] [rec1] [rec2] genrec\n",
20- " ---------------------------------------------------------------------\n",
21- " [if] [then] [rec1 [[if] [then] [rec1] [rec2] genrec] rec2] ifte\n",
22- "\n",
25+ " F == [if] [then] [rec1 [F] rec2] ifte\n",
2326 "\n",
24- "From \"Recursion Theory and Joy\" (j05cmp.html) by Manfred von Thun:\n",
27+ "From [\"Recursion Theory and Joy\"](https://www.kevinalbrecht.com/code/joy-mirror/j05cmp.html) by Manfred von Thun:\n",
2528 "\n",
2629 "> \"The genrec combinator takes four program parameters in addition to\n",
2730 "whatever data parameters it needs. Fourth from the top is an if-part,\n",
@@ -34,29 +37,23 @@
3437 "form. Typically it will then execute the bundled form, either with i or\n",
3538 "with app2, or some other combinator.\"\n",
3639 "\n",
37- "## Designing Recursive Functions\n",
38- "\n",
39- "Fix your base case and test functions and then treat `R1` and `R2` as an else-part \"sandwiching\" a quotation of the whole function.\n",
40- "\n",
41- "For example, given a (general recursive) function `F`:\n",
42- "\n",
43- " F == [P] [T] [R1] [R2] genrec\n",
44- " == [P] [T] [R1 [F] R2] ifte\n",
45- "\n",
46- "Derive `R1` and `R2` from:\n",
47- "\n",
48- " ... R1 [F] R2\n",
49- "\n",
50- "Set the stack arguments in front and figure out what `R1` and `R2` have to do to apply the quoted `[F]` in the proper way.\n",
51- "\n",
40+ "It's a fantastic paper and if you like this you should really go read that.\n",
41+ "This notebook is much lighter.\n",
42+ "We're going to look at things from the point-of-view of the [\"Bananas, Lenses, & Barbed Wire\"](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.125) paper, all about hylomorphisms, anamorphisms, catamorphisms, etc."
43+ ]
44+ },
45+ {
46+ "cell_type": "markdown",
47+ "metadata": {},
48+ "source": [
5249 "## [Hylomorphism](https://en.wikipedia.org/wiki/Hylomorphism_%28computer_science%29)\n",
5350 "\n",
54- "A [hylomorphism](https://en.wikipedia.org/wiki/Hylomorphism_%28computer_science%29) is a recursive function `H` that converts a value of type `A` into a value of type `C` by means of:\n",
51+ "A [hylomorphism](https://en.wikipedia.org/wiki/Hylomorphism_%28computer_science%29) is a recursive function `H` that converts a value of type `𝔸` into a value of type `ℂ` by means of:\n",
5552 "\n",
56- "- A generator `G` from `A` to `(B, A)`\n",
57- "- A combiner `Q` from `(B, C)` to `C`\n",
58- "- A predicate `P` from `A` to `Bool` to detect the base case\n",
59- "- A base case value `c` of type `C`, and\n",
53+ "- A generator `G` from `𝔸` to `(𝔹, 𝔸)`\n",
54+ "- A combiner `Q` from `(𝔹, ℂ)` to `ℂ`\n",
55+ "- A predicate `P` from `𝔸` to `Bool` to detect the base case\n",
56+ "- A base case value `c` of type `ℂ`, and\n",
6057 "- Recursive calls (zero or more); it has a \"call stack in the form of a cons list\".\n",
6158 "\n",
6259 "It may be helpful to see this function implemented in pseudocode (Python).\n",
@@ -72,22 +69,24 @@
7269 "\n",
7370 " return H\n",
7471 "\n",
75- "Cf. [\"Bananas, Lenses, & Barbed Wire\"](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.125)\n",
76- "\n",
77- "Note that during evaluation of `H()` the intermediate `b` values are stored in the Python call stack. This is what is meant by \"call stack in the form of a cons list\".\n",
78- "\n",
72+ "Note that during evaluation of `H()` the intermediate `b` values are stored in the Python call stack. This is what is meant by \"call stack in the form of a cons list\"."
73+ ]
74+ },
75+ {
76+ "cell_type": "markdown",
77+ "metadata": {},
78+ "source": [
7979 "## Hylomorphism in Joy\n",
8080 "\n",
8181 " a H\n",
8282 " ---------\n",
8383 " c\n",
8484 "\n",
85- "We can define a combinator `hylomorphism` that will make a hylomorphism combinator `H` from constituent parts.\n",
85+ "We can define a combinator `hylomorphism` that will make a hylomorphism combinator `H` from constituent parts. (The reason for the order of the parameters will become clear below):\n",
8686 "\n",
8787 " H == [P] c [G] [Q] hylomorphism\n",
8888 "\n",
89- "The function `H` is recursive, so we start with `ifte` and set the else-part to\n",
90- "some function `J` that will contain a quoted copy of `H`.\n",
89+ "The function `H` is recursive, so we start with `ifte` and set the else-part to some function `J` that will contain a quoted copy of `H`.\n",
9190 "The then-part just discards the leftover `a` and replaces it with the base case value `c`:\n",
9291 "\n",
9392 " H == [P] [pop c] [J] ifte\n",
@@ -96,23 +95,23 @@
9695 "\n",
9796 " a J\n",
9897 "\n",
99- "The first thing to do is use the generator `G` which produces values `b` and a new `aa`:\n",
98+ "The first thing to do is use the generator `G` which produces values `b` and a new `a′`:\n",
10099 "\n",
101100 " a G\n",
102101 " ----------\n",
103- " aa b\n",
102+ " a′ b\n",
104103 "\n",
105104 "So:\n",
106105 "\n",
107106 " J == G J′\n",
108107 "\n",
109- "Then we recur with `H` on `aa`:\n",
108+ "Then we recur with `H` on `a′`:\n",
110109 "\n",
111- " aa b [H] dip\n",
110+ " a′ b [H] dip\n",
112111 " ------------------\n",
113- " aa H b\n",
112+ " a′ H b\n",
114113 " ------------------\n",
115- " cc b\n",
114+ " c′ b\n",
116115 "\n",
117116 "So:\n",
118117 "\n",
@@ -120,7 +119,7 @@
120119 "\n",
121120 "And run `Q` on the result:\n",
122121 "\n",
123- " cc b Q\n",
122+ " c′ b Q\n",
124123 " ------------\n",
125124 " c\n",
126125 "So:\n",
@@ -147,37 +146,390 @@
147146 "it is a simple specialization of the general recursion combinator.\n",
148147 "\n",
149148 " [P] c [G] [Q] hylomorphism\n",
150- " [P] [pop c] [G] [dip Q] genrec\n",
151- "\n",
149+ " [P] [pop c] [G] [dip Q] genrec"
150+ ]
151+ },
152+ {
153+ "cell_type": "markdown",
154+ "metadata": {},
155+ "source": [
152156 "## Derivation of `hylomorphism` combinator\n",
153157 "\n",
154- "Now we just need to derive a definition that builds the `genrec` arguments\n",
155- "out of the pieces given to the `hylomorphism` combinator.\n",
158+ "Now we just need to derive a definition that builds the `genrec` arguments out of the pieces given to the `hylomorphism` combinator.\n",
156159 "\n",
157- " [P] c [G] [F] hylomorphism\n",
160+ " [P] c [G] [Q] hylomorphism\n",
158161 " ------------------------------------------\n",
159- " [P] [pop c] [G] [dip F] genrec\n",
162+ " [P] [pop c] [G] [dip Q] genrec\n",
160163 "\n",
161164 "Working in reverse:\n",
162165 "\n",
163- "- Use `swoncat` twice to decouple `[c]` and `[F]`.\n",
166+ "- Use `swoncat` twice to decouple `[c]` and `[Q]`.\n",
164167 "- Use `unit` to dequote `c`.\n",
165168 "- Use `dipd` to untangle `[unit [pop] swoncat]` from the givens.\n",
166169 "\n",
167- " H == [P] [pop c] [G] [dip F] genrec\n",
168- " [P] [c] [pop] swoncat [G] [F] [dip] swoncat genrec\n",
169- " [P] c unit [pop] swoncat [G] [F] [dip] swoncat genrec\n",
170- " [P] c [G] [F] [unit [pop] swoncat] dipd [dip] swoncat genrec\n",
170+ " H == [P] [pop c] [G] [dip Q] genrec\n",
171+ " [P] [c] [pop] swoncat [G] [Q] [dip] swoncat genrec\n",
172+ " [P] c unit [pop] swoncat [G] [Q] [dip] swoncat genrec\n",
173+ " [P] c [G] [Q] [unit [pop] swoncat] dipd [dip] swoncat genrec\n",
171174 "\n",
172- "At this point all of the arguments (givens) to the hylomorphism are to the left so we have\n",
173- "a definition for `hylomorphism`:\n",
175+ "At this point all of the parameters of the hylomorphism are to the left so we have a definition for `hylomorphism`:\n",
174176 "\n",
175177 " hylomorphism == [unit [pop] swoncat] dipd [dip] swoncat genrec"
176178 ]
177179 },
178180 {
179181 "cell_type": "code",
180- "execution_count": 1,
182+ "execution_count": 1,
183+ "metadata": {},
184+ "outputs": [
185+ {
186+ "name": "stdout",
187+ "output_type": "stream",
188+ "text": []
189+ }
190+ ],
191+ "source": [
192+ "[hylomorphism [unit [pop] swoncat] dipd [dip] swoncat genrec] inscribe"
193+ ]
194+ },
195+ {
196+ "cell_type": "markdown",
197+ "metadata": {},
198+ "source": [
199+ "### Example: Finding [Triangular Numbers](https://en.wikipedia.org/wiki/Triangular_number)\n",
200+ "Let's write a function that, given a positive integer, returns the sum of all positive integers less than that one. (In this case the types `𝔸`, `𝔹` and `ℂ` are all `int`.)\n",
201+ "\n",
202+ "To sum a range of integers from 0 to *n* - 1:\n",
203+ "\n",
204+ "- `[P]` is `[1 <=]`\n",
205+ "- `c` is `0`\n",
206+ "- `[G]` is `[-- dup]`\n",
207+ "- `[Q]` is `[+]`"
208+ ]
209+ },
210+ {
211+ "cell_type": "code",
212+ "execution_count": 2,
213+ "metadata": {},
214+ "outputs": [
215+ {
216+ "name": "stdout",
217+ "output_type": "stream",
218+ "text": []
219+ }
220+ ],
221+ "source": [
222+ "[triangular_number [1 <=] 0 [-- dup] [+] hylomorphism] inscribe"
223+ ]
224+ },
225+ {
226+ "cell_type": "markdown",
227+ "metadata": {},
228+ "source": [
229+ "Let's try it:"
230+ ]
231+ },
232+ {
233+ "cell_type": "code",
234+ "execution_count": 3,
235+ "metadata": {},
236+ "outputs": [
237+ {
238+ "name": "stdout",
239+ "output_type": "stream",
240+ "text": [
241+ "10"
242+ ]
243+ }
244+ ],
245+ "source": [
246+ "5 triangular_number"
247+ ]
248+ },
249+ {
250+ "cell_type": "code",
251+ "execution_count": 4,
252+ "metadata": {},
253+ "outputs": [
254+ {
255+ "name": "stdout",
256+ "output_type": "stream",
257+ "text": [
258+ "[0 0 1 3 6 10 15 21]"
259+ ]
260+ }
261+ ],
262+ "source": [
263+ "clear\n",
264+ "\n",
265+ "[0 1 2 3 4 5 6 7] [triangular_number] map"
266+ ]
267+ },
268+ {
269+ "cell_type": "markdown",
270+ "metadata": {},
271+ "source": [
272+ "Neat!"
273+ ]
274+ },
275+ {
276+ "cell_type": "markdown",
277+ "metadata": {},
278+ "source": [
279+ "In the Wikipedia entry for [hylomorphism](https://en.wikipedia.org/wiki/Hylomorphism_%28computer_science%29) it says:\n",
280+ "\n",
281+ "> a hylomorphism is a recursive function, corresponding to the composition of an [anamorphism](https://en.wikipedia.org/wiki/Anamorphism) (which first builds a set of results; also known as 'unfolding') followed by a [catamorphism](https://en.wikipedia.org/wiki/Catamorphism) (which then folds these results into a final return value).\n",
282+ "\n",
283+ "\n",
284+ "\n"
285+ ]
286+ },
287+ {
288+ "cell_type": "markdown",
289+ "metadata": {},
290+ "source": [
291+ "## Anamorphism\n",
292+ "An anamorphism can be defined as a hylomorphism that uses `[]` for `c` and\n",
293+ "`swons` for `Q`. An anamorphic function builds a list of values.\n",
294+ "\n",
295+ " A == [P] [] [G] [swons] hylomorphism\n",
296+ "\n",
297+ "An example of an anamorphism is the `range` function which generates the list of integers from $0$ to $n - 1$ given $n$.\n",
298+ "\n",
299+ " range == [0 <=] [] [-- dup] [swons] hylomorphism"
300+ ]
301+ },
302+ {
303+ "cell_type": "code",
304+ "execution_count": 16,
305+ "metadata": {},
306+ "outputs": [
307+ {
308+ "name": "stdout",
309+ "output_type": "stream",
310+ "text": []
311+ }
312+ ],
313+ "source": [
314+ "clear "
315+ ]
316+ },
317+ {
318+ "cell_type": "code",
319+ "execution_count": 6,
320+ "metadata": {},
321+ "outputs": [
322+ {
323+ "name": "stdout",
324+ "output_type": "stream",
325+ "text": []
326+ }
327+ ],
328+ "source": [
329+ "[range [0 <=] [] [-- dup] [swons] hylomorphism] inscribe"
330+ ]
331+ },
332+ {
333+ "cell_type": "code",
334+ "execution_count": 7,
335+ "metadata": {
336+ "scrolled": false
337+ },
338+ "outputs": [
339+ {
340+ "name": "stdout",
341+ "output_type": "stream",
342+ "text": [
343+ "[4 3 2 1 0]"
344+ ]
345+ }
346+ ],
347+ "source": [
348+ "5 range"
349+ ]
350+ },
351+ {
352+ "cell_type": "markdown",
353+ "metadata": {},
354+ "source": [
355+ "## Catamorphism\n",
356+ "A catamorphic function tears down a list term-by-term and makes some new value.\n",
357+ "It can be defined as a hylomorphism that uses `[uncons swap]` for `[G]`\n",
358+ "and `[[] =]` (or just `[not]`) for the predicate `[P]`.\n",
359+ "\n",
360+ " C == [not] c [uncons swap] [Q] hylomorphism\n",
361+ "\n",
362+ "An example of a catamorphism is the sum function.\n",
363+ "\n",
364+ " sum == [not] 0 [uncons swap] [+] hylomorphism"
365+ ]
366+ },
367+ {
368+ "cell_type": "code",
369+ "execution_count": 8,
370+ "metadata": {},
371+ "outputs": [
372+ {
373+ "name": "stdout",
374+ "output_type": "stream",
375+ "text": []
376+ }
377+ ],
378+ "source": [
379+ "clear "
380+ ]
381+ },
382+ {
383+ "cell_type": "code",
384+ "execution_count": 9,
385+ "metadata": {},
386+ "outputs": [
387+ {
388+ "name": "stdout",
389+ "output_type": "stream",
390+ "text": []
391+ }
392+ ],
393+ "source": [
394+ "[sum [not] 0 [uncons swap] [+] hylomorphism] inscribe"
395+ ]
396+ },
397+ {
398+ "cell_type": "code",
399+ "execution_count": 10,
400+ "metadata": {},
401+ "outputs": [
402+ {
403+ "name": "stdout",
404+ "output_type": "stream",
405+ "text": [
406+ "15"
407+ ]
408+ }
409+ ],
410+ "source": [
411+ "[5 4 3 2 1] sum"
412+ ]
413+ },
414+ {
415+ "cell_type": "code",
416+ "execution_count": 11,
417+ "metadata": {},
418+ "outputs": [
419+ {
420+ "name": "stdout",
421+ "output_type": "stream",
422+ "text": []
423+ }
424+ ],
425+ "source": [
426+ "clear "
427+ ]
428+ },
429+ {
430+ "cell_type": "markdown",
431+ "metadata": {},
432+ "source": [
433+ "The [\"Bananas, Lenses, & Barbed Wire\"](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.125) paper mentions the\n",
434+ "\n",
435+ "### \"Fusion Law\" for catamorphisms\n",
436+ "\n",
437+ " f . (| b, (+) |) = (| c, (x) |) <== f b = c /\\ f( a (+) as ) = a (x) (f as)\n",
438+ "\n"
439+ ]
440+ },
441+ {
442+ "cell_type": "markdown",
443+ "metadata": {},
444+ "source": [
445+ "The [\"Bananas, Lenses, & Barbed Wire\"](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.125) paper mentions the\n",
446+ "\n",
447+ "### \"Fusion Law\" for catamorphisms\n",
448+ "\n",
449+ " f ∘ ⦇b,⨁⦈ = ⦇c,⨂⦈ ⇐ f b = c ∧ f(a ⨁ as) = a ⨂ (f as)\n",
450+ "\n"
451+ ]
452+ },
453+ {
454+ "cell_type": "markdown",
455+ "metadata": {},
456+ "source": [
457+ " b [⨁] catamorphism f == c [⨂] catamorphism\n",
458+ " \n",
459+ " f == 10 *\n",
460+ " \n",
461+ " 0 [+] catamorphism f\n",
462+ " \n",
463+ " 0 f == 0\n",
464+ " \n",
465+ " as a + f == as f a ⨂\n",
466+ " \n",
467+ " ⨂ = f +\n",
468+ " \n",
469+ " 0 [+] catamorphism f = 0 [f +] catamorphism\n",
470+ " "
471+ ]
472+ },
473+ {
474+ "cell_type": "markdown",
475+ "metadata": {},
476+ "source": [
477+ "⨁ ⨂ ∘ ∧ ⦇ ⦈ ⇐"
478+ ]
479+ },
480+ {
481+ "cell_type": "markdown",
482+ "metadata": {},
483+ "source": [
484+ "### The `step` combinator\n",
485+ "The `step` combinator will often be easier to use than `catamorphism`."
486+ ]
487+ },
488+ {
489+ "cell_type": "code",
490+ "execution_count": 21,
491+ "metadata": {},
492+ "outputs": [
493+ {
494+ "name": "stdout",
495+ "output_type": "stream",
496+ "text": [
497+ "\n",
498+ "==== Help on step ====\n",
499+ "\n",
500+ "Run a quoted program on each item in a sequence.\n",
501+ "::\n",
502+ "\n",
503+ " ... [] [Q] . step\n",
504+ " -----------------------\n",
505+ " ... .\n",
506+ "\n",
507+ "\n",
508+ " ... [a] [Q] . step\n",
509+ " ------------------------\n",
510+ " ... a . Q\n",
511+ "\n",
512+ "\n",
513+ " ... [a b c] [Q] . step\n",
514+ " ----------------------------------------\n",
515+ " ... a . Q [b c] [Q] step\n",
516+ "\n",
517+ "The step combinator executes the quotation on each member of the list\n",
518+ "on top of the stack.\n",
519+ "\n",
520+ "---- end (step)\n",
521+ "\n",
522+ "\n"
523+ ]
524+ }
525+ ],
526+ "source": [
527+ "[step] help"
528+ ]
529+ },
530+ {
531+ "cell_type": "code",
532+ "execution_count": 22,
181533 "metadata": {},
182534 "outputs": [
183535 {
@@ -187,66 +539,53 @@
187539 }
188540 ],
189541 "source": [
190- "[hylomorphism [unit [pop] swoncat] dipd [dip] swoncat genrec] inscribe"
191- ]
192- },
193- {
194- "cell_type": "markdown",
195- "metadata": {},
196- "source": [
197- "### Example: Finding [Triangular Numbers](https://en.wikipedia.org/wiki/Triangular_number)\n",
198- "Let's write a function that, given a positive integer, returns the sum of all positive integers less than that one. (In this case the types `A`, `B` and `C` are all `int`.)\n",
199- "\n",
200- "To sum a range of integers from 0 to *n* - 1:\n",
201- "\n",
202- "- `[P]` is `[1 <=]`\n",
203- "- `c` is `0`\n",
204- "- `[G]` is `[-- dup]`\n",
205- "- `[F]` is `[+]`"
542+ "[sum 0 swap [+] step] inscribe"
206543 ]
207544 },
208545 {
209546 "cell_type": "code",
210- "execution_count": 2,
547+ "execution_count": 23,
211548 "metadata": {},
212549 "outputs": [
213550 {
214551 "name": "stdout",
215552 "output_type": "stream",
216- "text": []
553+ "text": [
554+ "15"
555+ ]
217556 }
218557 ],
219558 "source": [
220- "[triangular_number [1 <=] 0 [-- dup] [+] hylomorphism] inscribe"
559+ "[5 4 3 2 1] sum"
221560 ]
222561 },
223562 {
224563 "cell_type": "markdown",
225564 "metadata": {},
226565 "source": [
227- "Let's try it:"
566+ "## Hylo- is Ana- then Cata-\n",
567+ "\n",
568+ " anamorphism == [] swap [swons] hylomorphism\n",
569+ " \n",
570+ " catamorphism == [[not] swap [uncons swap]] dip hylomorphism\n",
571+ "\n",
572+ "A hylomorphism can be thought of as the composition of an anamorphism and a catamorphism:\n",
573+ "\n",
574+ " [P] [G] anamorphism c [Q] catamorphism == [P] c [G] [Q] hylomorphism\n"
228575 ]
229576 },
230577 {
231- "cell_type": "code",
232- "execution_count": 3,
578+ "cell_type": "markdown",
233579 "metadata": {},
234- "outputs": [
235- {
236- "name": "stdout",
237- "output_type": "stream",
238- "text": [
239- "10"
240- ]
241- }
242- ],
243580 "source": [
244- "5 triangular_number"
581+ "For example, `triangular_number` could be defined as the composition of the `range` and `sum` functions:\n",
582+ "\n",
583+ " triangular_number == range sum"
245584 ]
246585 },
247586 {
248587 "cell_type": "code",
249- "execution_count": 4,
588+ "execution_count": 15,
250589 "metadata": {},
251590 "outputs": [
252591 {
@@ -260,14 +599,14 @@
260599 "source": [
261600 "clear\n",
262601 "\n",
263- "[0 1 2 3 4 5 6 7] [triangular_number] map"
602+ "[0 1 2 3 4 5 6 7] [range sum] map"
264603 ]
265604 },
266605 {
267606 "cell_type": "markdown",
268607 "metadata": {},
269608 "source": [
270- "Neat!"
609+ "However, this creates (and destroys) an intermediate list, which is a waste."
271610 ]
272611 },
273612 {
@@ -275,22 +614,22 @@
275614 "metadata": {},
276615 "source": [
277616 "## Four Specializations\n",
278- "There are at least four kinds of recursive combinator, depending on two choices. The first choice is whether the combiner function `F` should be evaluated during the recursion or pushed into the pending expression to be \"collapsed\" at the end. The second choice is whether the combiner needs to operate on the current value of the datastructure or the generator's output, in other words, whether `F` or `G` should run first in the recursive branch.\n",
617+ "There are (at least) four kinds of recursive combinator, depending on two choices. The first choice is whether the combiner function `Q` should be evaluated during the recursion or pushed into the pending expression to be \"collapsed\" at the end. The second choice is whether the combiner needs to operate on the current value of the datastructure or the generator's output, in other words, whether `Q` or `G` should run first in the recursive branch.\n",
279618 "\n",
280- " H1 == [P] [pop c] [G ] [dip F] genrec\n",
281- " H2 == c swap [P] [pop] [G [F] dip ] [i] genrec\n",
282- " H3 == [P] [pop c] [ [G] dupdip ] [dip F] genrec\n",
283- " H4 == c swap [P] [pop] [ [F] dupdip G] [i] genrec\n",
619+ " H1 == [P] [pop c] [G ] [dip Q] genrec\n",
620+ " H2 == c swap [P] [pop] [G [Q] dip ] [i] genrec\n",
621+ " H3 == [P] [pop c] [ [G] dupdip ] [dip Q] genrec\n",
622+ " H4 == c swap [P] [pop] [ [Q] dupdip G] [i] genrec\n",
284623 "\n",
285624 "The working of the generator function `G` differs slightly for each. Consider the recursive branches:\n",
286625 "\n",
287- " ... a G [H1] dip F w/ a G == a′ b\n",
626+ " ... a G [H1] dip Q w/ a G == a′ b\n",
288627 " \n",
289- " ... c a G [F] dip H2 a G == b a′\n",
628+ " ... c a G [Q] dip H2 a G == b a′\n",
290629 " \n",
291- " ... a [G] dupdip [H3] dip F a G == a′\n",
630+ " ... a [G] dupdip [H3] dip Q a G == a′\n",
292631 " \n",
293- " ... c a [F] dupdip G H4 a G == a′\n",
632+ " ... c a [Q] dupdip G H4 a G == a′\n",
294633 "\n",
295634 "The following four sections illustrate how these work, omitting the predicate evaluation."
296635 ]
@@ -301,26 +640,27 @@
301640 "source": [
302641 "### `H1`\n",
303642 "\n",
304- " H1 == [P] [pop c] [G] [dip F] genrec\n",
305- "\n",
306- "Iterate n times.\n",
307- "\n",
308- " ... a G [H1] dip F\n",
309- " ... a′ b [H1] dip F\n",
310- " ... a′ H1 b F\n",
311- " ... a′ G [H1] dip F b F\n",
312- " ... a″ b′ [H1] dip F b F\n",
313- " ... a″ H1 b′ F b F\n",
314- " ... a″ G [H1] dip F b′ F b F\n",
315- " ... a‴ b″ [H1] dip F b′ F b F\n",
316- " ... a‴ H1 b″ F b′ F b F\n",
317- " ... a‴ pop c b″ F b′ F b F\n",
318- " ... c b″ F b′ F b F\n",
319- " ... d b′ F b F\n",
320- " ... d′ b F\n",
321- " ... d″\n",
322- "\n",
323- "This form builds up a pending expression (continuation) that contains the intermediate results along with the pending combiner functions. When the base case is reached the last term is replaced by the identity value `c` and the continuation \"collapses\" into the final result using the combiner `F`."
643+ "This form builds up a pending expression (continuation) that contains the intermediate results along with the pending combiner functions. When the base case is reached the last term is replaced by the identity value `c` and the continuation \"collapses\" into the final result using the combiner `Q`.\n",
644+ "\n",
645+ " H1 == [P] [pop c] [G] [dip Q] genrec\n",
646+ "\n",
647+ " ... a G [H1] dip Q\n",
648+ " ... a′ b [H1] dip Q\n",
649+ " ... a′ H1 b Q\n",
650+ " <predicate omitted>\n",
651+ " ... a′ G [H1] dip Q b Q\n",
652+ " ... a″ b′ [H1] dip Q b Q\n",
653+ " ... a″ H1 b′ Q b Q\n",
654+ " <predicate omitted>\n",
655+ " ... a″ G [H1] dip Q b′ Q b Q\n",
656+ " ... a‴ b″ [H1] dip Q b′ Q b Q\n",
657+ " ... a‴ H1 b″ Q b′ Q b Q\n",
658+ " <predicate omitted>\n",
659+ " ... a‴ pop c b″ Q b′ Q b Q\n",
660+ " ... c b″ Q b′ Q b Q\n",
661+ " ... c′ b′ Q b Q\n",
662+ " ... c″ b Q\n",
663+ " ... c‴"
324664 ]
325665 },
326666 {
@@ -328,24 +668,30 @@
328668 "metadata": {},
329669 "source": [
330670 "### `H2`\n",
331- "When you can start with the identity value `c` on the stack and the combiner `F` can operate as you go using the intermediate results immediately rather than queuing them up, use this form. An important difference is that the generator function must return its results in the reverse order.\n",
332671 "\n",
333- " H2 == c swap [P] [pop] [G [F] dip] primrec\n",
672+ "When you can start with the identity value `c` on the stack and the combiner `Q` can operate as you go using the intermediate results immediately rather than queuing them up, use this form.\n",
673+ "An important difference is that the generator function must return its results in the reverse order,\n",
674+ "and both `Q` and `G` have to take into account the presence of the `c` value:\n",
334675 "\n",
335- " ... c a G [F] dip H2\n",
336- " ... c b a′ [F] dip H2\n",
337- " ... c b F a′ H2\n",
338- " ... d a′ H2\n",
339- " ... d a′ G [F] dip H2\n",
340- " ... d b′ a″ [F] dip H2\n",
341- " ... d b′ F a″ H2\n",
342- " ... d′ a″ H2\n",
343- " ... d′ a″ G [F] dip H2\n",
344- " ... d′ b″ a‴ [F] dip H2\n",
345- " ... d′ b″ F a‴ H2\n",
346- " ... d″ a‴ H2\n",
347- " ... d″ a‴ pop\n",
348- " ... d″\n"
676+ " H2 == c swap [P] [pop] [G [Q] dip] tailrec\n",
677+ "\n",
678+ " ... c a G [Q] dip H2\n",
679+ " ... c b a′ [Q] dip H2\n",
680+ " ... c b Q a′ H2\n",
681+ " ... c′ a′ H2\n",
682+ " <predicate omitted>\n",
683+ " ... c′ a′ G [Q] dip H2\n",
684+ " ... c′ b′ a″ [Q] dip H2\n",
685+ " ... c′ b′ Q a″ H2\n",
686+ " ... c″ a″ H2\n",
687+ " <predicate omitted>\n",
688+ " ... c″ a″ G [Q] dip H2\n",
689+ " ... c″ b″ a‴ [Q] dip H2\n",
690+ " ... c″ b″ Q a‴ H2\n",
691+ " ... c‴ a‴ H2\n",
692+ " <predicate omitted>\n",
693+ " ... c‴ a‴ pop\n",
694+ " ... c‴\n"
349695 ]
350696 },
351697 {
@@ -353,28 +699,32 @@
353699 "metadata": {},
354700 "source": [
355701 "### `H3`\n",
356- "If you examine the traces above you'll see that the combiner `F` only gets to operate on the results of `G`, it never \"sees\" the first value `a`. If the combiner and the generator both need to work on the current value then `dup` must be used, and the generator must produce one item instead of two (the b is instead the duplicate of a.)\n",
357- "\n",
358- "\n",
359- " H3 == [P] [pop c] [[G] dupdip] [dip F] genrec\n",
360702 "\n",
361- " ... a [G] dupdip [H3] dip F\n",
362- " ... a G a [H3] dip F\n",
363- " ... a′ a [H3] dip F\n",
364- " ... a′ H3 a F\n",
365- " ... a′ [G] dupdip [H3] dip F a F\n",
366- " ... a′ G a′ [H3] dip F a F\n",
367- " ... a″ a′ [H3] dip F a F\n",
368- " ... a″ H3 a′ F a F\n",
369- " ... a″ [G] dupdip [H3] dip F a′ F a F\n",
370- " ... a″ G a″ [H3] dip F a′ F a F\n",
371- " ... a‴ a″ [H3] dip F a′ F a F\n",
372- " ... a‴ H3 a″ F a′ F a F\n",
373- " ... a‴ pop c a″ F a′ F a F\n",
374- " ... c a″ F a′ F a F\n",
375- " ... d a′ F a F\n",
376- " ... d′ a F\n",
377- " ... d″"
703+ "If you examine the traces above you'll see that the combiner `Q` only gets to operate on the results of `G`, it never \"sees\" the first value `a`. If the combiner and the generator both need to work on the current value then `dup` must be used, and the generator must produce one item instead of two (the b is instead the duplicate of a.)\n",
704+ "\n",
705+ "\n",
706+ " H3 == [P] [pop c] [[G] dupdip] [dip Q] genrec\n",
707+ "\n",
708+ " ... a [G] dupdip [H3] dip Q\n",
709+ " ... a G a [H3] dip Q\n",
710+ " ... a′ a [H3] dip Q\n",
711+ " ... a′ H3 a Q\n",
712+ " <predicate omitted>\n",
713+ " ... a′ [G] dupdip [H3] dip Q a Q\n",
714+ " ... a′ G a′ [H3] dip Q a Q\n",
715+ " ... a″ a′ [H3] dip Q a Q\n",
716+ " ... a″ H3 a′ Q a Q\n",
717+ " <predicate omitted>\n",
718+ " ... a″ [G] dupdip [H3] dip Q a′ Q a Q\n",
719+ " ... a″ G a″ [H3] dip Q a′ Q a Q\n",
720+ " ... a‴ a″ [H3] dip Q a′ Q a Q\n",
721+ " ... a‴ H3 a″ Q a′ Q a Q\n",
722+ " <predicate omitted>\n",
723+ " ... a‴ pop c a″ Q a′ Q a Q\n",
724+ " ... c a″ Q a′ Q a Q\n",
725+ " ... c′ a′ Q a Q\n",
726+ " ... c‴ a Q\n",
727+ " ... c‴"
378728 ]
379729 },
380730 {
@@ -382,35 +732,28 @@
382732 "metadata": {},
383733 "source": [
384734 "### `H4`\n",
385- "And, last but not least, if you can combine as you go, starting with `c`, and the combiner `F` needs to work on the current item, this is the form:\n",
386- "\n",
387- " H4 == c swap [P] [pop] [[F] dupdip G] primrec\n",
388- "\n",
389- " ... c a [F] dupdip G H4\n",
390- " ... c a F a G H4\n",
391- " ... d a G H4\n",
392- " ... d a′ H4\n",
393- " ... d a′ [F] dupdip G H4\n",
394- " ... d a′ F a′ G H4\n",
395- " ... d′ a′ G H4\n",
396- " ... d′ a″ H4\n",
397- " ... d′ a″ [F] dupdip G H4\n",
398- " ... d′ a″ F a″ G H4\n",
399- " ... d″ a″ G H4\n",
400- " ... d″ a‴ H4\n",
401- " ... d″ a‴ pop\n",
402- " ... d″"
403- ]
404- },
405- {
406- "cell_type": "markdown",
407- "metadata": {},
408- "source": [
409- "## Anamorphism\n",
410- "An anamorphism can be defined as a hylomorphism that uses `[]` for `c` and\n",
411- "`swons` for `F`. An anamorphic function builds a list of values.\n",
412735 "\n",
413- " A == [P] [] [G] [swons] hylomorphism"
736+ "And, last but not least, if you can combine as you go, starting with `c`, and the combiner `Q` needs to work on the current item, this is the form:\n",
737+ "\n",
738+ " H4 == c swap [P] [pop] [[Q] dupdip G] primrec\n",
739+ "\n",
740+ " ... c a [Q] dupdip G H4\n",
741+ " ... c a Q a G H4\n",
742+ " ... c′ a G H4\n",
743+ " ... c′ a′ H4\n",
744+ " <predicate omitted>\n",
745+ " ... c′ a′ [Q] dupdip G H4\n",
746+ " ... c′ a′ Q a′ G H4\n",
747+ " ... c‴ a′ G H4\n",
748+ " ... c‴ a″ H4\n",
749+ " <predicate omitted>\n",
750+ " ... c‴ a″ [Q] dupdip G H4\n",
751+ " ... c‴ a″ Q a″ G H4\n",
752+ " ... c‴ a″ G H4\n",
753+ " ... c‴ a‴ H4\n",
754+ " <predicate omitted>\n",
755+ " ... c‴ a‴ pop\n",
756+ " ... c‴"
414757 ]
415758 },
416759 {
@@ -429,7 +772,7 @@
429772 "metadata": {},
430773 "source": [
431774 "#### `range` with `H1`\n",
432- " H1 == [P] [pop c] [G] [dip F] genrec\n",
775+ " H1 == [P] [pop c] [G] [dip Q] genrec\n",
433776 " == [0 <=] [pop []] [-- dup] [dip swons] genrec"
434777 ]
435778 },
@@ -487,7 +830,7 @@
487830 "metadata": {},
488831 "source": [
489832 "#### `range` with `H2`\n",
490- " H2 == c swap [P] [pop] [G [F] dip] tailrec\n",
833+ " H2 == c swap [P] [pop] [G [Q] dip] tailrec\n",
491834 " == [] swap [0 <=] [pop] [-- dup [swons] dip] tailrec"
492835 ]
493836 },
@@ -545,7 +888,7 @@
545888 "metadata": {},
546889 "source": [
547890 "#### `range` with `H3`\n",
548- " H3 == [P] [pop c] [[G] dupdip] [dip F] genrec\n",
891+ " H3 == [P] [pop c] [[G] dupdip] [dip Q] genrec\n",
549892 " == [0 <=] [pop []] [[--] dupdip] [dip swons] genrec"
550893 ]
551894 },
@@ -603,7 +946,7 @@
603946 "metadata": {},
604947 "source": [
605948 "#### `range` with `H4`\n",
606- " H4 == c swap [P] [pop] [[F] dupdip G ] primrec\n",
949+ " H4 == c swap [P] [pop] [[Q] dupdip G ] primrec\n",
607950 " == [] swap [0 <=] [pop] [[swons] dupdip --] primrec"
608951 ]
609952 },
@@ -660,21 +1003,23 @@
6601003 "cell_type": "markdown",
6611004 "metadata": {},
6621005 "source": [
663- "## Catamorphism\n",
664- "A catamorphic function tears down a list term-by-term and makes some new value.\n",
665- "It can be defined as a hylomorphism that uses `[uncons swap]` for `[G]`\n",
666- "and `[[] =]` (or just `[not]`) for the predicate `[P]`.\n",
1006+ "## Example: Factorial Function\n",
1007+ "\n",
1008+ "For the Factorial function:\n",
6671009 "\n",
668- " C == [not] c [uncons swap] [F] hylomorphism\n",
1010+ " H4 == c swap [P] [pop] [[Q] dupdip G] tailrec\n",
6691011 "\n",
670- "An example of a catamorphism is the sum function.\n",
1012+ "With:\n",
6711013 "\n",
672- " sum == [not] 0 [uncons swap] [+] hylomorphism"
1014+ " c == 1\n",
1015+ " Q == *\n",
1016+ " G == --\n",
1017+ " P == 1 <="
6731018 ]
6741019 },
6751020 {
6761021 "cell_type": "code",
677- "execution_count": 17,
1022+ "execution_count": 24,
6781023 "metadata": {},
6791024 "outputs": [
6801025 {
@@ -684,12 +1029,12 @@
6841029 }
6851030 ],
6861031 "source": [
687- "clear "
1032+ "clear"
6881033 ]
6891034 },
6901035 {
6911036 "cell_type": "code",
692- "execution_count": 18,
1037+ "execution_count": 25,
6931038 "metadata": {},
6941039 "outputs": [
6951040 {
@@ -699,29 +1044,80 @@
6991044 }
7001045 ],
7011046 "source": [
702- "[sum [not] 0 [uncons swap] [+] hylomorphism] inscribe"
1047+ "[factorial 1 swap [1 <=] [pop] [[*] dupdip --] tailrec] inscribe"
7031048 ]
7041049 },
7051050 {
7061051 "cell_type": "code",
707- "execution_count": 19,
708- "metadata": {},
1052+ "execution_count": 26,
1053+ "metadata": {
1054+ "scrolled": false
1055+ },
7091056 "outputs": [
7101057 {
7111058 "name": "stdout",
7121059 "output_type": "stream",
7131060 "text": [
714- "15"
1061+ "120"
7151062 ]
7161063 }
7171064 ],
7181065 "source": [
719- "[5 4 3 2 1] sum"
1066+ "5 factorial"
1067+ ]
1068+ },
1069+ {
1070+ "cell_type": "markdown",
1071+ "metadata": {},
1072+ "source": [
1073+ "## Example: Filter Function\n",
1074+ "\n",
1075+ "An often-used function is `filter` which takes a list and a predicate and makes a new list with only those items from the input list that make the predicate true:\n",
1076+ "\n",
1077+ " [...] [P] filter\n",
1078+ " ----------------------\n",
1079+ " [...]′\n",
1080+ "\n",
1081+ "Let's start by making a simpler function that just recreates the input list:\n",
1082+ "\n",
1083+ " F == [not] [] [J] ifte\n",
1084+ "\n",
1085+ "To figure out the recursive branch `J` we start by setting a dummy list in front of it.\n",
1086+ "\n",
1087+ " [a b c] J\n",
1088+ " [a b c] uncons swap J′\n",
1089+ " a [b c] swap J′\n",
1090+ " [b c] a J′\n",
1091+ "\n",
1092+ " J == uncons swap J′\n",
1093+ "\n",
1094+ "We don't have the output list to which to `cons` that `a` so we recur instead and *then* `cons` (more precisely `swons`) it:\n",
1095+ "\n",
1096+ " J′ == [Q] dip swons\n",
1097+ "\n",
1098+ " [b c] a [Q] dip swons\n",
1099+ " [b c] Q a swons\n",
1100+ " ...\n",
1101+ " [c] Q b swons a swons\n",
1102+ " ...\n",
1103+ " [] c swons b swons a swons\n",
1104+ " ...\n",
1105+ " [a b c]\n",
1106+ "\n",
1107+ "So:\n",
1108+ "\n",
1109+ " J == uncons swap [Q] dip swons\n",
1110+ "\n",
1111+ "And:\n",
1112+ "\n",
1113+ " F == [not] [] [uncons swap [F] dip swons] ifte\n",
1114+ " [not] [] [uncons swap] [dip swons] genrec\n",
1115+ "\n"
7201116 ]
7211117 },
7221118 {
7231119 "cell_type": "code",
724- "execution_count": 20,
1120+ "execution_count": 27,
7251121 "metadata": {},
7261122 "outputs": [
7271123 {
@@ -731,62 +1127,94 @@
7311127 }
7321128 ],
7331129 "source": [
734- "clear "
735- ]
736- },
737- {
738- "cell_type": "markdown",
739- "metadata": {},
740- "source": [
741- "### The `step` combinator\n",
742- "The `step` combinator will usually be better to use than `catamorphism`."
1130+ "clear"
7431131 ]
7441132 },
7451133 {
7461134 "cell_type": "code",
747- "execution_count": 21,
1135+ "execution_count": 28,
7481136 "metadata": {},
7491137 "outputs": [
7501138 {
7511139 "name": "stdout",
7521140 "output_type": "stream",
7531141 "text": [
754- "\n",
755- "==== Help on step ====\n",
756- "\n",
757- "Run a quoted program on each item in a sequence.\n",
758- "::\n",
759- "\n",
760- " ... [] [Q] . step\n",
761- " -----------------------\n",
762- " ... .\n",
763- "\n",
764- "\n",
765- " ... [a] [Q] . step\n",
766- " ------------------------\n",
767- " ... a . Q\n",
768- "\n",
769- "\n",
770- " ... [a b c] [Q] . step\n",
771- " ----------------------------------------\n",
772- " ... a . Q [b c] [Q] step\n",
773- "\n",
774- "The step combinator executes the quotation on each member of the list\n",
775- "on top of the stack.\n",
776- "\n",
777- "---- end (step)\n",
778- "\n",
779- "\n"
1142+ "[1 2 3]"
7801143 ]
7811144 }
7821145 ],
7831146 "source": [
784- "[step] help"
1147+ "[1 2 3] [not] [] [uncons swap] [dip swons] genrec"
1148+ ]
1149+ },
1150+ {
1151+ "cell_type": "markdown",
1152+ "metadata": {
1153+ "scrolled": false
1154+ },
1155+ "source": [
1156+ "It would seem that all we need to do now is turn the `swons` into an expression that applies the input `P` predicate to the items and only puts them on the output list if they pass.\n",
1157+ "\n",
1158+ " filter == [not] [] [uncons swap] [dip W] genrec\n",
1159+ "\n",
1160+ "Resulting in, e.g.:\n",
1161+ "\n",
1162+ " [] c W b W a W\n",
1163+ "\n",
1164+ "However, the input list will be on the stack just below the item, so `W` has to take account of that. If our predicate function doesn't use any values from below the item under consideration then we're okay, but if it does then we have to deal with the input list somehow.\n",
1165+ "\n",
1166+ "We know `W` would be something like:\n",
1167+ "\n",
1168+ " W == [...[P]...] [swons] [pop] ifte\n",
1169+ "\n",
1170+ "Let's examine the situation:\n",
1171+ "\n",
1172+ " ... [...] item [...[P]...] [swons] [pop] ifte\n",
1173+ "\n",
1174+ "Since the predicate of the `ifte` combinator is applied `nullary` we can just `pop` the output list:\n",
1175+ "\n",
1176+ " ... [...] item popd P\n",
1177+ "\n",
1178+ "And since `[P]` is already a quote:\n",
1179+ "\n",
1180+ " W == [popd P] [swons] [pop] ifte\n",
1181+ "\n",
1182+ "Ergo:\n",
1183+ "\n",
1184+ " [P] filter == [not] [] [uncons swap] [dip [popd P] [swons] [pop] ifte] genrec\n",
1185+ "\n",
1186+ "Getting that `P` into position is straightforward. Working in reverse:\n",
1187+ "\n",
1188+ " [not] [] [uncons swap] [dip [popd P] [swons] [pop] ifte] genrec\n",
1189+ "\n",
1190+ "Undip the first three terms:\n",
1191+ "\n",
1192+ " [dip [popd P] [swons] [pop] ifte] [[not] [] [uncons swap]] dip genrec\n",
1193+ " ^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n",
1194+ "\n",
1195+ "Take off the `[dip]` prefix:\n",
1196+ "\n",
1197+ " [[popd P] [swons] [pop] ifte] [dip] swoncat [[not] [] [uncons swap]] dip genrec\n",
1198+ " ^^^^^^^^^^^^^\n",
1199+ "\n",
1200+ "Uncons the term containing `P`:\n",
1201+ "\n",
1202+ " [popd P] [[swons] [pop] ifte] cons [dip] swoncat [[not] [] [uncons swap]] dip genrec\n",
1203+ " ^^^^^^^^ ^^^^\n",
1204+ "\n",
1205+ "And then take off the `[popd]` prefix:\n",
1206+ "\n",
1207+ " [P] [popd] swoncat [[swons] [pop] ifte] cons [dip] swoncat [[not] [] [uncons swap]] dip genrec\n",
1208+ " ^^^^^^^^^^^^^^\n",
1209+ "\n",
1210+ "And so:\n",
1211+ "\n",
1212+ " filter == [popd] swoncat [[swons] [pop] ifte] cons [dip] swoncat [[not] [] [uncons swap]] dip genrec\n"
7851213 ]
7861214 },
7871215 {
7881216 "cell_type": "code",
789- "execution_count": 22,
1217+ "execution_count": 29,
7901218 "metadata": {},
7911219 "outputs": [
7921220 {
@@ -796,91 +1224,65 @@
7961224 }
7971225 ],
7981226 "source": [
799- "[sum 0 swap [+] step] inscribe"
1227+ "clear"
8001228 ]
8011229 },
8021230 {
8031231 "cell_type": "code",
804- "execution_count": 23,
1232+ "execution_count": 30,
8051233 "metadata": {},
8061234 "outputs": [
8071235 {
8081236 "name": "stdout",
8091237 "output_type": "stream",
810- "text": [
811- "15"
812- ]
1238+ "text": []
8131239 }
8141240 ],
8151241 "source": [
816- "[5 4 3 2 1] sum"
817- ]
818- },
819- {
820- "cell_type": "markdown",
821- "metadata": {},
822- "source": [
823- "## Example: Factorial Function\n",
824- "\n",
825- "For the Factorial function:\n",
826- "\n",
827- " H4 == c swap [P] [pop] [[F] dupdip G] primrec\n",
828- "\n",
829- "With:\n",
830- "\n",
831- " c == 1\n",
832- " F == *\n",
833- " G == --\n",
834- " P == 1 <="
1242+ "[filter [popd] swoncat [[swons] [pop] ifte] cons [dip] swoncat [[not] [] [uncons swap]] dip genrec] inscribe"
8351243 ]
8361244 },
8371245 {
8381246 "cell_type": "code",
839- "execution_count": 24,
1247+ "execution_count": 31,
8401248 "metadata": {},
8411249 "outputs": [
8421250 {
8431251 "name": "stdout",
8441252 "output_type": "stream",
845- "text": []
1253+ "text": [
1254+ "[1 2 3 4 5 6 7 8] [2 mod not]"
1255+ ]
8461256 }
8471257 ],
8481258 "source": [
849- "clear"
1259+ "[1 2 3 4 5 6 7 8] [2 mod not]"
8501260 ]
8511261 },
8521262 {
8531263 "cell_type": "code",
854- "execution_count": 25,
1264+ "execution_count": 32,
8551265 "metadata": {},
8561266 "outputs": [
8571267 {
8581268 "name": "stdout",
8591269 "output_type": "stream",
860- "text": []
1270+ "text": [
1271+ "[2 4 6 8]"
1272+ ]
8611273 }
8621274 ],
8631275 "source": [
864- "[factorial 1 swap [1 <=] [pop] [[*] dupdip --] tailrec] inscribe"
1276+ "filter"
8651277 ]
8661278 },
8671279 {
868- "cell_type": "code",
869- "execution_count": 26,
1280+ "cell_type": "markdown",
8701281 "metadata": {
8711282 "scrolled": false
8721283 },
873- "outputs": [
874- {
875- "name": "stdout",
876- "output_type": "stream",
877- "text": [
878- "120"
879- ]
880- }
881- ],
8821284 "source": [
883- "5 factorial"
1285+ "This isn't completely satisfying. For one thing, it would be nice to apply the predicate as we go so we are not putting items (and `W`) onto the expression for items that will fail the predicate `P`."
8841286 ]
8851287 },
8861288 {
@@ -909,7 +1311,7 @@
9091311 },
9101312 {
9111313 "cell_type": "code",
912- "execution_count": 27,
1314+ "execution_count": 33,
9131315 "metadata": {},
9141316 "outputs": [
9151317 {
@@ -924,7 +1326,7 @@
9241326 },
9251327 {
9261328 "cell_type": "code",
927- "execution_count": 28,
1329+ "execution_count": 34,
9281330 "metadata": {},
9291331 "outputs": [
9301332 {
@@ -939,7 +1341,7 @@
9391341 },
9401342 {
9411343 "cell_type": "code",
942- "execution_count": 29,
1344+ "execution_count": 35,
9431345 "metadata": {},
9441346 "outputs": [
9451347 {
@@ -964,15 +1366,15 @@
9641366 "\n",
9651367 "### Hylo-, Ana-, Cata-\n",
9661368 "\n",
967- " H == [P ] [pop c ] [G ] [dip F ] genrec\n",
1369+ " H == [P ] [pop c ] [G ] [dip Q ] genrec\n",
9681370 " A == [P ] [pop []] [G ] [dip swap cons] genrec\n",
969- " C == [not] [pop c ] [uncons swap] [dip F ] genrec\n",
1371+ " C == [not] [pop c ] [uncons swap] [dip Q ] genrec\n",
9701372 "\n",
9711373 "### Para-, ?-, ?-\n",
9721374 "\n",
973- " P == c swap [P ] [pop] [[F ] dupdip G ] primrec\n",
1375+ " P == c swap [P ] [pop] [[Q ] dupdip G ] primrec\n",
9741376 " ? == [] swap [P ] [pop] [[swap cons] dupdip G ] primrec\n",
975- " ? == c swap [not] [pop] [[F ] dupdip uncons swap] primrec\n"
1377+ " ? == c swap [not] [pop] [[Q ] dupdip uncons swap] primrec\n"
9761378 ]
9771379 },
9781380 {
@@ -981,7 +1383,7 @@
9811383 "source": [
9821384 "## Appendix: Fun with Symbols\n",
9831385 "\n",
984- " |[ (c, F), (G, P) ]| == (|c, F|) • [(G, P)]\n",
1386+ " |[ (c, Q), (G, P) ]| == (|c, Q|) • [(G, P)]\n",
9851387 "\n",
9861388 "[\"Bananas, Lenses, & Barbed Wire\"](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.125)\n",
9871389 "\n",
--- /dev/null
+++ b/docs/Remove-Function.ipynb
@@ -0,0 +1,484 @@
1+{
2+ "cells": [
3+ {
4+ "cell_type": "markdown",
5+ "id": "0edff064",
6+ "metadata": {},
7+ "source": [
8+ "# `remove`\n",
9+ "\n",
10+ " [1 2 3 4] 5 remove\n",
11+ " ------------------------\n",
12+ " [1 2 3 4]\n",
13+ "\n",
14+ " [1 2 3 4] 2 remove\n",
15+ " ------------------------\n",
16+ " [1 3 4]\n",
17+ "\n",
18+ " [] a remove\n",
19+ " ------------------------\n",
20+ " []\n",
21+ "\n",
22+ "## First attempt\n",
23+ "\n",
24+ "First let's handle the case of an empty list:\n",
25+ "\n",
26+ " remove == [pop not] [pop] [remove'] ifte\n",
27+ "\n",
28+ "For non-empty lists, the predicate and base case are easy:\n",
29+ "\n",
30+ " remove' == [swap first =] [pop rest] [R0] [R1] genrec\n",
31+ "\n",
32+ "The recursive branch:\n",
33+ "\n",
34+ " [1 2 3 4] 3 R0 [remove'] R1\n",
35+ "\n",
36+ "For `R0` use `[uncons] dip`:\n",
37+ "\n",
38+ " [1 2 3 4] 3 [uncons] dip [remove'] R1\n",
39+ " [1 2 3 4] uncons 3 [remove'] R1\n",
40+ " 1 [2 3 4] 3 [remove'] R1\n",
41+ "\n",
42+ "For `R1` let's try `i cons`:\n",
43+ "\n",
44+ " 1 [2 3 4] 3 [remove'] i cons\n",
45+ " 1 [2 3 4] 3 remove' cons\n",
46+ " ...\n",
47+ " 1 2 [3 4] 3 remove' cons cons\n",
48+ " ...\n",
49+ " 1 2 [4] cons cons\n",
50+ " ...\n",
51+ " [1 2 4]\n",
52+ "\n",
53+ "Ergo:\n",
54+ "\n",
55+ " remove' == [swap first =] [pop rest] [[uncons] dip] [i cons] genrec\n",
56+ " remove == [pop not] [pop] [remove'] ifte\n"
57+ ]
58+ },
59+ {
60+ "cell_type": "code",
61+ "execution_count": 1,
62+ "id": "80f0926d",
63+ "metadata": {},
64+ "outputs": [
65+ {
66+ "name": "stdout",
67+ "output_type": "stream",
68+ "text": []
69+ }
70+ ],
71+ "source": [
72+ "[remove' [swap first =] [pop rest] [[uncons] dip] [i cons] genrec] inscribe\n",
73+ "[remo [pop not] [pop] [remove'] ifte] inscribe"
74+ ]
75+ },
76+ {
77+ "cell_type": "code",
78+ "execution_count": 2,
79+ "id": "6ef0d06a",
80+ "metadata": {},
81+ "outputs": [
82+ {
83+ "name": "stdout",
84+ "output_type": "stream",
85+ "text": [
86+ "[1 2 3 4] 3"
87+ ]
88+ }
89+ ],
90+ "source": [
91+ "[1 2 3 4] 3 "
92+ ]
93+ },
94+ {
95+ "cell_type": "code",
96+ "execution_count": 3,
97+ "id": "e0c12f34",
98+ "metadata": {},
99+ "outputs": [
100+ {
101+ "name": "stdout",
102+ "output_type": "stream",
103+ "text": [
104+ "[1 2 4]"
105+ ]
106+ }
107+ ],
108+ "source": [
109+ "remo"
110+ ]
111+ },
112+ {
113+ "cell_type": "markdown",
114+ "id": "e34f9996",
115+ "metadata": {},
116+ "source": [
117+ "So far so good but I made a mistake. The recursive part doesn't handle empty lists, so it's broken for the case of the item not being in the list:"
118+ ]
119+ },
120+ {
121+ "cell_type": "code",
122+ "execution_count": 4,
123+ "id": "ecb11a12",
124+ "metadata": {},
125+ "outputs": [
126+ {
127+ "name": "stdout",
128+ "output_type": "stream",
129+ "text": [
130+ "[1 2 4] 45"
131+ ]
132+ }
133+ ],
134+ "source": [
135+ "45"
136+ ]
137+ },
138+ {
139+ "cell_type": "code",
140+ "execution_count": null,
141+ "id": "fb6472f5",
142+ "metadata": {},
143+ "outputs": [],
144+ "source": [
145+ " remo"
146+ ]
147+ },
148+ {
149+ "cell_type": "markdown",
150+ "id": "fd33d021",
151+ "metadata": {},
152+ "source": [
153+ "## Second attempt\n",
154+ "\n",
155+ " remove == [pop not] [pop] [R0] [R1] genrec\n",
156+ " remove == [pop not] [pop] [R0 [remove] R1] ifte\n",
157+ "\n",
158+ "Non-empty:\n",
159+ "\n",
160+ " [a b c] item R0 [remove] R1\n",
161+ "\n",
162+ "\n",
163+ " R0 [remove] R1\n",
164+ " -----------------------------------------------------\n",
165+ " [swap first =] [pop rest] [E1 [remove] E2] ifte\n",
166+ "\n",
167+ "Recursive branch:\n",
168+ "\n",
169+ " [a b c] d E1 [remove] E2\n",
170+ "\n",
171+ "With:\n",
172+ "\n",
173+ " E1 == [uncons] dip\n",
174+ " E2 == i cons\n",
175+ "\n",
176+ " [a b c] d [uncons] dip [remove] i cons\n",
177+ " a [b c] d [remove] i cons\n",
178+ " a [b c] d remove cons\n",
179+ "\n",
180+ "How to make it?\n",
181+ "\n",
182+ " R0 == [swap first =] [pop rest]\n",
183+ "\n",
184+ "Then we want:\n",
185+ "\n",
186+ " R1 == [[uncons] dip [remove] i cons] ifte\n",
187+ "\n",
188+ "But of course `[remove]` can't appear in there like that, we have to package it up:\n",
189+ "\n",
190+ " R1 == [i cons] cons [[uncons] dip] swoncat ifte\n",
191+ "\n",
192+ "Or better yet:\n",
193+ "\n",
194+ " [[uncons] dip remove cons] ifte\n",
195+ "\n",
196+ " R1 == [cons] concat [[uncons] dip] swoncat ifte\n",
197+ "\n",
198+ "Clunky, but it works:\n",
199+ "\n",
200+ " remove == [pop not] [pop] [[swap first =] [pop rest]] [[cons] concat [[uncons] dip] swoncat ifte] genrec\n",
201+ " "
202+ ]
203+ },
204+ {
205+ "cell_type": "code",
206+ "execution_count": 6,
207+ "id": "891135c8",
208+ "metadata": {},
209+ "outputs": [
210+ {
211+ "name": "stdout",
212+ "output_type": "stream",
213+ "text": [
214+ "[1 2 4] 45"
215+ ]
216+ }
217+ ],
218+ "source": [
219+ "[remo2 [pop not] [pop] [[swap first =] [pop rest]] [[cons] concat [[uncons] dip] swoncat ifte] genrec] inscribe"
220+ ]
221+ },
222+ {
223+ "cell_type": "code",
224+ "execution_count": 7,
225+ "id": "c32ea032",
226+ "metadata": {},
227+ "outputs": [
228+ {
229+ "name": "stdout",
230+ "output_type": "stream",
231+ "text": [
232+ "[1 2 4]"
233+ ]
234+ }
235+ ],
236+ "source": [
237+ "remo2"
238+ ]
239+ },
240+ {
241+ "cell_type": "code",
242+ "execution_count": 8,
243+ "id": "6bd05f5b",
244+ "metadata": {},
245+ "outputs": [
246+ {
247+ "name": "stdout",
248+ "output_type": "stream",
249+ "text": [
250+ "[1 2 4] 2"
251+ ]
252+ }
253+ ],
254+ "source": [
255+ "2"
256+ ]
257+ },
258+ {
259+ "cell_type": "code",
260+ "execution_count": 9,
261+ "id": "20bdec4c",
262+ "metadata": {},
263+ "outputs": [
264+ {
265+ "name": "stdout",
266+ "output_type": "stream",
267+ "text": [
268+ "[1 4]"
269+ ]
270+ }
271+ ],
272+ "source": [
273+ "remo2"
274+ ]
275+ },
276+ {
277+ "cell_type": "markdown",
278+ "id": "7605e056",
279+ "metadata": {},
280+ "source": [
281+ "## Third attempt\n",
282+ "\n",
283+ "What if we let `[remove]` be on the stack instead of building the else-part each iteration?:\n",
284+ "\n",
285+ " remove == [pop not] [pop] [] [[P] [THEN] [ELSE] ifte] genrec\n",
286+ " remove == [pop not] [pop] [ [remove] [P] [THEN] [ELSE] ifte] ifte\n",
287+ "\n",
288+ "So:\n",
289+ "\n",
290+ " [a b c] item [remove] [P] [THEN] [ELSE] ifte\n",
291+ " \n",
292+ " P == pop swap first =\n",
293+ " \n",
294+ " THEN == popop rest\n",
295+ " \n",
296+ " ELSE == ...\n",
297+ "\n",
298+ "Hmm...\n",
299+ "\n",
300+ " [a b c] item [remove] ELSE\n",
301+ " [a b c] item [remove] [uncons] dipd i cons\n",
302+ " a [b c] item [remove] i cons\n",
303+ " a [b c] item remove cons\n",
304+ " ...\n",
305+ " a [b c] cons\n",
306+ " [a b c]\n",
307+ "\n",
308+ "So:\n",
309+ "\n",
310+ " ELSE == [uncons] dipd i cons\n",
311+ "\n",
312+ "And:\n",
313+ "\n",
314+ " remove == [pop not] [pop] [] [[pop swap first =] [popop rest] [[uncons] dipd i cons] ifte] genrec"
315+ ]
316+ },
317+ {
318+ "cell_type": "code",
319+ "execution_count": 10,
320+ "id": "acd3f326",
321+ "metadata": {},
322+ "outputs": [
323+ {
324+ "name": "stdout",
325+ "output_type": "stream",
326+ "text": [
327+ "[1 4]"
328+ ]
329+ }
330+ ],
331+ "source": [
332+ "[remo3 [pop not] [pop] [] [[pop swap first =] [popop rest] [[uncons] dipd i cons] ifte] genrec] inscribe"
333+ ]
334+ },
335+ {
336+ "cell_type": "code",
337+ "execution_count": 11,
338+ "id": "70178b16",
339+ "metadata": {},
340+ "outputs": [
341+ {
342+ "name": "stdout",
343+ "output_type": "stream",
344+ "text": [
345+ "[1 4 5 6]"
346+ ]
347+ }
348+ ],
349+ "source": [
350+ "[5 6] concat"
351+ ]
352+ },
353+ {
354+ "cell_type": "code",
355+ "execution_count": 12,
356+ "id": "f6cb0b12",
357+ "metadata": {},
358+ "outputs": [
359+ {
360+ "name": "stdout",
361+ "output_type": "stream",
362+ "text": [
363+ "[1 4 5 6] 5"
364+ ]
365+ }
366+ ],
367+ "source": [
368+ "5"
369+ ]
370+ },
371+ {
372+ "cell_type": "code",
373+ "execution_count": 13,
374+ "id": "d2e6aeb8",
375+ "metadata": {},
376+ "outputs": [
377+ {
378+ "name": "stdout",
379+ "output_type": "stream",
380+ "text": [
381+ "[1 4 6]"
382+ ]
383+ }
384+ ],
385+ "source": [
386+ "remo3"
387+ ]
388+ },
389+ {
390+ "cell_type": "code",
391+ "execution_count": 14,
392+ "id": "f2c8c0be",
393+ "metadata": {},
394+ "outputs": [
395+ {
396+ "name": "stdout",
397+ "output_type": "stream",
398+ "text": [
399+ "[1 4 6] 5"
400+ ]
401+ }
402+ ],
403+ "source": [
404+ "5"
405+ ]
406+ },
407+ {
408+ "cell_type": "code",
409+ "execution_count": 15,
410+ "id": "deb5e389",
411+ "metadata": {},
412+ "outputs": [
413+ {
414+ "name": "stdout",
415+ "output_type": "stream",
416+ "text": [
417+ "[1 4 6]"
418+ ]
419+ }
420+ ],
421+ "source": [
422+ "remo3"
423+ ]
424+ },
425+ {
426+ "cell_type": "code",
427+ "execution_count": 16,
428+ "id": "84fc4e3f",
429+ "metadata": {},
430+ "outputs": [
431+ {
432+ "name": "stdout",
433+ "output_type": "stream",
434+ "text": [
435+ "[] 5"
436+ ]
437+ }
438+ ],
439+ "source": [
440+ "pop [] 5"
441+ ]
442+ },
443+ {
444+ "cell_type": "code",
445+ "execution_count": 17,
446+ "id": "ee99b894",
447+ "metadata": {},
448+ "outputs": [
449+ {
450+ "name": "stdout",
451+ "output_type": "stream",
452+ "text": [
453+ "[]"
454+ ]
455+ }
456+ ],
457+ "source": [
458+ "remo3"
459+ ]
460+ },
461+ {
462+ "cell_type": "code",
463+ "execution_count": null,
464+ "id": "0518f168",
465+ "metadata": {},
466+ "outputs": [],
467+ "source": []
468+ }
469+ ],
470+ "metadata": {
471+ "kernelspec": {
472+ "display_name": "Joypy",
473+ "language": "",
474+ "name": "thun"
475+ },
476+ "language_info": {
477+ "file_extension": ".joy",
478+ "mimetype": "text/plain",
479+ "name": "Joy"
480+ }
481+ },
482+ "nbformat": 4,
483+ "nbformat_minor": 5
484+}
Afficher sur ancien navigateur de dépôt.