2 from notebook_preamble import D, DefinitionWrapper, J, V, define
5 # Recursion Combinators
7 This article describes the `genrec` combinator, how to use it, and several generic specializations.
9 [if] [then] [rec1] [rec2] genrec
10 ---------------------------------------------------------------------
11 [if] [then] [rec1 [[if] [then] [rec1] [rec2] genrec] rec2] ifte
14 From "Recursion Theory and Joy" (j05cmp.html) by Manfred von Thun:
16 > "The genrec combinator takes four program parameters in addition to
17 whatever data parameters it needs. Fourth from the top is an if-part,
18 followed by a then-part. If the if-part yields true, then the then-part
19 is executed and the combinator terminates. The other two parameters are
20 the rec1-part and the rec2-part. If the if-part yields false, the
21 rec1-part is executed. Following that the four program parameters and
22 the combinator are again pushed onto the stack bundled up in a quoted
23 form. Then the rec2-part is executed, where it will find the bundled
24 form. Typically it will then execute the bundled form, either with i or
25 with app2, or some other combinator."
27 ## Designing Recursive Functions
28 The way to design one of these is to fix your base case and
29 test and then treat `R1` and `R2` as an else-part "sandwiching"
30 a quotation of the whole function.
32 For example, given a (general recursive) function `F`:
34 F == [I] [T] [R1] [R2] genrec
35 == [I] [T] [R1 [F] R2] ifte
37 If the `[I]` predicate is false you must derive `R1` and `R2` from:
41 Set the stack arguments in front and figure out what `R1` and `R2`
42 have to do to apply the quoted `[F]` in the proper way.
44 ## Primitive Recursive Functions
45 Primitive recursive functions are those where `R2 == i`.
47 P == [I] [T] [R] primrec
48 == [I] [T] [R [P] i] ifte
51 ## [Hylomorphism](https://en.wikipedia.org/wiki/Hylomorphism_%28computer_science%29)
52 A [hylomorphism](https://en.wikipedia.org/wiki/Hylomorphism_%28computer_science%29) is a recursive function `H :: A -> C` that converts a value of type `A` into a value of type `C` by means of:
54 - A generator `G :: A -> (B, A)`
55 - A combiner `F :: (B, C) -> C`
56 - A predicate `P :: A -> Bool` to detect the base case
57 - A base case value `c :: C`
58 - Recursive calls (zero or more); it has a "call stack in the form of a cons list".
60 It may be helpful to see this function implemented in imperative Python code.
64 def hylomorphism(c, F, P, G):
65 '''Return a hylomorphism function H.'''
72 result = F(b, H(aa)) # b is stored in the stack frame during recursive call to H().
78 Cf. ["Bananas, Lenses, & Barbed Wire"](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.125)
80 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".
82 ## Hylomorphism in Joy
83 We can define a combinator `hylomorphism` that will make a hylomorphism combinator `H` from constituent parts.
85 H == [P] c [G] [F] hylomorphism
87 The function `H` is recursive, so we start with `ifte` and set the else-part to
88 some function `J` that will contain a quoted copy of `H`. (The then-part just
89 discards the leftover `a` and replaces it with the base case value `c`.)
91 H == [P] [pop c] [J] ifte
93 The else-part `J` gets just the argument `a` on the stack.
96 a G The first thing to do is use the generator G
97 aa b which produces b and a new aa
98 aa b [H] dip we recur with H on the new aa
99 aa H b F and run F on the result.
101 This gives us a definition for `J`.
105 Plug it in and convert to genrec.
107 H == [P] [pop c] [G [H] dip F] ifte
108 H == [P] [pop c] [G] [dip F] genrec
110 This is the form of a hylomorphism in Joy, which nicely illustrates that
111 it is a simple specialization of the general recursion combinator.
113 H == [P] c [G] [F] hylomorphism == [P] [pop c] [G] [dip F] genrec
115 ## Derivation of `hylomorphism` combinator
117 Now we just need to derive a definition that builds the `genrec` arguments
118 out of the pieces given to the `hylomorphism` combinator.
120 [P] c [G] [F] hylomorphism
121 ------------------------------------------
122 [P] [pop c] [G] [dip F] genrec
126 - Use `swoncat` twice to decouple `[c]` and `[F]`.
127 - Use `unit` to dequote `c`.
128 - Use `dipd` to untangle `[unit [pop] swoncat]` from the givens.
132 H == [P] [pop c] [G] [dip F] genrec
133 [P] [c] [pop] swoncat [G] [F] [dip] swoncat genrec
134 [P] c unit [pop] swoncat [G] [F] [dip] swoncat genrec
135 [P] c [G] [F] [unit [pop] swoncat] dipd [dip] swoncat genrec
137 At this point all of the arguments (givens) to the hylomorphism are to the left so we have
138 a definition for `hylomorphism`:
140 hylomorphism == [unit [pop] swoncat] dipd [dip] swoncat genrec
144 define('hylomorphism == [unit [pop] swoncat] dipd [dip] swoncat genrec')
147 ### Example: Finding [Triangular Numbers](https://en.wikipedia.org/wiki/Triangular_number)
148 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`.)
150 To sum a range of integers from 0 to *n* - 1:
154 - `[G]` is `[-- dup]`
159 define('triangular_number == [1 <=] 0 [-- dup] [+] hylomorphism')
166 J('5 triangular_number')
174 J('[0 1 2 3 4 5 6] [triangular_number] map')
180 ## Four Specializations
181 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.
183 H1 == [P] [pop c] [G ] [dip F] genrec
184 H2 == c swap [P] [pop] [G [F] dip ] [i] genrec
185 H3 == [P] [pop c] [ [G] dupdip ] [dip F] genrec
186 H4 == c swap [P] [pop] [ [F] dupdip G] [i] genrec
188 The working of the generator function `G` differs slightly for each. Consider the recursive branches:
190 ... a G [H1] dip F w/ a G == a′ b
192 ... c a G [F] dip H2 a G == b a′
194 ... a [G] dupdip [H3] dip F a G == a′
196 ... c a [F] dupdip G H4 a G == a′
198 The following four sections illustrate how these work, omitting the predicate evaluation.
202 H1 == [P] [pop c] [G] [dip F] genrec
209 ... a′ G [H1] dip F b F
210 ... a″ b′ [H1] dip F b F
212 ... a″ G [H1] dip F b′ F b F
213 ... a‴ b″ [H1] dip F b′ F b F
214 ... a‴ H1 b″ F b′ F b F
215 ... a‴ pop c b″ F b′ F b F
221 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`.
224 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.
226 H2 == c swap [P] [pop] [G [F] dip] primrec
229 ... c b a′ [F] dip H2
232 ... d a′ G [F] dip H2
233 ... d b′ a″ [F] dip H2
236 ... d′ a″ G [F] dip H2
237 ... d′ b″ a‴ [F] dip H2
245 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.)
248 H3 == [P] [pop c] [[G] dupdip] [dip F] genrec
250 ... a [G] dupdip [H3] dip F
254 ... a′ [G] dupdip [H3] dip F a F
255 ... a′ G a′ [H3] dip F a F
256 ... a″ a′ [H3] dip F a F
258 ... a″ [G] dupdip [H3] dip F a′ F a F
259 ... a″ G a″ [H3] dip F a′ F a F
260 ... a‴ a″ [H3] dip F a′ F a F
261 ... a‴ H3 a″ F a′ F a F
262 ... a‴ pop c a″ F a′ F a F
269 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:
271 H4 == c swap [P] [pop] [[F] dupdip G] primrec
273 ... c a [F] dupdip G H4
277 ... d a′ [F] dupdip G H4
281 ... d′ a″ [F] dupdip G H4
289 An anamorphism can be defined as a hylomorphism that uses `[]` for `c` and
290 `swons` for `F`. An anamorphic function builds a list of values.
292 A == [P] [] [G] [swons] hylomorphism
295 An example of an anamorphism is the `range` function which generates the list of integers from 0 to *n* - 1 given *n*.
297 Each of the above variations can be used to make four slightly different `range` functions.
299 #### `range` with `H1`
300 H1 == [P] [pop c] [G] [dip F] genrec
301 == [0 <=] [pop []] [-- dup] [dip swons] genrec
305 define('range == [0 <=] [] [-- dup] [swons] hylomorphism')
316 #### `range` with `H2`
317 H2 == c swap [P] [pop] [G [F] dip] primrec
318 == [] swap [0 <=] [pop] [-- dup [swons] dip] primrec
322 define('range_reverse == [] swap [0 <=] [pop] [-- dup [swons] dip] primrec')
333 #### `range` with `H3`
334 H3 == [P] [pop c] [[G] dupdip] [dip F] genrec
335 == [0 <=] [pop []] [[--] dupdip] [dip swons] genrec
339 define('ranger == [0 <=] [pop []] [[--] dupdip] [dip swons] genrec')
350 #### `range` with `H4`
351 H4 == c swap [P] [pop] [[F] dupdip G ] primrec
352 == [] swap [0 <=] [pop] [[swons] dupdip --] primrec
356 define('ranger_reverse == [] swap [0 <=] [pop] [[swons] dupdip --] primrec')
361 J('5 ranger_reverse')
367 Hopefully this illustrates the workings of the variations. For more insight you can run the cells using the `V()` function instead of the `J()` function to get a trace of the Joy evaluation.
370 A catamorphism can be defined as a hylomorphism that uses `[uncons swap]` for `[G]`
371 and `[[] =]` (or just `[not]`) for the predicate `[P]`. A catamorphic function tears down a list term-by-term and makes some new value.
373 C == [not] c [uncons swap] [F] hylomorphism
377 define('swuncons == uncons swap') # Awkward name.
380 An example of a catamorphism is the sum function.
382 sum == [not] 0 [swuncons] [+] hylomorphism
386 define('sum == [not] 0 [swuncons] [+] hylomorphism')
397 ### The `step` combinator
398 The `step` combinator will usually be better to use than `catamorphism`.
405 Run a quoted program on each item in a sequence.
409 -----------------------
414 ------------------------
418 ... [a b c] [Q] . step
419 ----------------------------------------
420 ... a . Q [b c] [Q] step
422 The step combinator executes the quotation on each member of the list
429 define('sum == 0 swap [+] step')
440 ## Example: Factorial Function
442 For the Factorial function:
444 H4 == c swap [P] [pop] [[F] dupdip G] primrec
455 define('factorial == 1 swap [1 <=] [pop] [[*] dupdip --] primrec')
467 An example of a paramorphism for lists given in the ["Bananas..." paper](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.125) is `tails` which returns the list of "tails" of a list.
474 We can build as we go, and we want `F` to run after `G`, so we use pattern `H2`:
476 H2 == c swap [P] [pop] [G [F] dip] primrec
487 define('tails == [] swap [not] [pop] [rest dup [swons] dip] primrec')
498 ## Conclusion: Patterns of Recursion
502 ### Hylo-, Ana-, Cata-
504 H == [P ] [pop c ] [G ] [dip F ] genrec
505 A == [P ] [pop []] [G ] [dip swap cons] genrec
506 C == [not] [pop c ] [uncons swap] [dip F ] genrec
510 P == c swap [P ] [pop] [[F ] dupdip G ] primrec
511 ? == [] swap [P ] [pop] [[swap cons] dupdip G ] primrec
512 ? == c swap [not] [pop] [[F ] dupdip uncons swap] primrec
515 ## Appendix: Fun with Symbols
517 |[ (c, F), (G, P) ]| == (|c, F|) • [(G, P)]
519 ["Bananas, Lenses, & Barbed Wire"](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.125)
521 (|...|) [(...)] [<...>]
523 I think they are having slightly too much fun with the symbols. However, "Too much is always better than not enough."