3 from notebook_preamble import D, DefinitionWrapper, J, V, define
8 This article describes the ``genrec`` combinator, how to use it, and
9 several generic specializations.
13 [if] [then] [rec1] [rec2] genrec
14 ---------------------------------------------------------------------
15 [if] [then] [rec1 [[if] [then] [rec1] [rec2] genrec] rec2] ifte
17 From “Recursion Theory and Joy” (j05cmp.html) by Manfred von Thun:
19 “The genrec combinator takes four program parameters in addition to
20 whatever data parameters it needs. Fourth from the top is an if-part,
21 followed by a then-part. If the if-part yields true, then the
22 then-part is executed and the combinator terminates. The other two
23 parameters are the rec1-part and the rec2-part. If the if-part yields
24 false, the rec1-part is executed. Following that the four program
25 parameters and the combinator are again pushed onto the stack bundled
26 up in a quoted form. Then the rec2-part is executed, where it will
27 find the bundled form. Typically it will then execute the bundled
28 form, either with i or with app2, or some other combinator.”
30 Designing Recursive Functions
31 -----------------------------
33 The way to design one of these is to fix your base case and test and
34 then treat ``R1`` and ``R2`` as an else-part “sandwiching” a quotation
35 of the whole function.
37 For example, given a (general recursive) function ``F``:
41 F == [I] [T] [R1] [R2] genrec
42 == [I] [T] [R1 [F] R2] ifte
44 If the ``[I]`` predicate is false you must derive ``R1`` and ``R2``
51 Set the stack arguments in front and figure out what ``R1`` and ``R2``
52 have to do to apply the quoted ``[F]`` in the proper way.
54 Primitive Recursive Functions
55 -----------------------------
57 Primitive recursive functions are those where ``R2 == i``.
61 P == [I] [T] [R] primrec
62 == [I] [T] [R [P] i] ifte
65 `Hylomorphism <https://en.wikipedia.org/wiki/Hylomorphism_%28computer_science%29>`__
66 ------------------------------------------------------------------------------------
69 `hylomorphism <https://en.wikipedia.org/wiki/Hylomorphism_%28computer_science%29>`__
70 is a recursive function ``H :: A -> C`` that converts a value of type
71 ``A`` into a value of type ``C`` by means of:
73 - A generator ``G :: A -> (B, A)``
74 - A combiner ``F :: (B, C) -> C``
75 - A predicate ``P :: A -> Bool`` to detect the base case
76 - A base case value ``c :: C``
77 - Recursive calls (zero or more); it has a “call stack in the form of a
80 It may be helpful to see this function implemented in imperative Python
85 def hylomorphism(c, F, P, G):
86 '''Return a hylomorphism function H.'''
93 result = F(b, H(aa)) # b is stored in the stack frame during recursive call to H().
98 Cf. `“Bananas, Lenses, & Barbed
99 Wire” <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.125>`__
101 Note that during evaluation of ``H()`` the intermediate ``b`` values are
102 stored in the Python call stack. This is what is meant by “call stack in
103 the form of a cons list”.
108 We can define a combinator ``hylomorphism`` that will make a
109 hylomorphism combinator ``H`` from constituent parts.
113 H == [P] c [G] [F] hylomorphism
115 The function ``H`` is recursive, so we start with ``ifte`` and set the
116 else-part to some function ``J`` that will contain a quoted copy of
117 ``H``. (The then-part just discards the leftover ``a`` and replaces it
118 with the base case value ``c``.)
122 H == [P] [pop c] [J] ifte
124 The else-part ``J`` gets just the argument ``a`` on the stack.
129 a G The first thing to do is use the generator G
130 aa b which produces b and a new aa
131 aa b [H] dip we recur with H on the new aa
132 aa H b F and run F on the result.
134 This gives us a definition for ``J``.
140 Plug it in and convert to genrec.
144 H == [P] [pop c] [G [H] dip F] ifte
145 H == [P] [pop c] [G] [dip F] genrec
147 This is the form of a hylomorphism in Joy, which nicely illustrates that
148 it is a simple specialization of the general recursion combinator.
152 H == [P] c [G] [F] hylomorphism == [P] [pop c] [G] [dip F] genrec
154 Derivation of ``hylomorphism`` combinator
155 -----------------------------------------
157 Now we just need to derive a definition that builds the ``genrec``
158 arguments out of the pieces given to the ``hylomorphism`` combinator.
162 [P] c [G] [F] hylomorphism
163 ------------------------------------------
164 [P] [pop c] [G] [dip F] genrec
168 - Use ``swoncat`` twice to decouple ``[c]`` and ``[F]``.
169 - Use ``unit`` to dequote ``c``.
170 - Use ``dipd`` to untangle ``[unit [pop] swoncat]`` from the givens.
176 H == [P] [pop c] [G] [dip F] genrec
177 [P] [c] [pop] swoncat [G] [F] [dip] swoncat genrec
178 [P] c unit [pop] swoncat [G] [F] [dip] swoncat genrec
179 [P] c [G] [F] [unit [pop] swoncat] dipd [dip] swoncat genrec
181 At this point all of the arguments (givens) to the hylomorphism are to
182 the left so we have a definition for ``hylomorphism``:
186 hylomorphism == [unit [pop] swoncat] dipd [dip] swoncat genrec
190 define('hylomorphism == [unit [pop] swoncat] dipd [dip] swoncat genrec')
192 Example: Finding `Triangular Numbers <https://en.wikipedia.org/wiki/Triangular_number>`__
193 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
195 Let’s write a function that, given a positive integer, returns the sum
196 of all positive integers less than that one. (In this case the types
197 ``A``, ``B`` and ``C`` are all ``int``.)
199 To sum a range of integers from 0 to *n* - 1:
201 - ``[P]`` is ``[1 <=]``
203 - ``[G]`` is ``[-- dup]``
208 define('triangular_number == [1 <=] 0 [-- dup] [+] hylomorphism')
214 J('5 triangular_number')
224 J('[0 1 2 3 4 5 6] [triangular_number] map')
235 There are at least four kinds of recursive combinator, depending on two
236 choices. The first choice is whether the combiner function ``F`` should
237 be evaluated during the recursion or pushed into the pending expression
238 to be “collapsed” at the end. The second choice is whether the combiner
239 needs to operate on the current value of the datastructure or the
240 generator’s output, in other words, whether ``F`` or ``G`` should run
241 first in the recursive branch.
245 H1 == [P] [pop c] [G ] [dip F] genrec
246 H2 == c swap [P] [pop] [G [F] dip ] [i] genrec
247 H3 == [P] [pop c] [ [G] dupdip ] [dip F] genrec
248 H4 == c swap [P] [pop] [ [F] dupdip G] [i] genrec
250 The working of the generator function ``G`` differs slightly for each.
251 Consider the recursive branches:
255 ... a G [H1] dip F w/ a G == a′ b
257 ... c a G [F] dip H2 a G == b a′
259 ... a [G] dupdip [H3] dip F a G == a′
261 ... c a [F] dupdip G H4 a G == a′
263 The following four sections illustrate how these work, omitting the
264 predicate evaluation.
271 H1 == [P] [pop c] [G] [dip F] genrec
280 ... a′ G [H1] dip F b F
281 ... a″ b′ [H1] dip F b F
283 ... a″ G [H1] dip F b′ F b F
284 ... a‴ b″ [H1] dip F b′ F b F
285 ... a‴ H1 b″ F b′ F b F
286 ... a‴ pop c b″ F b′ F b F
292 This form builds up a pending expression (continuation) that contains
293 the intermediate results along with the pending combiner functions. When
294 the base case is reached the last term is replaced by the identity value
295 ``c`` and the continuation “collapses” into the final result using the
301 When you can start with the identity value ``c`` on the stack and the
302 combiner ``F`` can operate as you go using the intermediate results
303 immediately rather than queuing them up, use this form. An important
304 difference is that the generator function must return its results in the
309 H2 == c swap [P] [pop] [G [F] dip] primrec
312 ... c b a′ [F] dip H2
315 ... d a′ G [F] dip H2
316 ... d b′ a″ [F] dip H2
319 ... d′ a″ G [F] dip H2
320 ... d′ b″ a‴ [F] dip H2
329 If you examine the traces above you’ll see that the combiner ``F`` only
330 gets to operate on the results of ``G``, it never “sees” the first value
331 ``a``. If the combiner and the generator both need to work on the
332 current value then ``dup`` must be used, and the generator must produce
333 one item instead of two (the b is instead the duplicate of a.)
337 H3 == [P] [pop c] [[G] dupdip] [dip F] genrec
339 ... a [G] dupdip [H3] dip F
343 ... a′ [G] dupdip [H3] dip F a F
344 ... a′ G a′ [H3] dip F a F
345 ... a″ a′ [H3] dip F a F
347 ... a″ [G] dupdip [H3] dip F a′ F a F
348 ... a″ G a″ [H3] dip F a′ F a F
349 ... a‴ a″ [H3] dip F a′ F a F
350 ... a‴ H3 a″ F a′ F a F
351 ... a‴ pop c a″ F a′ F a F
360 And, last but not least, if you can combine as you go, starting with
361 ``c``, and the combiner ``F`` needs to work on the current item, this is
366 H4 == c swap [P] [pop] [[F] dupdip G] primrec
368 ... c a [F] dupdip G H4
372 ... d a′ [F] dupdip G H4
376 ... d′ a″ [F] dupdip G H4
386 An anamorphism can be defined as a hylomorphism that uses ``[]`` for
387 ``c`` and ``swons`` for ``F``. An anamorphic function builds a list of
392 A == [P] [] [G] [swons] hylomorphism
394 ``range`` et. al. An example of an anamorphism is the ``range`` function which generates the list of integers from 0 to *n* - 1 given *n*.
395 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
397 Each of the above variations can be used to make four slightly different
400 ``range`` with ``H1``
401 ^^^^^^^^^^^^^^^^^^^^^
405 H1 == [P] [pop c] [G] [dip F] genrec
406 == [0 <=] [pop []] [-- dup] [dip swons] genrec
410 define('range == [0 <=] [] [-- dup] [swons] hylomorphism')
422 ``range`` with ``H2``
423 ^^^^^^^^^^^^^^^^^^^^^
427 H2 == c swap [P] [pop] [G [F] dip] primrec
428 == [] swap [0 <=] [pop] [-- dup [swons] dip] primrec
432 define('range_reverse == [] swap [0 <=] [pop] [-- dup [swons] dip] primrec')
444 ``range`` with ``H3``
445 ^^^^^^^^^^^^^^^^^^^^^
449 H3 == [P] [pop c] [[G] dupdip] [dip F] genrec
450 == [0 <=] [pop []] [[--] dupdip] [dip swons] genrec
454 define('ranger == [0 <=] [pop []] [[--] dupdip] [dip swons] genrec')
466 ``range`` with ``H4``
467 ^^^^^^^^^^^^^^^^^^^^^
471 H4 == c swap [P] [pop] [[F] dupdip G ] primrec
472 == [] swap [0 <=] [pop] [[swons] dupdip --] primrec
476 define('ranger_reverse == [] swap [0 <=] [pop] [[swons] dupdip --] primrec')
480 J('5 ranger_reverse')
488 Hopefully this illustrates the workings of the variations. For more
489 insight you can run the cells using the ``V()`` function instead of the
490 ``J()`` function to get a trace of the Joy evaluation.
495 A catamorphism can be defined as a hylomorphism that uses
496 ``[uncons swap]`` for ``[G]`` and ``[[] =]`` (or just ``[not]``) for the
497 predicate ``[P]``. A catamorphic function tears down a list term-by-term
498 and makes some new value.
502 C == [not] c [uncons swap] [F] hylomorphism
506 define('swuncons == uncons swap') # Awkward name.
508 An example of a catamorphism is the sum function.
512 sum == [not] 0 [swuncons] [+] hylomorphism
516 define('sum == [not] 0 [swuncons] [+] hylomorphism')
528 The ``step`` combinator
529 ~~~~~~~~~~~~~~~~~~~~~~~
531 The ``step`` combinator will usually be better to use than
541 Run a quoted program on each item in a sequence.
545 -----------------------
550 ------------------------
554 ... [a b c] [Q] . step
555 ----------------------------------------
556 ... a . Q [b c] [Q] step
558 The step combinator executes the quotation on each member of the list
565 define('sum == 0 swap [+] step')
577 Example: Factorial Function
578 ---------------------------
580 For the Factorial function:
584 H4 == c swap [P] [pop] [[F] dupdip G] primrec
597 define('factorial == 1 swap [1 <=] [pop] [[*] dupdip --] primrec')
612 An example of a paramorphism for lists given in the `“Bananas…”
613 paper <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.125>`__
614 is ``tails`` which returns the list of “tails” of a list.
622 We can build as we go, and we want ``F`` to run after ``G``, so we use
627 H2 == c swap [P] [pop] [G [F] dip] primrec
640 define('tails == [] swap [not] [pop] [rest dup [swons] dip] primrec')
652 Conclusion: Patterns of Recursion
653 ---------------------------------
662 H == [P ] [pop c ] [G ] [dip F ] genrec
663 A == [P ] [pop []] [G ] [dip swap cons] genrec
664 C == [not] [pop c ] [uncons swap] [dip F ] genrec
671 P == c swap [P ] [pop] [[F ] dupdip G ] primrec
672 ? == [] swap [P ] [pop] [[swap cons] dupdip G ] primrec
673 ? == c swap [not] [pop] [[F ] dupdip uncons swap] primrec
675 Appendix: Fun with Symbols
676 --------------------------
680 |[ (c, F), (G, P) ]| == (|c, F|) • [(G, P)]
682 `“Bananas, Lenses, & Barbed
683 Wire” <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.125>`__
687 (|...|) [(...)] [<...>]
689 I think they are having slightly too much fun with the symbols. However,
690 “Too much is always better than not enough.”