docs/Treestep.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "markdown",
   5    "metadata": {},
   6    "source": [
   7     "# Treating Trees II: `treestep`\n",
   8     "Let's consider a tree structure, similar to one described [\"Why functional programming matters\" by John Hughes](https://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf), that consists of a node value followed by zero or more child trees.  (The asterisk is meant to indicate the [Kleene star](https://en.wikipedia.org/wiki/Kleene_star).)\n",
   9     "\n",
  10     "    tree = [] | [node tree*]"
  11    ]
  12   },
  13   {
  14    "cell_type": "markdown",
  15    "metadata": {},
  16    "source": [
  17     "In the spirit of `step` we are going to define a combinator `treestep` which expects a tree and three additional items: a base-case function `[B]`, and two quoted programs `[N]` and `[C]`.\n",
  18     "\n",
  19     "    tree [B] [N] [C] treestep"
  20    ]
  21   },
  22   {
  23    "cell_type": "markdown",
  24    "metadata": {},
  25    "source": [
  26     "If the current tree node is empty then just execute `B`:\n",
  27     "\n",
  28     "       [] [B] [N] [C] treestep\n",
  29     "    ---------------------------\n",
  30     "       []  B"
  31    ]
  32   },
  33   {
  34    "cell_type": "markdown",
  35    "metadata": {},
  36    "source": [
  37     "Otherwise, evaluate `N` on the node value, `map` the whole function (abbreviated here as `K`) over the child trees recursively, and then combine the result with `C`.\n",
  38     "\n",
  39     "       [node tree*] [B] [N] [C] treestep\n",
  40     "    --------------------------------------- w/ K == [B] [N] [C] treestep\n",
  41     "           node N [tree*] [K] map C\n",
  42     "\n",
  43     "(Later on we'll experiment with making `map` part of `C` so you can use other combinators.)"
  44    ]
  45   },
  46   {
  47    "cell_type": "markdown",
  48    "metadata": {},
  49    "source": [
  50     "## Derive the recursive function.\n",
  51     "We can begin to derive it by finding the `ifte` stage that `genrec` will produce.\n",
  52     "\n",
  53     "    K == [not] [B] [R0]   [R1] genrec\n",
  54     "      == [not] [B] [R0 [K] R1] ifte\n",
  55     "\n",
  56     "So we just have to derive `J`:\n",
  57     "\n",
  58     "    J == R0 [K] R1"
  59    ]
  60   },
  61   {
  62    "cell_type": "markdown",
  63    "metadata": {},
  64    "source": [
  65     "The behavior of `J` is to accept a (non-empty) tree node and arrive at the desired outcome.\n",
  66     "\n",
  67     "           [node tree*] J\n",
  68     "    ------------------------------\n",
  69     "       node N [tree*] [K] map C"
  70    ]
  71   },
  72   {
  73    "cell_type": "markdown",
  74    "metadata": {},
  75    "source": [
  76     "So `J` will have some form like:\n",
  77     "\n",
  78     "    J == ... [N] ... [K] ... [C] ..."
  79    ]
  80   },
  81   {
  82    "cell_type": "markdown",
  83    "metadata": {},
  84    "source": [
  85     "Let's dive in.  First, unquote the node and `dip` `N`.\n",
  86     "\n",
  87     "    [node tree*] uncons [N] dip\n",
  88     "    node [tree*]        [N] dip\n",
  89     "    node N [tree*]"
  90    ]
  91   },
  92   {
  93    "cell_type": "markdown",
  94    "metadata": {},
  95    "source": [
  96     "Next, `map` `K` over the child trees and combine with `C`.\n",
  97     "\n",
  98     "    node N [tree*] [K] map C\n",
  99     "    node N [tree*] [K] map C\n",
 100     "    node N [K.tree*]       C"
 101    ]
 102   },
 103   {
 104    "cell_type": "markdown",
 105    "metadata": {},
 106    "source": [
 107     "So:\n",
 108     "\n",
 109     "    J == uncons [N] dip [K] map C"
 110    ]
 111   },
 112   {
 113    "cell_type": "markdown",
 114    "metadata": {},
 115    "source": [
 116     "Plug it in and convert to `genrec`:\n",
 117     "\n",
 118     "    K == [not] [B] [J                       ] ifte\n",
 119     "      == [not] [B] [uncons [N] dip [K] map C] ifte\n",
 120     "      == [not] [B] [uncons [N] dip]   [map C] genrec"
 121    ]
 122   },
 123   {
 124    "cell_type": "markdown",
 125    "metadata": {},
 126    "source": [
 127     "## Extract the givens to parameterize the program.\n",
 128     "Working backwards:\n",
 129     "\n",
 130     "    [not] [B]          [uncons [N] dip]                  [map C] genrec\n",
 131     "    [B] [not] swap     [uncons [N] dip]                  [map C] genrec\n",
 132     "    [B]                [uncons [N] dip] [[not] swap] dip [map C] genrec\n",
 133     "                                        ^^^^^^^^^^^^^^^^\n",
 134     "    [B] [[N] dip]      [uncons] swoncat [[not] swap] dip [map C] genrec\n",
 135     "    [B] [N] [dip] cons [uncons] swoncat [[not] swap] dip [map C] genrec\n",
 136     "            ^^^^^^^^^^^^^^^^^^^^^^^^^^^"
 137    ]
 138   },
 139   {
 140    "cell_type": "markdown",
 141    "metadata": {},
 142    "source": [
 143     "Extract a couple of auxiliary definitions:\n",
 144     "\n",
 145     "    TS.0 == [[not] swap] dip\n",
 146     "    TS.1 == [dip] cons [uncons] swoncat"
 147    ]
 148   },
 149   {
 150    "cell_type": "markdown",
 151    "metadata": {},
 152    "source": [
 153     "    [B] [N] TS.1 TS.0 [map C]                         genrec\n",
 154     "    [B] [N]           [map C]         [TS.1 TS.0] dip genrec\n",
 155     "    [B] [N] [C]         [map] swoncat [TS.1 TS.0] dip genrec\n",
 156     "\n",
 157     "The givens are all to the left so we have our definition."
 158    ]
 159   },
 160   {
 161    "cell_type": "markdown",
 162    "metadata": {},
 163    "source": [
 164     "### (alternate) Extract the givens to parameterize the program.\n",
 165     "Working backwards:\n",
 166     "\n",
 167     "    [not] [B]           [uncons [N] dip]            [map C] genrec\n",
 168     "    [not] [B] [N]       [dip] cons [uncons] swoncat [map C] genrec\n",
 169     "    [B] [N] [not] roll> [dip] cons [uncons] swoncat [map C] genrec\n",
 170     "            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^"
 171    ]
 172   },
 173   {
 174    "cell_type": "markdown",
 175    "metadata": {},
 176    "source": [
 177     "## Define `treestep`"
 178    ]
 179   },
 180   {
 181    "cell_type": "code",
 182    "execution_count": 1,
 183    "metadata": {},
 184    "outputs": [],
 185    "source": [
 186     "from notebook_preamble import D, J, V, define, DefinitionWrapper"
 187    ]
 188   },
 189   {
 190    "cell_type": "code",
 191    "execution_count": 2,
 192    "metadata": {},
 193    "outputs": [],
 194    "source": [
 195     "DefinitionWrapper.add_definitions('''\n",
 196     "\n",
 197     "    _treestep_0 == [[not] swap] dip\n",
 198     "    _treestep_1 == [dip] cons [uncons] swoncat\n",
 199     "    treegrind == [_treestep_1 _treestep_0] dip genrec\n",
 200     "    treestep == [map] swoncat treegrind\n",
 201     "\n",
 202     "''', D)"
 203    ]
 204   },
 205   {
 206    "cell_type": "markdown",
 207    "metadata": {},
 208    "source": [
 209     "## Examples\n",
 210     "Consider trees, the nodes of which are integers.  We can find the sum of all nodes in a tree with this function:\n",
 211     "\n",
 212     "    sumtree == [pop 0] [] [sum +] treestep"
 213    ]
 214   },
 215   {
 216    "cell_type": "code",
 217    "execution_count": 3,
 218    "metadata": {},
 219    "outputs": [],
 220    "source": [
 221     "define('sumtree == [pop 0] [] [sum +] treestep')"
 222    ]
 223   },
 224   {
 225    "cell_type": "markdown",
 226    "metadata": {},
 227    "source": [
 228     "Running this function on an empty tree value gives zero:\n",
 229     "\n",
 230     "       [] [pop 0] [] [sum +] treestep\n",
 231     "    ------------------------------------\n",
 232     "               0"
 233    ]
 234   },
 235   {
 236    "cell_type": "code",
 237    "execution_count": 4,
 238    "metadata": {},
 239    "outputs": [
 240     {
 241      "name": "stdout",
 242      "output_type": "stream",
 243      "text": [
 244       "0\n"
 245      ]
 246     }
 247    ],
 248    "source": [
 249     "J('[] sumtree')  # Empty tree."
 250    ]
 251   },
 252   {
 253    "cell_type": "markdown",
 254    "metadata": {},
 255    "source": [
 256     "Running it on a non-empty node:\n",
 257     "\n",
 258     "    [n tree*]  [pop 0] [] [sum +] treestep\n",
 259     "    n [tree*] [[pop 0] [] [sum +] treestep] map sum +\n",
 260     "    n [ ... ]                                   sum +\n",
 261     "    n m                                             +\n",
 262     "    n+m\n"
 263    ]
 264   },
 265   {
 266    "cell_type": "code",
 267    "execution_count": 5,
 268    "metadata": {
 269     "scrolled": true
 270    },
 271    "outputs": [
 272     {
 273      "name": "stdout",
 274      "output_type": "stream",
 275      "text": [
 276       "23\n"
 277      ]
 278     }
 279    ],
 280    "source": [
 281     "J('[23] sumtree')  # No child trees."
 282    ]
 283   },
 284   {
 285    "cell_type": "code",
 286    "execution_count": 6,
 287    "metadata": {
 288     "scrolled": true
 289    },
 290    "outputs": [
 291     {
 292      "name": "stdout",
 293      "output_type": "stream",
 294      "text": [
 295       "23\n"
 296      ]
 297     }
 298    ],
 299    "source": [
 300     "J('[23 []] sumtree')  # Child tree, empty."
 301    ]
 302   },
 303   {
 304    "cell_type": "code",
 305    "execution_count": 7,
 306    "metadata": {},
 307    "outputs": [
 308     {
 309      "name": "stdout",
 310      "output_type": "stream",
 311      "text": [
 312       "32\n"
 313      ]
 314     }
 315    ],
 316    "source": [
 317     "J('[23 [2 [4]] [3]] sumtree')  # Non-empty child trees."
 318    ]
 319   },
 320   {
 321    "cell_type": "code",
 322    "execution_count": 8,
 323    "metadata": {},
 324    "outputs": [
 325     {
 326      "name": "stdout",
 327      "output_type": "stream",
 328      "text": [
 329       "49\n"
 330      ]
 331     }
 332    ],
 333    "source": [
 334     "J('[23 [2 [8] [9]] [3] [4 []]] sumtree')  # Etc..."
 335    ]
 336   },
 337   {
 338    "cell_type": "code",
 339    "execution_count": 9,
 340    "metadata": {},
 341    "outputs": [
 342     {
 343      "name": "stdout",
 344      "output_type": "stream",
 345      "text": [
 346       "49\n"
 347      ]
 348     }
 349    ],
 350    "source": [
 351     "J('[23 [2 [8] [9]] [3] [4 []]] [pop 0] [] [cons sum] treestep')  # Alternate \"spelling\"."
 352    ]
 353   },
 354   {
 355    "cell_type": "code",
 356    "execution_count": 10,
 357    "metadata": {},
 358    "outputs": [
 359     {
 360      "name": "stdout",
 361      "output_type": "stream",
 362      "text": [
 363       "[23 [23 [23] [23]] [23] [23 []]]\n"
 364      ]
 365     }
 366    ],
 367    "source": [
 368     "J('[23 [2 [8] [9]] [3] [4 []]] [] [pop 23] [cons] treestep')  # Replace each node."
 369    ]
 370   },
 371   {
 372    "cell_type": "code",
 373    "execution_count": 11,
 374    "metadata": {},
 375    "outputs": [
 376     {
 377      "name": "stdout",
 378      "output_type": "stream",
 379      "text": [
 380       "[1 [1 [1] [1]] [1] [1 []]]\n"
 381      ]
 382     }
 383    ],
 384    "source": [
 385     "J('[23 [2 [8] [9]] [3] [4 []]] [] [pop 1] [cons] treestep')"
 386    ]
 387   },
 388   {
 389    "cell_type": "code",
 390    "execution_count": 12,
 391    "metadata": {},
 392    "outputs": [
 393     {
 394      "name": "stdout",
 395      "output_type": "stream",
 396      "text": [
 397       "6\n"
 398      ]
 399     }
 400    ],
 401    "source": [
 402     "J('[23 [2 [8] [9]] [3] [4 []]] [] [pop 1] [cons] treestep sumtree')"
 403    ]
 404   },
 405   {
 406    "cell_type": "code",
 407    "execution_count": 13,
 408    "metadata": {
 409     "scrolled": false
 410    },
 411    "outputs": [
 412     {
 413      "name": "stdout",
 414      "output_type": "stream",
 415      "text": [
 416       "6\n"
 417      ]
 418     }
 419    ],
 420    "source": [
 421     "J('[23 [2 [8] [9]] [3] [4 []]] [pop 0] [pop 1] [sum +] treestep')  # Combine replace and sum into one function."
 422    ]
 423   },
 424   {
 425    "cell_type": "code",
 426    "execution_count": 14,
 427    "metadata": {
 428     "scrolled": false
 429    },
 430    "outputs": [
 431     {
 432      "name": "stdout",
 433      "output_type": "stream",
 434      "text": [
 435       "3\n"
 436      ]
 437     }
 438    ],
 439    "source": [
 440     "J('[4 [3 [] [7]]] [pop 0] [pop 1] [sum +] treestep')  # Combine replace and sum into one function."
 441    ]
 442   },
 443   {
 444    "cell_type": "markdown",
 445    "metadata": {},
 446    "source": [
 447     "## Redefining the Ordered Binary Tree in terms of `treestep`.\n",
 448     "\n",
 449     "    Tree = [] | [[key value] left right]"
 450    ]
 451   },
 452   {
 453    "cell_type": "markdown",
 454    "metadata": {},
 455    "source": [
 456     "What kind of functions can we write for this with our `treestep`?\n",
 457     "\n",
 458     "The pattern for processing a non-empty node is:\n",
 459     "\n",
 460     "    node N [tree*] [K] map C\n",
 461     "\n",
 462     "Plugging in our BTree structure:\n",
 463     "\n",
 464     "    [key value] N [left right] [K] map C"
 465    ]
 466   },
 467   {
 468    "cell_type": "markdown",
 469    "metadata": {},
 470    "source": [
 471     "### Traversal\n",
 472     "    [key value] first [left right] [K] map i\n",
 473     "    key [value]       [left right] [K] map i\n",
 474     "    key               [left right] [K] map i\n",
 475     "    key               [lkey rkey ]         i\n",
 476     "    key                lkey rkey"
 477    ]
 478   },
 479   {
 480    "cell_type": "markdown",
 481    "metadata": {},
 482    "source": [
 483     "This doesn't quite work:"
 484    ]
 485   },
 486   {
 487    "cell_type": "code",
 488    "execution_count": 15,
 489    "metadata": {},
 490    "outputs": [
 491     {
 492      "name": "stdout",
 493      "output_type": "stream",
 494      "text": [
 495       "3 'B' 'B'\n"
 496      ]
 497     }
 498    ],
 499    "source": [
 500     "J('[[3 0] [[2 0] [][]] [[9 0] [[5 0] [[4 0] [][]] [[8 0] [[6 0] [] [[7 0] [][]]][]]][]]] [\"B\"] [first] [i] treestep')"
 501    ]
 502   },
 503   {
 504    "cell_type": "markdown",
 505    "metadata": {},
 506    "source": [
 507     "Doesn't work because `map` extracts the `first` item of whatever its mapped function produces.  We have to return a list, rather than depositing our results directly on the stack.\n",
 508     "\n",
 509     "\n",
 510     "    [key value] N     [left right] [K] map C\n",
 511     "\n",
 512     "    [key value] first [left right] [K] map flatten cons\n",
 513     "    key               [left right] [K] map flatten cons\n",
 514     "    key               [[lk] [rk] ]         flatten cons\n",
 515     "    key               [ lk   rk  ]                 cons\n",
 516     "                      [key  lk   rk  ]\n",
 517     "\n",
 518     "So:\n",
 519     "\n",
 520     "    [] [first] [flatten cons] treestep"
 521    ]
 522   },
 523   {
 524    "cell_type": "code",
 525    "execution_count": 16,
 526    "metadata": {
 527     "scrolled": true
 528    },
 529    "outputs": [
 530     {
 531      "name": "stdout",
 532      "output_type": "stream",
 533      "text": [
 534       "[3 2 9 5 4 8 6 7]\n"
 535      ]
 536     }
 537    ],
 538    "source": [
 539     "J('[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]]   [] [first] [flatten cons] treestep')"
 540    ]
 541   },
 542   {
 543    "cell_type": "markdown",
 544    "metadata": {},
 545    "source": [
 546     "There we go."
 547    ]
 548   },
 549   {
 550    "cell_type": "markdown",
 551    "metadata": {},
 552    "source": [
 553     "### In-order traversal\n",
 554     "\n",
 555     "From here:\n",
 556     "\n",
 557     "    key [[lk] [rk]] C\n",
 558     "    key [[lk] [rk]] i\n",
 559     "    key  [lk] [rk] roll<\n",
 560     "    [lk] [rk] key swons concat\n",
 561     "    [lk] [key rk]       concat\n",
 562     "    [lk   key rk]\n",
 563     "\n",
 564     "So:\n",
 565     "\n",
 566     "    [] [i roll< swons concat] [first] treestep"
 567    ]
 568   },
 569   {
 570    "cell_type": "code",
 571    "execution_count": 17,
 572    "metadata": {},
 573    "outputs": [
 574     {
 575      "name": "stdout",
 576      "output_type": "stream",
 577      "text": [
 578       "[2 3 4 5 6 7 8 9]\n"
 579      ]
 580     }
 581    ],
 582    "source": [
 583     "J('[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]]   [] [uncons pop] [i roll< swons concat] treestep')"
 584    ]
 585   },
 586   {
 587    "cell_type": "markdown",
 588    "metadata": {},
 589    "source": [
 590     "## With `treegrind`?\n",
 591     "The `treegrind` function doesn't include the `map` combinator, so the `[C]` function must arrange to use some combinator on the quoted recursive copy `[K]`.  With this function, the pattern for processing a non-empty node is:\n",
 592     "\n",
 593     "    node N [tree*] [K] C\n",
 594     "\n",
 595     "Plugging in our BTree structure:\n",
 596     "\n",
 597     "    [key value] N [left right] [K] C"
 598    ]
 599   },
 600   {
 601    "cell_type": "code",
 602    "execution_count": 18,
 603    "metadata": {},
 604    "outputs": [
 605     {
 606      "name": "stdout",
 607      "output_type": "stream",
 608      "text": [
 609       "['key' 'value'] 'N' [['left'] ['right']] [[not] ['B'] [uncons ['N'] dip] ['C'] genrec] 'C'\n"
 610      ]
 611     }
 612    ],
 613    "source": [
 614     "J('[[\"key\" \"value\"] [\"left\"] [\"right\"] ] [\"B\"] [\"N\"] [\"C\"] treegrind')"
 615    ]
 616   },
 617   {
 618    "cell_type": "markdown",
 619    "metadata": {},
 620    "source": [
 621     "## `treegrind` with `step`"
 622    ]
 623   },
 624   {
 625    "cell_type": "markdown",
 626    "metadata": {},
 627    "source": [
 628     "Iteration through the nodes"
 629    ]
 630   },
 631   {
 632    "cell_type": "code",
 633    "execution_count": 19,
 634    "metadata": {},
 635    "outputs": [
 636     {
 637      "name": "stdout",
 638      "output_type": "stream",
 639      "text": [
 640       "[3 0] 'N' [2 0] 'N' [9 0] 'N' [5 0] 'N' [4 0] 'N' [8 0] 'N' [6 0] 'N' [7 0] 'N'\n"
 641      ]
 642     }
 643    ],
 644    "source": [
 645     "J('[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]]   [pop] [\"N\"] [step] treegrind')"
 646    ]
 647   },
 648   {
 649    "cell_type": "markdown",
 650    "metadata": {},
 651    "source": [
 652     "Sum the nodes' keys."
 653    ]
 654   },
 655   {
 656    "cell_type": "code",
 657    "execution_count": 20,
 658    "metadata": {},
 659    "outputs": [
 660     {
 661      "name": "stdout",
 662      "output_type": "stream",
 663      "text": [
 664       "44\n"
 665      ]
 666     }
 667    ],
 668    "source": [
 669     "J('0 [[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]]   [pop] [first +] [step] treegrind')"
 670    ]
 671   },
 672   {
 673    "cell_type": "markdown",
 674    "metadata": {},
 675    "source": [
 676     "Rebuild the tree using `map` (imitating `treestep`.)"
 677    ]
 678   },
 679   {
 680    "cell_type": "code",
 681    "execution_count": 21,
 682    "metadata": {},
 683    "outputs": [
 684     {
 685      "name": "stdout",
 686      "output_type": "stream",
 687      "text": [
 688       "[[103 0] [[102 0] [] []] [[109 0] [[105 0] [[104 0] [] []] [[108 0] [[106 0] [] [[107 0] [] []]] []]] []]]\n"
 689      ]
 690     }
 691    ],
 692    "source": [
 693     "J('[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]]   [] [[100 +] infra] [map cons] treegrind')"
 694    ]
 695   },
 696   {
 697    "cell_type": "markdown",
 698    "metadata": {},
 699    "source": [
 700     "## Do we have the flexibility to reimplement `Tree-get`?\n",
 701     "I think we do:\n",
 702     "\n",
 703     "    [B] [N] [C] treegrind"
 704    ]
 705   },
 706   {
 707    "cell_type": "markdown",
 708    "metadata": {},
 709    "source": [
 710     "We'll start by saying that the base-case (the key is not in the tree) is user defined, and the per-node function is just the query key literal:\n",
 711     "\n",
 712     "    [B] [query_key] [C] treegrind"
 713    ]
 714   },
 715   {
 716    "cell_type": "markdown",
 717    "metadata": {},
 718    "source": [
 719     "This means we just have to define `C` from:\n",
 720     "\n",
 721     "    [key value] query_key [left right] [K] C\n",
 722     " "
 723    ]
 724   },
 725   {
 726    "cell_type": "markdown",
 727    "metadata": {},
 728    "source": [
 729     "Let's try `cmp`:\n",
 730     "\n",
 731     "    C == P [T>] [E] [T<] cmp\n",
 732     "\n",
 733     "    [key value] query_key [left right] [K] P [T>] [E] [T<] cmp"
 734    ]
 735   },
 736   {
 737    "cell_type": "markdown",
 738    "metadata": {},
 739    "source": [
 740     "### The predicate `P`\n",
 741     "Seems pretty easy (we must preserve the value in case the keys are equal):\n",
 742     "\n",
 743     "    [key value] query_key [left right] [K] P\n",
 744     "    [key value] query_key [left right] [K] roll<\n",
 745     "    [key value] [left right] [K] query_key       [roll< uncons swap] dip\n",
 746     "\n",
 747     "    [key value] [left right] [K] roll< uncons swap query_key\n",
 748     "    [left right] [K] [key value]       uncons swap query_key\n",
 749     "    [left right] [K] key [value]              swap query_key\n",
 750     "    [left right] [K] [value] key                   query_key\n",
 751     "\n",
 752     "    P == roll< [roll< uncons swap] dip\n",
 753     "\n",
 754     "(Possibly with a swap at the end?  Or just swap `T<` and `T>`.)"
 755    ]
 756   },
 757   {
 758    "cell_type": "markdown",
 759    "metadata": {},
 760    "source": [
 761     "So now:\n",
 762     "\n",
 763     "    [left right] [K] [value] key query_key [T>] [E] [T<] cmp\n",
 764     "\n",
 765     "Becomes one of these three:\n",
 766     "\n",
 767     "    [left right] [K] [value] T>\n",
 768     "    [left right] [K] [value] E\n",
 769     "    [left right] [K] [value] T<\n"
 770    ]
 771   },
 772   {
 773    "cell_type": "markdown",
 774    "metadata": {},
 775    "source": [
 776     "### `E`\n",
 777     "Easy.\n",
 778     "\n",
 779     "    E == roll> popop first"
 780    ]
 781   },
 782   {
 783    "cell_type": "markdown",
 784    "metadata": {},
 785    "source": [
 786     "### `T<` and `T>`\n",
 787     "\n",
 788     "    T< == pop [first] dip i\n",
 789     "    T> == pop [second] dip i"
 790    ]
 791   },
 792   {
 793    "cell_type": "markdown",
 794    "metadata": {},
 795    "source": [
 796     "## Putting it together\n",
 797     "\n",
 798     "\n",
 799     "    T> == pop [first] dip i\n",
 800     "    T< == pop [second] dip i\n",
 801     "    E == roll> popop first\n",
 802     "    P == roll< [roll< uncons swap] dip\n",
 803     "    \n",
 804     "    Tree-get == [P [T>] [E] [T<] cmp] treegrind\n",
 805     "\n",
 806     "To me, that seems simpler than the `genrec` version."
 807    ]
 808   },
 809   {
 810    "cell_type": "code",
 811    "execution_count": 22,
 812    "metadata": {},
 813    "outputs": [],
 814    "source": [
 815     "DefinitionWrapper.add_definitions('''\n",
 816     "\n",
 817     "    T> == pop [first] dip i\n",
 818     "    T< == pop [second] dip i\n",
 819     "    E == roll> popop first\n",
 820     "    P == roll< [roll< uncons swap] dip\n",
 821     "\n",
 822     "    Tree-get == [P [T>] [E] [T<] cmp] treegrind\n",
 823     "\n",
 824     "''', D)"
 825    ]
 826   },
 827   {
 828    "cell_type": "code",
 829    "execution_count": 23,
 830    "metadata": {},
 831    "outputs": [
 832     {
 833      "name": "stdout",
 834      "output_type": "stream",
 835      "text": [
 836       "15\n"
 837      ]
 838     }
 839    ],
 840    "source": [
 841     "J('''\\\n",
 842     "\n",
 843     "[[3 13] [[2 12] [] []] [[9 19] [[5 15] [[4 14] [] []] [[8 18] [[6 16] [] [[7 17] [] []]] []]] []]]\n",
 844     "\n",
 845     "[] [5] Tree-get\n",
 846     "\n",
 847     "''')"
 848    ]
 849   },
 850   {
 851    "cell_type": "code",
 852    "execution_count": 24,
 853    "metadata": {},
 854    "outputs": [
 855     {
 856      "name": "stdout",
 857      "output_type": "stream",
 858      "text": [
 859       "'nope'\n"
 860      ]
 861     }
 862    ],
 863    "source": [
 864     "J('''\\\n",
 865     "\n",
 866     "[[3 13] [[2 12] [] []] [[9 19] [[5 15] [[4 14] [] []] [[8 18] [[6 16] [] [[7 17] [] []]] []]] []]]\n",
 867     "\n",
 868     "[pop \"nope\"] [25] Tree-get\n",
 869     "\n",
 870     "''')"
 871    ]
 872   }
 873  ],
 874  "metadata": {
 875   "kernelspec": {
 876    "display_name": "Python 2",
 877    "language": "python",
 878    "name": "python2"
 879   },
 880   "language_info": {
 881    "codemirror_mode": {
 882     "name": "ipython",
 883     "version": 2
 884    },
 885    "file_extension": ".py",
 886    "mimetype": "text/x-python",
 887    "name": "python",
 888    "nbconvert_exporter": "python",
 889    "pygments_lexer": "ipython2",
 890    "version": "2.7.12"
 891   }
 892  },
 893  "nbformat": 4,
 894  "nbformat_minor": 2
 895 }