docs/Recursion_Combinators.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "markdown",
   5    "metadata": {},
   6    "source": [
   7     "# Recursion Combinators\n",
   8     "\n",
   9     "This article describes the `genrec` combinator and how to use it, then several generic specializations.\n",
  10     "\n",
  11     "## General Recursive Function\n",
  12     "\n",
  13     "In Joy recursive functions are defined by four quoted programs and the `genrec` combinator.\n",
  14     "\n",
  15     "    F == [if] [then] [rec1] [rec2] genrec\n",
  16     "\n",
  17     "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",
  18     "\n",
  19     "                          [if] [then] [rec1] [rec2] genrec\n",
  20     "    ---------------------------------------------------------------------\n",
  21     "       [if] [then] [rec1 [[if] [then] [rec1] [rec2] genrec] rec2] ifte\n",
  22     "\n",
  23     "\n",
  24     "From \"Recursion Theory and Joy\" (j05cmp.html) by Manfred von Thun:\n",
  25     "\n",
  26     "> \"The genrec combinator takes four program parameters in addition to\n",
  27     "whatever data parameters it needs. Fourth from the top is an if-part,\n",
  28     "followed by a then-part. If the if-part yields true, then the then-part\n",
  29     "is executed and the combinator terminates. The other two parameters are\n",
  30     "the rec1-part and the rec2-part. If the if-part yields false, the\n",
  31     "rec1-part is executed. Following that the four program parameters and\n",
  32     "the combinator are again pushed onto the stack bundled up in a quoted\n",
  33     "form. Then the rec2-part is executed, where it will find the bundled\n",
  34     "form. Typically it will then execute the bundled form, either with i or\n",
  35     "with app2, or some other combinator.\"\n",
  36     "\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",
  52     "## [Hylomorphism](https://en.wikipedia.org/wiki/Hylomorphism_%28computer_science%29)\n",
  53     "\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",
  55     "\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",
  60     "- Recursive calls (zero or more); it has a \"call stack in the form of a cons list\".\n",
  61     "\n",
  62     "It may be helpful to see this function implemented in pseudocode (Python).\n",
  63     "\n",
  64     "    def hylomorphism(c, Q, P, G):\n",
  65     "        '''Return a hylomorphism function H.'''\n",
  66     "\n",
  67     "        def H(a):\n",
  68     "            if P(a):\n",
  69     "                return c\n",
  70     "            b, aa = G(a)\n",
  71     "            return Q(b, H(aa))\n",
  72     "\n",
  73     "        return H\n",
  74     "\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",
  79     "## Hylomorphism in Joy\n",
  80     "\n",
  81     "       a H\n",
  82     "    ---------\n",
  83     "        c\n",
  84     "\n",
  85     "We can define a combinator `hylomorphism` that will make a hylomorphism combinator `H` from constituent parts.\n",
  86     "\n",
  87     "    H == [P] c [G] [Q] hylomorphism\n",
  88     "\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",
  91     "The then-part just discards the leftover `a` and replaces it with the base case value `c`:\n",
  92     "\n",
  93     "    H == [P] [pop c] [J] ifte\n",
  94     "\n",
  95     "The else-part `J` gets just the argument `a` on the stack.\n",
  96     "\n",
  97     "    a J\n",
  98     "\n",
  99     "The first thing to do is use the generator `G` which produces values `b` and a new `aa`:\n",
 100     "\n",
 101     "        a G\n",
 102     "    ----------\n",
 103     "       aa b\n",
 104     "\n",
 105     "So:\n",
 106     "\n",
 107     "    J == G J′\n",
 108     "\n",
 109     "Then we recur with `H` on `aa`:\n",
 110     "\n",
 111     "       aa b [H] dip\n",
 112     "    ------------------\n",
 113     "         aa H b\n",
 114     "    ------------------\n",
 115     "          cc b\n",
 116     "\n",
 117     "So:\n",
 118     "\n",
 119     "    J′ == [H] dip J″\n",
 120     "\n",
 121     "And run `Q` on the result:\n",
 122     "\n",
 123     "       cc b Q\n",
 124     "    ------------\n",
 125     "         c\n",
 126     "So:\n",
 127     "\n",
 128     "    J″ == Q\n",
 129     "\n",
 130     "Summing up:\n",
 131     "\n",
 132     "    J  == G J′\n",
 133     "    J′ == [H] dip J″\n",
 134     "    J″ == Q\n",
 135     "\n",
 136     "This gives us a definition for `J`:\n",
 137     "\n",
 138     "    J == G [H] dip Q\n",
 139     "\n",
 140     "Plug it in and convert to genrec:\n",
 141     "\n",
 142     "    H == [P] [pop c] [     J     ] ifte\n",
 143     "         [P] [pop c] [G [H] dip Q] ifte\n",
 144     "         [P] [pop c] [G]   [dip Q] genrec\n",
 145     "\n",
 146     "This is the form of a hylomorphism in Joy, which nicely illustrates that\n",
 147     "it is a simple specialization of the general recursion combinator.\n",
 148     "\n",
 149     "    [P]      c  [G]     [Q] hylomorphism\n",
 150     "    [P] [pop c] [G] [dip Q] genrec\n",
 151     "\n",
 152     "## Derivation of `hylomorphism` combinator\n",
 153     "\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",
 156     "\n",
 157     "       [P]      c  [G]     [F] hylomorphism\n",
 158     "    ------------------------------------------\n",
 159     "       [P] [pop c] [G] [dip F] genrec\n",
 160     "\n",
 161     "Working in reverse:\n",
 162     "\n",
 163     "- Use `swoncat` twice to decouple `[c]` and `[F]`.\n",
 164     "- Use `unit` to dequote `c`.\n",
 165     "- Use `dipd` to untangle `[unit [pop] swoncat]` from the givens.\n",
 166     "\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",
 171     "\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",
 174     "\n",
 175     "    hylomorphism == [unit [pop] swoncat] dipd [dip] swoncat genrec"
 176    ]
 177   },
 178   {
 179    "cell_type": "code",
 180    "execution_count": 1,
 181    "metadata": {},
 182    "outputs": [
 183     {
 184      "name": "stdout",
 185      "output_type": "stream",
 186      "text": []
 187     }
 188    ],
 189    "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 `[+]`"
 206    ]
 207   },
 208   {
 209    "cell_type": "code",
 210    "execution_count": 2,
 211    "metadata": {},
 212    "outputs": [
 213     {
 214      "name": "stdout",
 215      "output_type": "stream",
 216      "text": []
 217     }
 218    ],
 219    "source": [
 220     "[triangular_number [1 <=] 0 [-- dup] [+] hylomorphism] inscribe"
 221    ]
 222   },
 223   {
 224    "cell_type": "markdown",
 225    "metadata": {},
 226    "source": [
 227     "Let's try it:"
 228    ]
 229   },
 230   {
 231    "cell_type": "code",
 232    "execution_count": 3,
 233    "metadata": {},
 234    "outputs": [
 235     {
 236      "name": "stdout",
 237      "output_type": "stream",
 238      "text": [
 239       "10"
 240      ]
 241     }
 242    ],
 243    "source": [
 244     "5 triangular_number"
 245    ]
 246   },
 247   {
 248    "cell_type": "code",
 249    "execution_count": 4,
 250    "metadata": {},
 251    "outputs": [
 252     {
 253      "name": "stdout",
 254      "output_type": "stream",
 255      "text": [
 256       "[0 0 1 3 6 10 15 21]"
 257      ]
 258     }
 259    ],
 260    "source": [
 261     "clear\n",
 262     "\n",
 263     "[0 1 2 3 4 5 6 7] [triangular_number] map"
 264    ]
 265   },
 266   {
 267    "cell_type": "markdown",
 268    "metadata": {},
 269    "source": [
 270     "Neat!"
 271    ]
 272   },
 273   {
 274    "cell_type": "markdown",
 275    "metadata": {},
 276    "source": [
 277     "## 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",
 279     "\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",
 284     "\n",
 285     "The working of the generator function `G` differs slightly for each.  Consider the recursive branches:\n",
 286     "\n",
 287     "    ... a G [H1] dip F                w/ a G == a′ b\n",
 288     "    \n",
 289     "    ... c a G [F] dip H2                 a G == b  a′\n",
 290     "    \n",
 291     "    ... a [G] dupdip [H3] dip F          a G == a′\n",
 292     "    \n",
 293     "    ... c a [F] dupdip G H4              a G == a′\n",
 294     "\n",
 295     "The following four sections illustrate how these work, omitting the predicate evaluation."
 296    ]
 297   },
 298   {
 299    "cell_type": "markdown",
 300    "metadata": {},
 301    "source": [
 302     "### `H1`\n",
 303     "\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`."
 324    ]
 325   },
 326   {
 327    "cell_type": "markdown",
 328    "metadata": {},
 329    "source": [
 330     "### `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",
 332     "\n",
 333     "    H2 == c swap [P] [pop] [G [F] dip] primrec\n",
 334     "\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"
 349    ]
 350   },
 351   {
 352    "cell_type": "markdown",
 353    "metadata": {},
 354    "source": [
 355     "### `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",
 360     "\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″"
 378    ]
 379   },
 380   {
 381    "cell_type": "markdown",
 382    "metadata": {},
 383    "source": [
 384     "### `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",
 412     "\n",
 413     "    A == [P] [] [G] [swons] hylomorphism"
 414    ]
 415   },
 416   {
 417    "cell_type": "markdown",
 418    "metadata": {},
 419    "source": [
 420     "### `range` et. al.\n",
 421     "\n",
 422     "An example of an anamorphism is the `range` function which generates the list of integers from 0 to *n* - 1 given *n*.\n",
 423     "\n",
 424     "Each of the above variations can be used to make four slightly different `range` functions."
 425    ]
 426   },
 427   {
 428    "cell_type": "markdown",
 429    "metadata": {},
 430    "source": [
 431     "#### `range` with `H1`\n",
 432     "    H1 == [P]    [pop c]  [G]      [dip F]     genrec\n",
 433     "       == [0 <=] [pop []] [-- dup] [dip swons] genrec"
 434    ]
 435   },
 436   {
 437    "cell_type": "code",
 438    "execution_count": 5,
 439    "metadata": {},
 440    "outputs": [
 441     {
 442      "name": "stdout",
 443      "output_type": "stream",
 444      "text": []
 445     }
 446    ],
 447    "source": [
 448     "clear "
 449    ]
 450   },
 451   {
 452    "cell_type": "code",
 453    "execution_count": 6,
 454    "metadata": {},
 455    "outputs": [
 456     {
 457      "name": "stdout",
 458      "output_type": "stream",
 459      "text": []
 460     }
 461    ],
 462    "source": [
 463     "[range [0 <=] [] [-- dup] [swons] hylomorphism] inscribe"
 464    ]
 465   },
 466   {
 467    "cell_type": "code",
 468    "execution_count": 7,
 469    "metadata": {
 470     "scrolled": false
 471    },
 472    "outputs": [
 473     {
 474      "name": "stdout",
 475      "output_type": "stream",
 476      "text": [
 477       "[4 3 2 1 0]"
 478      ]
 479     }
 480    ],
 481    "source": [
 482     "5 range"
 483    ]
 484   },
 485   {
 486    "cell_type": "markdown",
 487    "metadata": {},
 488    "source": [
 489     "#### `range` with `H2`\n",
 490     "    H2 == c  swap [P]    [pop] [G      [F]     dip] tailrec\n",
 491     "       == [] swap [0 <=] [pop] [-- dup [swons] dip] tailrec"
 492    ]
 493   },
 494   {
 495    "cell_type": "code",
 496    "execution_count": 8,
 497    "metadata": {},
 498    "outputs": [
 499     {
 500      "name": "stdout",
 501      "output_type": "stream",
 502      "text": []
 503     }
 504    ],
 505    "source": [
 506     "clear "
 507    ]
 508   },
 509   {
 510    "cell_type": "code",
 511    "execution_count": 9,
 512    "metadata": {},
 513    "outputs": [
 514     {
 515      "name": "stdout",
 516      "output_type": "stream",
 517      "text": []
 518     }
 519    ],
 520    "source": [
 521     "[range_reverse [] swap [0 <=] [pop] [-- dup [swons] dip] tailrec] inscribe"
 522    ]
 523   },
 524   {
 525    "cell_type": "code",
 526    "execution_count": 10,
 527    "metadata": {
 528     "scrolled": true
 529    },
 530    "outputs": [
 531     {
 532      "name": "stdout",
 533      "output_type": "stream",
 534      "text": [
 535       "[0 1 2 3 4]"
 536      ]
 537     }
 538    ],
 539    "source": [
 540     "5 range_reverse"
 541    ]
 542   },
 543   {
 544    "cell_type": "markdown",
 545    "metadata": {},
 546    "source": [
 547     "#### `range` with `H3`\n",
 548     "    H3 == [P]    [pop c]  [[G]  dupdip] [dip F]     genrec\n",
 549     "       == [0 <=] [pop []] [[--] dupdip] [dip swons] genrec"
 550    ]
 551   },
 552   {
 553    "cell_type": "code",
 554    "execution_count": 11,
 555    "metadata": {},
 556    "outputs": [
 557     {
 558      "name": "stdout",
 559      "output_type": "stream",
 560      "text": []
 561     }
 562    ],
 563    "source": [
 564     "clear "
 565    ]
 566   },
 567   {
 568    "cell_type": "code",
 569    "execution_count": 12,
 570    "metadata": {},
 571    "outputs": [
 572     {
 573      "name": "stdout",
 574      "output_type": "stream",
 575      "text": []
 576     }
 577    ],
 578    "source": [
 579     "[ranger [0 <=] [pop []] [[--] dupdip] [dip swons] genrec] inscribe"
 580    ]
 581   },
 582   {
 583    "cell_type": "code",
 584    "execution_count": 13,
 585    "metadata": {
 586     "scrolled": true
 587    },
 588    "outputs": [
 589     {
 590      "name": "stdout",
 591      "output_type": "stream",
 592      "text": [
 593       "[5 4 3 2 1]"
 594      ]
 595     }
 596    ],
 597    "source": [
 598     "5 ranger"
 599    ]
 600   },
 601   {
 602    "cell_type": "markdown",
 603    "metadata": {},
 604    "source": [
 605     "#### `range` with `H4`\n",
 606     "    H4 == c  swap [P]    [pop] [[F]     dupdip G ] primrec\n",
 607     "       == [] swap [0 <=] [pop] [[swons] dupdip --] primrec"
 608    ]
 609   },
 610   {
 611    "cell_type": "code",
 612    "execution_count": 14,
 613    "metadata": {},
 614    "outputs": [
 615     {
 616      "name": "stdout",
 617      "output_type": "stream",
 618      "text": []
 619     }
 620    ],
 621    "source": [
 622     "clear "
 623    ]
 624   },
 625   {
 626    "cell_type": "code",
 627    "execution_count": 15,
 628    "metadata": {},
 629    "outputs": [
 630     {
 631      "name": "stdout",
 632      "output_type": "stream",
 633      "text": []
 634     }
 635    ],
 636    "source": [
 637     "[ranger_reverse [] swap [0 <=] [pop] [[swons] dupdip --] tailrec] inscribe"
 638    ]
 639   },
 640   {
 641    "cell_type": "code",
 642    "execution_count": 16,
 643    "metadata": {
 644     "scrolled": true
 645    },
 646    "outputs": [
 647     {
 648      "name": "stdout",
 649      "output_type": "stream",
 650      "text": [
 651       "[1 2 3 4 5]"
 652      ]
 653     }
 654    ],
 655    "source": [
 656     "5 ranger_reverse"
 657    ]
 658   },
 659   {
 660    "cell_type": "markdown",
 661    "metadata": {},
 662    "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",
 667     "\n",
 668     "    C == [not] c [uncons swap] [F] hylomorphism\n",
 669     "\n",
 670     "An example of a catamorphism is the sum function.\n",
 671     "\n",
 672     "    sum == [not] 0 [uncons swap] [+] hylomorphism"
 673    ]
 674   },
 675   {
 676    "cell_type": "code",
 677    "execution_count": 17,
 678    "metadata": {},
 679    "outputs": [
 680     {
 681      "name": "stdout",
 682      "output_type": "stream",
 683      "text": []
 684     }
 685    ],
 686    "source": [
 687     "clear "
 688    ]
 689   },
 690   {
 691    "cell_type": "code",
 692    "execution_count": 18,
 693    "metadata": {},
 694    "outputs": [
 695     {
 696      "name": "stdout",
 697      "output_type": "stream",
 698      "text": []
 699     }
 700    ],
 701    "source": [
 702     "[sum [not] 0 [uncons swap] [+] hylomorphism] inscribe"
 703    ]
 704   },
 705   {
 706    "cell_type": "code",
 707    "execution_count": 19,
 708    "metadata": {},
 709    "outputs": [
 710     {
 711      "name": "stdout",
 712      "output_type": "stream",
 713      "text": [
 714       "15"
 715      ]
 716     }
 717    ],
 718    "source": [
 719     "[5 4 3 2 1] sum"
 720    ]
 721   },
 722   {
 723    "cell_type": "code",
 724    "execution_count": 20,
 725    "metadata": {},
 726    "outputs": [
 727     {
 728      "name": "stdout",
 729      "output_type": "stream",
 730      "text": []
 731     }
 732    ],
 733    "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`."
 743    ]
 744   },
 745   {
 746    "cell_type": "code",
 747    "execution_count": 21,
 748    "metadata": {},
 749    "outputs": [
 750     {
 751      "name": "stdout",
 752      "output_type": "stream",
 753      "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"
 780      ]
 781     }
 782    ],
 783    "source": [
 784     "[step] help"
 785    ]
 786   },
 787   {
 788    "cell_type": "code",
 789    "execution_count": 22,
 790    "metadata": {},
 791    "outputs": [
 792     {
 793      "name": "stdout",
 794      "output_type": "stream",
 795      "text": []
 796     }
 797    ],
 798    "source": [
 799     "[sum 0 swap [+] step] inscribe"
 800    ]
 801   },
 802   {
 803    "cell_type": "code",
 804    "execution_count": 23,
 805    "metadata": {},
 806    "outputs": [
 807     {
 808      "name": "stdout",
 809      "output_type": "stream",
 810      "text": [
 811       "15"
 812      ]
 813     }
 814    ],
 815    "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 <="
 835    ]
 836   },
 837   {
 838    "cell_type": "code",
 839    "execution_count": 24,
 840    "metadata": {},
 841    "outputs": [
 842     {
 843      "name": "stdout",
 844      "output_type": "stream",
 845      "text": []
 846     }
 847    ],
 848    "source": [
 849     "clear"
 850    ]
 851   },
 852   {
 853    "cell_type": "code",
 854    "execution_count": 25,
 855    "metadata": {},
 856    "outputs": [
 857     {
 858      "name": "stdout",
 859      "output_type": "stream",
 860      "text": []
 861     }
 862    ],
 863    "source": [
 864     "[factorial 1 swap [1 <=] [pop] [[*] dupdip --] tailrec] inscribe"
 865    ]
 866   },
 867   {
 868    "cell_type": "code",
 869    "execution_count": 26,
 870    "metadata": {
 871     "scrolled": false
 872    },
 873    "outputs": [
 874     {
 875      "name": "stdout",
 876      "output_type": "stream",
 877      "text": [
 878       "120"
 879      ]
 880     }
 881    ],
 882    "source": [
 883     "5 factorial"
 884    ]
 885   },
 886   {
 887    "cell_type": "markdown",
 888    "metadata": {},
 889    "source": [
 890     "## Example: `tails`\n",
 891     "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.\n",
 892     "\n",
 893     "        [1 2 3] tails\n",
 894     "    --------------------\n",
 895     "       [[] [3] [2 3]]\n",
 896     "    \n",
 897     "\n",
 898     "We can build as we go, and we want `Q` to run after `G`, so we use pattern `H2`:\n",
 899     "\n",
 900     "    H2 == c swap [P] [pop] [G [Q] dip] tailrec\n",
 901     "\n",
 902     "We would use:\n",
 903     "\n",
 904     "    c == []\n",
 905     "    Q == swons\n",
 906     "    G == rest dup\n",
 907     "    P == not"
 908    ]
 909   },
 910   {
 911    "cell_type": "code",
 912    "execution_count": 27,
 913    "metadata": {},
 914    "outputs": [
 915     {
 916      "name": "stdout",
 917      "output_type": "stream",
 918      "text": []
 919     }
 920    ],
 921    "source": [
 922     "clear"
 923    ]
 924   },
 925   {
 926    "cell_type": "code",
 927    "execution_count": 28,
 928    "metadata": {},
 929    "outputs": [
 930     {
 931      "name": "stdout",
 932      "output_type": "stream",
 933      "text": []
 934     }
 935    ],
 936    "source": [
 937     "[tails [] swap [not] [pop] [rest dup [swons] dip] tailrec] inscribe"
 938    ]
 939   },
 940   {
 941    "cell_type": "code",
 942    "execution_count": 29,
 943    "metadata": {},
 944    "outputs": [
 945     {
 946      "name": "stdout",
 947      "output_type": "stream",
 948      "text": [
 949       "[[] [3] [2 3]]"
 950      ]
 951     }
 952    ],
 953    "source": [
 954     "[1 2 3] tails"
 955    ]
 956   },
 957   {
 958    "cell_type": "markdown",
 959    "metadata": {},
 960    "source": [
 961     "## Conclusion: Patterns of Recursion\n",
 962     "Our story so far...\n",
 963     "\n",
 964     "\n",
 965     "### Hylo-, Ana-, Cata-\n",
 966     "\n",
 967     "    H == [P  ] [pop c ] [G          ] [dip F        ] genrec\n",
 968     "    A == [P  ] [pop []] [G          ] [dip swap cons] genrec\n",
 969     "    C == [not] [pop c ] [uncons swap] [dip F        ] genrec\n",
 970     "\n",
 971     "### Para-, ?-, ?-\n",
 972     "\n",
 973     "    P == c  swap [P  ] [pop] [[F        ] dupdip G          ] primrec\n",
 974     "    ? == [] swap [P  ] [pop] [[swap cons] dupdip G          ] primrec\n",
 975     "    ? == c  swap [not] [pop] [[F        ] dupdip uncons swap] primrec\n"
 976    ]
 977   },
 978   {
 979    "cell_type": "markdown",
 980    "metadata": {},
 981    "source": [
 982     "## Appendix: Fun with Symbols\n",
 983     "\n",
 984     "    |[ (c, F), (G, P) ]| == (|c, F|) • [(G, P)]\n",
 985     "\n",
 986     "[\"Bananas, Lenses, & Barbed Wire\"](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.125)\n",
 987     "\n",
 988     "    (|...|)  [(...)]  [<...>]\n",
 989     "\n",
 990     "I think they are having slightly too much fun with the symbols.  However, \"Too much is always better than not enough.\""
 991    ]
 992   }
 993  ],
 994  "metadata": {
 995   "kernelspec": {
 996    "display_name": "Joypy",
 997    "language": "",
 998    "name": "thun"
 999   },
1000   "language_info": {
1001    "file_extension": ".joy",
1002    "mimetype": "text/plain",
1003    "name": "Joy"
1004   }
1005  },
1006  "nbformat": 4,
1007  "nbformat_minor": 2
1008 }