docs/Ordered_Binary_Trees.md

   1 # Treating Trees I: Ordered Binary Trees
   2
   3 Although any expression in Joy can be considered to describe a [tree](https://en.wikipedia.org/wiki/Tree_structure) with the quotes as compound nodes and the non-quote values as leaf nodes, in this page I want to talk about [ordered binary trees](https://en.wikipedia.org/wiki/Binary_search_tree) and how to make and use them.
   4
   5 The basic structure, in a [crude type notation](https://en.wikipedia.org/wiki/Algebraic_data_type), is:
   6
   7     Tree :: [] | [key value Tree Tree]
   8
   9 That says that a Tree is either the empty quote `[]` or a quote with four items: a key, a value, and two Trees representing the left and right branches of the tree.
  10
  11 We're going to derive some recursive functions to work with such datastructures:
  12
  13     Tree-add
  14     Tree-delete
  15     Tree-get
  16     Tree-iter
  17     Tree-iter-order
  18
  19 Once these functions are defined we have a new "type" to work with, and the Sufficiently Smart Compiler can be modified to use an optimized implementation under the hood.  (Where does the "type" come from?  It has a contingent existence predicated on the disciplined use of these functions on otherwise undistinguished Joy datastructures.)
  20
  21
  22 ```python
  23 from notebook_preamble import D, J, V, define, DefinitionWrapper
  24 ```
  25
  26 ## Adding Nodes to the Tree
  27 Let's consider adding nodes to a Tree structure.
  28
  29        Tree value key Tree-add
  30     -----------------------------
  31                 Tree′
  32
  33 ### Adding to an empty node.
  34 If the current node is `[]` then you just return `[key value [] []]`:
  35
  36     Tree-add == [popop not] [[pop] dipd Tree-new] [R0] [R1] genrec
  37
  38 #### `Tree-new`
  39 Where `Tree-new` is defined as:
  40
  41        value key Tree-new
  42     ------------------------
  43        [key value [] []]
  44
  45 Example:
  46
  47     value key swap [[] []] cons cons
  48     key value      [[] []] cons cons
  49     key      [value [] []]      cons
  50          [key value [] []]
  51
  52 Definition:
  53
  54     Tree-new == swap [[] []] cons cons
  55
  56
  57 ```python
  58 define('Tree-new == swap [[] []] cons cons')
  59 ```
  60
  61
  62 ```python
  63 J('"v" "k" Tree-new')
  64 ```
  65
  66     ['k' 'v' [] []]
  67
  68
  69 (As an implementation detail, the `[[] []]` literal used in the definition of `Tree-new` will be reused to supply the *constant* tail for *all* new nodes produced by it.  This is one of those cases where you get amortized storage "for free" by using [persistent datastructures](https://en.wikipedia.org/wiki/Persistent_data_structure).  Because the tail, which is `((), ((), ()))` in Python, is immutable and embedded in the definition body for `Tree-new`, all new nodes can reuse it as their own tail without fear that some other code somewhere will change it.)
  70
  71 ### Adding to a non-empty node.
  72
  73 We now have to derive `R0` and `R1`, consider:
  74
  75     [key_n value_n left right] value key R0 [Tree-add] R1
  76
  77 In this case, there are three possibilites: the key can be greater or less than or equal to the node's key.  In two of those cases we will need to apply a copy of `Tree-add`, so `R0` is pretty much out of the picture.
  78
  79     [R0] == []
  80
  81 #### A predicate to compare keys.
  82
  83     [key_n value_n left right] value key [BTree-add] R1
  84
  85 The first thing we need to do is compare the the key we're adding to the node key and `branch` accordingly:
  86
  87     [key_n value_n left right] value key [BTree-add] [P] [T] [E] ifte
  88
  89 That would suggest something like:
  90
  91     [key_n value_n left right] value key [BTree-add] P
  92     [key_n value_n left right] value key [BTree-add] pop roll> pop first >
  93     [key_n value_n left right] value key                 roll> pop first >
  94     key [key_n value_n left right] value                 roll> pop first >
  95     key key_n                                                            >
  96     Boolean
  97
  98 Let's abstract the predicate just a little to let us specify the comparison operator:
  99
 100     P > == pop roll> pop first >
 101     P < == pop roll> pop first <
 102     P   == pop roll> pop first
 103
 104
 105 ```python
 106 define('P == pop roll> pop first')
 107 ```
 108
 109
 110 ```python
 111 J('["old_key" 23 [] []] 17 "new_key" ["..."] P')
 112 ```
 113
 114     'new_key' 'old_key'
 115
 116
 117 #### If the key we're adding is greater than the node's key.
 118
 119 Here the parentheses are meant to signify that the expression is not literal, the code in the parentheses is meant to have been evaluated:
 120
 121        [key_n value_n left right] value key [Tree-add] T
 122     -------------------------------------------------------
 123        [key_n value_n left (Tree-add key value right)]
 124
 125 So how do we do this?  We're going to want to use `infra` on some function `K` that has the key and value to work with, as well as the quoted copy of `Tree-add` to apply somehow.  Considering the node as a stack:
 126
 127        right left value_n key_n value key [Tree-add] K
 128     -----------------------------------------------------
 129        right value key Tree-add left value_n key_n
 130
 131 Pretty easy:
 132
 133     right left value_n key_n value key [Tree-add] cons cons dipdd
 134     right left value_n key_n [value key Tree-add]           dipdd
 135     right value key Tree-add left value_n key_n
 136
 137 So:
 138
 139     K == cons cons dipdd
 140
 141 Looking at it from the point-of-view of the node as node again:
 142
 143     [key_n value_n left right] [value key [Tree-add] K] infra
 144
 145 Expand `K` and evaluate a little:
 146
 147     [key_n value_n left right] [value key [Tree-add] K] infra
 148     [key_n value_n left right] [value key [Tree-add] cons cons dipdd] infra
 149     [key_n value_n left right] [[value key Tree-add]           dipdd] infra
 150
 151 Then, working backwards:
 152
 153     [key_n value_n left right] [[value key Tree-add]           dipdd]      infra
 154     [key_n value_n left right] [value key Tree-add]           [dipdd] cons infra
 155     [key_n value_n left right] value key [Tree-add] cons cons [dipdd] cons infra
 156
 157
 158 And so `T` is just:
 159
 160     T == cons cons [dipdd] cons infra
 161
 162
 163 ```python
 164 define('T == cons cons [dipdd] cons infra')
 165 ```
 166
 167
 168 ```python
 169 J('["old_k" "old_value" "left" "right"] "new_value" "new_key" ["Tree-add"] T')
 170 ```
 171
 172     ['old_k' 'old_value' 'left' 'Tree-add' 'new_key' 'new_value' 'right']
 173
 174
 175 #### If the key we're adding is less than the node's key.
 176 This is very very similar to the above:
 177
 178     [key_n value_n left right] value key [Tree-add] E
 179     [key_n value_n left right] value key [Tree-add] [P <] [Te] [Ee] ifte
 180
 181
 182 ```python
 183 define('E == [P <] [Te] [Ee] ifte')
 184 ```
 185
 186 In this case `Te` works that same as `T` but on the left child tree instead of the right, so the only difference is that it must use `dipd` instead of `dipdd`:
 187
 188     Te == cons cons [dipd] cons infra
 189
 190
 191 ```python
 192 define('Te == cons cons [dipd] cons infra')
 193 ```
 194
 195
 196 ```python
 197 J('["old_k" "old_value" "left" "right"] "new_value" "new_key" ["Tree-add"] Te')
 198 ```
 199
 200     ['old_k' 'old_value' 'Tree-add' 'new_key' 'new_value' 'left' 'right']
 201
 202
 203 #### Else the keys must be equal.
 204 This means we must find:
 205
 206        [key old_value left right] new_value key [Tree-add] Ee
 207     ------------------------------------------------------------
 208        [key new_value left right]
 209
 210 This is another easy one:
 211
 212     Ee == pop swap roll< rest rest cons cons
 213
 214 Example:
 215
 216     [key old_value left right] new_value key [Tree-add] pop swap roll< rest rest cons cons
 217     [key old_value left right] new_value key                swap roll< rest rest cons cons
 218     [key old_value left right] key new_value                     roll< rest rest cons cons
 219     key new_value [key old_value left right]                           rest rest cons cons
 220     key new_value [              left right]                                     cons cons
 221                   [key new_value left right]
 222
 223
 224 ```python
 225 define('Ee == pop swap roll< rest rest cons cons')
 226 ```
 227
 228
 229 ```python
 230 J('["k" "old_value" "left" "right"] "new_value" "k" ["Tree-add"] Ee')
 231 ```
 232
 233     ['k' 'new_value' 'left' 'right']
 234
 235
 236 ### Now we can define `Tree-add`
 237     Tree-add == [popop not] [[pop] dipd Tree-new] [] [[P >] [T] [E] ifte] genrec
 238
 239 Putting it all together:
 240
 241     Tree-new == swap [[] []] cons cons
 242     P == pop roll> pop first
 243     T == cons cons [dipdd] cons infra
 244     Te == cons cons [dipd] cons infra
 245     Ee == pop swap roll< rest rest cons cons
 246     E == [P <] [Te] [Ee] ifte
 247     R == [P >] [T] [E] ifte
 248
 249     Tree-add == [popop not] [[pop] dipd Tree-new] [] [R] genrec
 250
 251
 252 ```python
 253 define('Tree-add == [popop not] [[pop] dipd Tree-new] [] [[P >] [T] [E] ifte] genrec')
 254 ```
 255
 256 ### Examples
 257
 258
 259 ```python
 260 J('[] 23 "b" Tree-add')  # Initial
 261 ```
 262
 263     ['b' 23 [] []]
 264
 265
 266
 267 ```python
 268 J('["b" 23 [] []] 88 "c" Tree-add')  # Greater than
 269 ```
 270
 271     ['b' 23 [] ['c' 88 [] []]]
 272
 273
 274
 275 ```python
 276 J('["b" 23 [] []] 88 "a" Tree-add')  # Less than
 277 ```
 278
 279     ['b' 23 ['a' 88 [] []] []]
 280
 281
 282
 283 ```python
 284 J('["b" 23 [] []] 88 "b" Tree-add')  # Equal to
 285 ```
 286
 287     ['b' 88 [] []]
 288
 289
 290
 291 ```python
 292 J('[] 23 "b" Tree-add 88 "a" Tree-add 44 "c" Tree-add')  # Series.
 293 ```
 294
 295     ['b' 23 ['a' 88 [] []] ['c' 44 [] []]]
 296
 297
 298
 299 ```python
 300 J('[] [[23 "b"] [88 "a"] [44 "c"]] [i Tree-add] step')
 301 ```
 302
 303     ['b' 23 ['a' 88 [] []] ['c' 44 [] []]]
 304
 305
 306 ## Interlude: `cmp` combinator
 307 Instead of mucking about with nested `ifte` combinators let's use `cmp` which takes two values and three quoted programs on the stack and runs one of the three depending on the results of comparing the two values:
 308
 309        a b [G] [E] [L] cmp
 310     ------------------------- a > b
 311             G
 312
 313        a b [G] [E] [L] cmp
 314     ------------------------- a = b
 315                 E
 316
 317        a b [G] [E] [L] cmp
 318     ------------------------- a < b
 319                     L
 320
 321
 322 ```python
 323 J("1 0 ['G'] ['E'] ['L'] cmp")
 324 ```
 325
 326     'G'
 327
 328
 329
 330 ```python
 331 J("1 1 ['G'] ['E'] ['L'] cmp")
 332 ```
 333
 334     'E'
 335
 336
 337
 338 ```python
 339 J("0 1 ['G'] ['E'] ['L'] cmp")
 340 ```
 341
 342     'L'
 343
 344
 345 ### Redefine `Tree-add`
 346 We need a new non-destructive predicate `P`:
 347
 348        [node_key node_value left right] value key [Tree-add] P
 349     ------------------------------------------------------------------------
 350        [node_key node_value left right] value key [Tree-add] key node_key
 351
 352 Let's start with `over` to get a copy of the key and then apply some function `Q` with the `nullary` combinator so it can dig out the node key (by throwing everything else away):
 353
 354     P == over [Q] nullary
 355
 356     [node_key node_value left right] value key [Tree-add] over [Q] nullary
 357     [node_key node_value left right] value key [Tree-add] key  [Q] nullary
 358
 359 And `Q` would be:
 360
 361     Q == popop popop first
 362
 363     [node_key node_value left right] value key [Tree-add] key Q
 364     [node_key node_value left right] value key [Tree-add] key popop popop first
 365     [node_key node_value left right] value key                      popop first
 366     [node_key node_value left right]                                      first
 367      node_key
 368
 369 Or just:
 370
 371     P == over [popop popop first] nullary
 372
 373
 374 ```python
 375 define('P == over [popop popop first] nullary')
 376 ```
 377
 378 Using `cmp` to simplify [our code above at `R1`](#Adding-to-a-non-empty-node.):
 379
 380     [node_key node_value left right] value key [Tree-add] R1
 381     [node_key node_value left right] value key [Tree-add] P [T] [E] [Te] cmp
 382
 383 The line above becomes one of the three lines below:
 384
 385     [node_key node_value left right] value key [Tree-add] T
 386     [node_key node_value left right] value key [Tree-add] E
 387     [node_key node_value left right] value key [Tree-add] Te
 388
 389 The definition is a little longer but, I think, more elegant and easier to understand:
 390
 391     Tree-add == [popop not] [[pop] dipd Tree-new] [] [P [T] [Ee] [Te] cmp] genrec
 392
 393
 394 ```python
 395 define('Tree-add == [popop not] [[pop] dipd Tree-new] [] [P [T] [Ee] [Te] cmp] genrec')
 396 ```
 397
 398
 399 ```python
 400 J('[] 23 "b" Tree-add 88 "a" Tree-add 44 "c" Tree-add')  # Still works.
 401 ```
 402
 403     ['b' 23 ['a' 88 [] []] ['c' 44 [] []]]
 404
 405
 406 ## A Function to Traverse this Structure
 407 Let's take a crack at writing a function that can recursively iterate or traverse these trees.
 408
 409 ### Base case `[]`
 410 The stopping predicate just has to detect the empty list:
 411
 412     Tree-iter == [not] [E] [R0] [R1] genrec
 413
 414 And since there's nothing at this node, we just `pop` it:
 415
 416     Tree-iter == [not] [pop] [R0] [R1] genrec
 417
 418 ### Node case `[key value left right]`
 419 Now we need to figure out `R0` and `R1`:
 420
 421     Tree-iter == [not] [pop] [R0]           [R1] genrec
 422               == [not] [pop] [R0 [Tree-iter] R1] ifte
 423
 424 Let's look at it *in situ*:
 425
 426     [key value left right] R0 [Tree-iter] R1
 427
 428 #### Processing the current node.
 429
 430 `R0` is almost certainly going to use `dup` to make a copy of the node and then `dip` on some function to process the copy with it:
 431
 432     [key value left right] [F] dupdip                 [Tree-iter] R1
 433     [key value left right]  F  [key value left right] [Tree-iter] R1
 434
 435 For example, if we're getting all the keys `F` would be `first`:
 436
 437     R0 == [first] dupdip
 438
 439     [key value left right] [first] dupdip                 [Tree-iter] R1
 440     [key value left right]  first  [key value left right] [Tree-iter] R1
 441     key                            [key value left right] [Tree-iter] R1
 442
 443 #### Recur
 444 Now `R1` needs to apply `[Tree-iter]` to `left` and `right`.  If we drop the key and value from the node using `rest` twice we are left with an interesting situation:
 445
 446     key [key value left right] [Tree-iter] R1
 447     key [key value left right] [Tree-iter] [rest rest] dip
 448     key [key value left right] rest rest [Tree-iter]
 449     key [left right] [Tree-iter]
 450
 451 Hmm, will `step` do?
 452
 453     key [left right] [Tree-iter] step
 454     key left Tree-iter [right] [Tree-iter] step
 455     key left-keys [right] [Tree-iter] step
 456     key left-keys right Tree-iter
 457     key left-keys right-keys
 458
 459 Neat. So:
 460
 461     R1 == [rest rest] dip step
 462
 463 ### Putting it together
 464 We have:
 465
 466     Tree-iter == [not] [pop] [[F] dupdip] [[rest rest] dip step] genrec
 467
 468 When I was reading this over I realized `rest rest` could go in `R0`:
 469
 470     Tree-iter == [not] [pop] [[F] dupdip rest rest] [step] genrec
 471
 472 (And `[step] genrec` is such a cool and suggestive combinator!)
 473
 474 ### Parameterizing the `F` per-node processing function.
 475
 476                     [F] Tree-iter
 477     ------------------------------------------------------
 478        [not] [pop] [[F] dupdip rest rest] [step] genrec
 479
 480 Working backward:
 481
 482     [not] [pop] [[F] dupdip rest rest]            [step] genrec
 483     [not] [pop] [F]       [dupdip rest rest] cons [step] genrec
 484     [F] [not] [pop] roll< [dupdip rest rest] cons [step] genrec
 485
 486 ### `Tree-iter`
 487
 488     Tree-iter == [not] [pop] roll< [dupdip rest rest] cons [step] genrec
 489
 490
 491 ```python
 492 define('Tree-iter == [not] [pop] roll< [dupdip rest rest] cons [step] genrec')
 493 ```
 494
 495 ### Examples
 496
 497
 498 ```python
 499 J('[] [foo] Tree-iter')  #  It doesn't matter what F is as it won't be used.
 500 ```
 501
 502
 503
 504
 505
 506 ```python
 507 J("['b' 23 ['a' 88 [] []] ['c' 44 [] []]] [first] Tree-iter")
 508 ```
 509
 510     'b' 'a' 'c'
 511
 512
 513
 514 ```python
 515 J("['b' 23 ['a' 88 [] []] ['c' 44 [] []]] [second] Tree-iter")
 516 ```
 517
 518     23 88 44
 519
 520
 521 ## Interlude: A Set-like Datastructure
 522 We can use this to make a set-like datastructure by just setting values to e.g. 0 and ignoring them.  It's set-like in that duplicate items added to it will only occur once within it, and we can query it in [$O(\log_2 N)$](https://en.wikipedia.org/wiki/Binary_search_tree#cite_note-2) time.
 523
 524
 525 ```python
 526 J('[] [3 9 5 2 8 6 7 8 4] [0 swap Tree-add] step')
 527 ```
 528
 529     [3 0 [2 0 [] []] [9 0 [5 0 [4 0 [] []] [8 0 [6 0 [] [7 0 [] []]] []]] []]]
 530
 531
 532
 533 ```python
 534 define('to_set == [] swap [0 swap Tree-add] step')
 535 ```
 536
 537
 538 ```python
 539 J('[3 9 5 2 8 6 7 8 4] to_set')
 540 ```
 541
 542     [3 0 [2 0 [] []] [9 0 [5 0 [4 0 [] []] [8 0 [6 0 [] [7 0 [] []]] []]] []]]
 543
 544
 545 And with that we can write a little program `unique` to remove duplicate items from a list.
 546
 547
 548 ```python
 549 define('unique == [to_set [first] Tree-iter] cons run')
 550 ```
 551
 552
 553 ```python
 554 J('[3 9 3 5 2 9 8 8 8 6 2 7 8 4 3] unique')  # Filter duplicate items.
 555 ```
 556
 557     [7 6 8 4 5 9 2 3]
 558
 559
 560 ## A Version of `Tree-iter` that does In-Order Traversal
 561
 562 If you look back to the [non-empty case of the `Tree-iter` function](#Node-case-[key-value-left-right]) we can design a variant that first processes the left child, then the current node, then the right child.  This will allow us to traverse the tree in sort order.
 563
 564     Tree-iter-order == [not] [pop] [R0] [R1] genrec
 565
 566 To define `R0` and `R1` it helps to look at them as they will appear when they run:
 567
 568     [key value left right] R0 [BTree-iter-order] R1
 569
 570 ### Process the left child.
 571 Staring at this for a bit suggests `dup third` to start:
 572
 573     [key value left right] R0        [Tree-iter-order] R1
 574     [key value left right] dup third [Tree-iter-order] R1
 575     [key value left right] left      [Tree-iter-order] R1
 576
 577 Now maybe:
 578
 579     [key value left right] left [Tree-iter-order] [cons dip] dupdip
 580     [key value left right] left [Tree-iter-order]  cons dip [Tree-iter-order]
 581     [key value left right] [left Tree-iter-order]       dip [Tree-iter-order]
 582     left Tree-iter-order [key value left right]             [Tree-iter-order]
 583
 584 ### Process the current node.
 585 So far, so good.  Now we need to process the current node's values:
 586
 587     left Tree-iter-order [key value left right] [Tree-iter-order] [[F] dupdip] dip
 588     left Tree-iter-order [key value left right] [F] dupdip [Tree-iter-order]
 589     left Tree-iter-order [key value left right] F [key value left right] [Tree-iter-order]
 590
 591 If `F` needs items from the stack below the left stuff it should have `cons`'d them before beginning maybe?  For functions like `first` it works fine as-is.
 592
 593     left Tree-iter-order [key value left right] first [key value left right] [Tree-iter-order]
 594     left Tree-iter-order key [key value left right] [Tree-iter-order]
 595
 596 ### Process the right child.
 597 First ditch the rest of the node and get the right child:
 598
 599     left Tree-iter-order key [key value left right] [Tree-iter-order] [rest rest rest first] dip
 600     left Tree-iter-order key right [Tree-iter-order]
 601
 602 Then, of course, we just need `i` to run `Tree-iter-order` on the right side:
 603
 604     left Tree-iter-order key right [Tree-iter-order] i
 605     left Tree-iter-order key right Tree-iter-order
 606
 607 ### Defining `Tree-iter-order`
 608 The result is a little awkward:
 609
 610     R1 == [cons dip] dupdip [[F] dupdip] dip [rest rest rest first] dip i
 611
 612 Let's do a little semantic factoring:
 613
 614     fourth == rest rest rest first
 615
 616     proc_left == [cons dip] dupdip
 617     proc_current == [[F] dupdip] dip
 618     proc_right == [fourth] dip i
 619
 620     Tree-iter-order == [not] [pop] [dup third] [proc_left proc_current proc_right] genrec
 621
 622 Now we can sort sequences.
 623
 624
 625 ```python
 626 #define('Tree-iter-order == [not] [pop] [dup third] [[cons dip] dupdip [[first] dupdip] dip [rest rest rest first] dip i] genrec')
 627
 628
 629 DefinitionWrapper.add_definitions('''
 630
 631 fourth == rest rest rest first
 632
 633 proc_left == [cons dip] dupdip
 634 proc_current == [[first] dupdip] dip
 635 proc_right == [fourth] dip i
 636
 637 Tree-iter-order == [not] [pop] [dup third] [proc_left proc_current proc_right] genrec
 638
 639 ''', D)
 640
 641
 642
 643 ```
 644
 645
 646 ```python
 647 J('[3 9 5 2 8 6 7 8 4] to_set Tree-iter-order')
 648 ```
 649
 650     2 3 4 5 6 7 8 9
 651
 652
 653 Parameterizing the `[F]` function is left as an exercise for the reader.
 654
 655 ## Getting values by key
 656 Let's derive a function that accepts a tree and a key and returns the value associated with that key.
 657
 658        tree key Tree-get
 659     -----------------------
 660             value
 661
 662 But what do we do if the key isn't in the tree?  In Python we might raise a `KeyError` but I'd like to avoid exceptions in Joy if possible, and here I think it's possible.  (Division by zero is an example of where I think it's probably better to let Python crash Joy.  Sometimes the machinery fails and you have to "stop the line", I think.)
 663
 664 Let's pass the buck to the caller by making the base case a given, you have to decide for yourself what `[E]` should be.
 665
 666
 667        tree key [E] Tree-get
 668     ---------------------------- key in tree
 669                value
 670
 671        tree key [E] Tree-get
 672     ---------------------------- key not in tree
 673              [] key E
 674
 675 ### The base case `[]`
 676 As before, the stopping predicate just has to detect the empty list:
 677
 678     Tree-get == [pop not] [E] [R0] [R1] genrec
 679
 680 So we define:
 681
 682     Tree-get == [pop not] swap [R0] [R1] genrec
 683
 684 Note that this `Tree-get` creates a slightly different function than itself and *that function* does the actual recursion.  This kind of higher-level programming is unusual in most languages but natural in Joy.
 685
 686     tree key [E] [pop not] swap [R0] [R1] genrec
 687     tree key [pop not] [E] [R0] [R1] genrec
 688
 689 The anonymous specialized recursive function that will do the real work.
 690
 691     [pop not] [E] [R0] [R1] genrec
 692
 693 ### Node case `[key value left right]`
 694 Now we need to figure out `R0` and `R1`:
 695
 696     [key value left right] key R0 [BTree-get] R1
 697
 698 We want to compare the search key with the key in the node, and if they are the same return the value, otherwise recur on one of the child nodes.  So it's very similar to the above funtion, with `[R0] == []` and `R1 == P [T>] [E] [T<] cmp`:
 699
 700     [key value left right] key [BTree-get] P [T>] [E] [T<] cmp
 701
 702 #### Predicate
 703
 704     P == over [get-node-key] nullary
 705     get-node-key == pop popop first
 706
 707 The only difference is that `get-node-key` does one less `pop` because there's no value to discard.
 708
 709 #### Branches
 710 Now we have to derive the branches:
 711
 712     [key_n value_n left right] key [BTree-get] T>
 713     [key_n value_n left right] key [BTree-get] E
 714     [key_n value_n left right] key [BTree-get] T<
 715
 716 #### Greater than and less than
 717 The cases of `T>` and `T<` are similar to above but instead of using `infra` we have to discard the rest of the structure:
 718
 719        [key_n value_n left right] key [BTree-get] T>
 720     ---------------------------------------------------
 721                            right  key  BTree-get
 722
 723 And:
 724
 725        [key_n value_n left right] key [BTree-get] T<
 726     ---------------------------------------------------
 727                       left        key  BTree-get
 728
 729 So:
 730
 731     T> == [fourth] dipd i
 732     T< == [third] dipd i
 733
 734 E.g.:
 735
 736     [key_n value_n left right]        key [BTree-get] [fourth] dipd i
 737     [key_n value_n left right] fourth key [BTree-get]               i
 738                         right         key [BTree-get]               i
 739                         right         key  BTree-get
 740
 741 #### Equal keys
 742 Return the node's value:
 743
 744     [key_n value_n left right] key [BTree-get] E == value_n
 745
 746     E == popop second
 747
 748 ### `Tree-get`
 749 So:
 750
 751     fourth == rest rest rest first
 752     get-node-key == pop popop first
 753     P == over [get-node-key] nullary
 754     T> == [fourth] dipd i
 755     T< == [third] dipd i
 756     E == popop second
 757
 758     Tree-get == [pop not] swap [] [P [T>] [E] [T<] cmp] genrec
 759
 760
 761 ```python
 762 # I don't want to deal with name conflicts with the above so I'm inlining everything here.
 763 # The original Joy system has "hide" which is a meta-command which allows you to use named
 764 # definitions that are only in scope for a given definition.  I don't want to implement
 765 # that (yet) so...
 766
 767
 768 define('''
 769 Tree-get == [pop not] swap [] [
 770   over [pop popop first] nullary
 771   [[fourth] dipd i]
 772   [popop second]
 773   [[third] dipd i]
 774   cmp
 775   ] genrec
 776 ''')
 777 ```
 778
 779
 780 ```python
 781 J('["gary" 23 [] []] "mike" [popd " not in tree" +] Tree-get')
 782 ```
 783
 784     'mike not in tree'
 785
 786
 787
 788 ```python
 789 J('["gary" 23 [] []] "gary" [popop "err"] Tree-get')
 790 ```
 791
 792     23
 793
 794
 795
 796 ```python
 797 J('''
 798
 799     [] [[0 'a'] [1 'b'] [2 'c']] [i Tree-add] step
 800
 801     'c' [popop 'not found'] Tree-get
 802
 803 ''')
 804 ```
 805
 806     2
 807
 808
 809
 810 ```python
 811 J('''
 812
 813     [] [[0 'a'] [1 'b'] [2 'c']] [i Tree-add] step
 814
 815     'd' [popop 'not found'] Tree-get
 816
 817 ''')
 818 ```
 819
 820     'not found'
 821
 822
 823 ## Tree-delete
 824
 825 Now let's write a function that can return a tree datastructure with a key, value pair deleted:
 826
 827        tree key Tree-delete
 828     ---------------------------
 829               tree
 830
 831 If the key is not in tree it just returns the tree unchanged.
 832
 833 ### Base case
 834 Same as above.
 835
 836     Tree-Delete == [pop not] [pop] [R0] [R1] genrec
 837
 838 ### Recur
 839 Now we get to figure out the recursive case.  We need the node's key to compare and we need to carry the key into recursive branches.  Let `D` be shorthand for `Tree-Delete`:
 840
 841     D == Tree-Delete == [pop not] [pop] [R0] [R1] genrec
 842
 843     [node_key node_value left right] key R0                   [D] R1
 844     [node_key node_value left right] key over  first swap dup [D] cons R1′
 845     [node_key node_value left right] key [...] first swap dup [D] cons R1′
 846     [node_key node_value left right] key node_key    swap dup [D] cons R1′
 847     [node_key node_value left right] node_key key         dup [D] cons R1′
 848     [node_key node_value left right] node_key key key         [D] cons R1′
 849     [node_key node_value left right] node_key key         [key D]      R1′
 850
 851 And then:
 852
 853     [node_key node_value left right] node_key key [key D] R1′
 854     [node_key node_value left right] node_key key [key D] roll> [T>] [E] [T<] cmp
 855     [node_key node_value left right] node_key key [key D] roll> [T>] [E] [T<] cmp
 856     [node_key node_value left right] [key D] node_key key       [T>] [E] [T<] cmp
 857
 858 So:
 859
 860     R0 == over first swap dup
 861     R1 == cons roll> [T>] [E] [T<] cmp
 862
 863 ### Compare Keys
 864 The last line above:
 865
 866     [node_key node_value left right] [key D] node_key key [T>] [E] [T<] cmp
 867
 868 Then becomes one of these three:
 869
 870     [node_key node_value left right] [key D] T>
 871     [node_key node_value left right] [key D] E
 872     [node_key node_value left right] [key D] T<
 873
 874 ### Greater than case and less than case
 875
 876        [node_key node_value left right] [F] T>
 877     -------------------------------------------------
 878        [node_key node_value (left F) right]
 879
 880
 881        [node_key node_value left right] [F] T<
 882     -------------------------------------------------
 883        [node_key node_value left (right F)]
 884
 885 First, treating the node as a stack:
 886
 887     right left       node_value node_key [key D] dipd
 888     right left key D node_value node_key
 889     right left'      node_value node_key
 890
 891 Ergo:
 892
 893     [node_key node_value left right] [key D] [dipd] cons infra
 894
 895 So:
 896
 897     T> == [dipd] cons infra
 898     T< == [dipdd] cons infra
 899
 900 ### The else case
 901 We have found the node in the tree where `key` equals `node_key`.  We need to replace the current node with something
 902
 903        [node_key node_value left right] [key D] E
 904     ------------------------------------------------
 905                         tree
 906
 907 We have to handle three cases, so let's use `cond`.
 908
 909 #### One or more child nodes are `[]`
 910 The first two cases are symmetrical: if we only have one non-empty child node return it.  If both child nodes are empty return an empty node.
 911
 912     E == [
 913         [[pop third not] pop fourth]
 914         [[pop fourth not] pop third]
 915         [default]
 916     ] cond
 917
 918 #### Both child nodes are non-empty.
 919 If both child nodes are non-empty, we find the highest node in our lower sub-tree, take its key and value to replace (delete) our own, then get rid of it by recursively calling delete() on our lower sub-node with our new key.
 920
 921 (We could also find the lowest node in our higher sub-tree and take its key and value and delete it. I only implemented one of these two symmetrical options. Over a lot of deletions this might make the tree more unbalanced.  Oh well.)
 922
 923 The initial structure of the default function:
 924
 925     default == [E′] cons infra
 926
 927     [node_key node_value left right] [key D] default
 928     [node_key node_value left right] [key D] [E′] cons infra
 929     [node_key node_value left right] [[key D] E′]      infra
 930
 931     right left node_value node_key [key D] E′
 932
 933 First things first, we no longer need this node's key and value:
 934
 935     right left node_value node_key [key D] roll> popop E″
 936     right left [key D] node_value node_key       popop E″
 937     right left [key D]                                 E″
 938
 939 #### We have to we find the highest (right-most) node in our lower (left) sub-tree:
 940
 941     right left [key D] E″
 942
 943 Ditch the key:
 944
 945     right left [key D] rest E‴
 946     right left     [D]      E‴
 947
 948 Find the right-most node:
 949
 950     right left        [D] [dup W] dip E⁗
 951     right left dup  W [D]             E⁗
 952     right left left W [D]             E⁗
 953
 954 Consider:
 955
 956     left W
 957
 958 We know left is not empty:
 959
 960     [L_key L_value L_left L_right] W
 961
 962 We want to keep extracting the right node as long as it is not empty:
 963
 964     W.rightmost == [P] [B] while
 965
 966     left W.rightmost W′
 967
 968 The predicate:
 969
 970     [L_key L_value L_left L_right] P
 971     [L_key L_value L_left L_right] fourth
 972                           L_right
 973
 974 This can run on `[]` so must be guarded:
 975
 976     ?fourth ==  [] [fourth] [] ifte
 977
 978 (
 979     if_not_empty == [] swap [] ifte
 980     ?fourth == [fourth] if_not_empty
 981 )
 982
 983 The body is just `fourth`:
 984
 985     left [?fourth] [fourth] while W′
 986     rightest                      W′
 987
 988 So:
 989
 990     W.rightmost == [?fourth] [fourth] while
 991
 992 #### Found right-most node in our left sub-tree
 993 We know rightest is not empty:
 994
 995     [R_key R_value R_left R_right] W′
 996     [R_key R_value R_left R_right] W′
 997     [R_key R_value R_left R_right] uncons uncons pop
 998     R_key [R_value R_left R_right]        uncons pop
 999     R_key R_value [R_left R_right]               pop
1000     R_key R_value
1001
1002
1003 So:
1004
1005     W == [?fourth] [fourth] while uncons uncons pop
1006
1007 And:
1008
1009     right left left W        [D] E⁗
1010     right left R_key R_value [D] E⁗
1011
1012 #### Replace current node key and value, recursively delete rightmost
1013 Final stretch.  We want to end up with something like:
1014
1015     right left [R_key D] i R_value R_key
1016     right left  R_key D    R_value R_key
1017     right left′            R_value R_key
1018
1019 If we adjust our definition of `W` to include `over` at the end:
1020
1021     W == [fourth] [fourth] while uncons uncons pop over
1022
1023 That will give us:
1024
1025     right left R_key R_value R_key [D] E⁗
1026
1027     right left         R_key R_value R_key [D] cons dipd E⁗′
1028     right left         R_key R_value [R_key D]      dipd E⁗′
1029     right left R_key D R_key R_value                     E⁗′
1030     right left′        R_key R_value                     E⁗′
1031     right left′        R_key R_value                     swap
1032     right left′ R_value R_key
1033
1034 So:
1035
1036     E′ == roll> popop E″
1037
1038     E″ == rest E‴
1039
1040     E‴ == [dup W] dip E⁗
1041
1042     E⁗ == cons dipdd swap
1043
1044 Substituting:
1045
1046     W == [fourth] [fourth] while uncons uncons pop over
1047     E′ == roll> popop rest [dup W] dip cons dipd swap
1048     E == [
1049         [[pop third not] pop fourth]
1050         [[pop fourth not] pop third]
1051         [[E′] cons infra]
1052     ] cond
1053
1054 Minor rearrangement, move `dup` into `W`:
1055
1056     W == dup [fourth] [fourth] while uncons uncons pop over
1057     E′ == roll> popop rest [W] dip cons dipd swap
1058     E == [
1059         [[pop third not] pop fourth]
1060         [[pop fourth not] pop third]
1061         [[E′] cons infra]
1062     ] cond
1063
1064 ### Refactoring
1065
1066     W.rightmost == [fourth] [fourth] while
1067     W.unpack == uncons uncons pop
1068     W == dup W.rightmost W.unpack over
1069     E.clear_stuff == roll> popop rest
1070     E.delete == cons dipd
1071     E.0 == E.clear_stuff [W] dip E.delete swap
1072     E == [
1073         [[pop third not] pop fourth]
1074         [[pop fourth not] pop third]
1075         [[E.0] cons infra]
1076     ] cond
1077     T> == [dipd] cons infra
1078     T< == [dipdd] cons infra
1079     R0 == over first swap dup
1080     R1 == cons roll> [T>] [E] [T<] cmp
1081     BTree-Delete == [pop not] swap [R0] [R1] genrec
1082
1083 By the standards of the code I've written so far, this is a *huge* Joy program.
1084
1085
1086 ```python
1087 DefinitionWrapper.add_definitions('''
1088 first_two == uncons uncons pop
1089 fourth == rest rest rest first
1090 ?fourth == [] [fourth] [] ifte
1091 W.rightmost == [?fourth] [fourth] while
1092 E.clear_stuff == roll> popop rest
1093 E.delete == cons dipd
1094 W == dup W.rightmost first_two over
1095 E.0 == E.clear_stuff [W] dip E.delete swap
1096 E == [[[pop third not] pop fourth] [[pop fourth not] pop third] [[E.0] cons infra]] cond
1097 T> == [dipd] cons infra
1098 T< == [dipdd] cons infra
1099 R0 == over first swap dup
1100 R1 == cons roll> [T>] [E] [T<] cmp
1101 Tree-Delete == [pop not] [pop] [R0] [R1] genrec
1102 ''', D)
1103 ```
1104
1105
1106 ```python
1107 J("['a' 23 [] ['b' 88 [] ['c' 44 [] []]]] 'c' Tree-Delete ")
1108 ```
1109
1110     ['a' 23 [] ['b' 88 [] []]]
1111
1112
1113
1114 ```python
1115 J("['a' 23 [] ['b' 88 [] ['c' 44 [] []]]] 'b' Tree-Delete ")
1116 ```
1117
1118     ['a' 23 [] ['c' 44 [] []]]
1119
1120
1121
1122 ```python
1123 J("['a' 23 [] ['b' 88 [] ['c' 44 [] []]]] 'a' Tree-Delete ")
1124 ```
1125
1126     ['b' 88 [] ['c' 44 [] []]]
1127
1128
1129
1130 ```python
1131 J("['a' 23 [] ['b' 88 [] ['c' 44 [] []]]] 'der' Tree-Delete ")
1132 ```
1133
1134     ['a' 23 [] ['b' 88 [] ['c' 44 [] []]]]
1135
1136
1137
1138 ```python
1139 J('[] [4 2 3 1 6 7 5 ] [0 swap Tree-add] step')
1140 ```
1141
1142     [4 0 [2 0 [1 0 [] []] [3 0 [] []]] [6 0 [5 0 [] []] [7 0 [] []]]]
1143
1144
1145
1146 ```python
1147 J("[4 0 [2 0 [1 0 [] []] [3 0 [] []]] [6 0 [5 0 [] []] [7 0 [] []]]] 3 Tree-Delete ")
1148 ```
1149
1150     [4 0 [2 0 [1 0 [] []] []] [6 0 [5 0 [] []] [7 0 [] []]]]
1151
1152
1153
1154 ```python
1155 J("[4 0 [2 0 [1 0 [] []] [3 0 [] []]] [6 0 [5 0 [] []] [7 0 [] []]]] 4 Tree-Delete ")
1156 ```
1157
1158     [3 0 [2 0 [1 0 [] []] []] [6 0 [5 0 [] []] [7 0 [] []]]]
1159
1160
1161 ## Appendix: The source code.
1162
1163
1164
1165
1166     fourth == rest_two rest first
1167     ?fourth == [] [fourth] [] ifte
1168     first_two == uncons uncons pop
1169     ccons == cons cons
1170     cinf == cons infra
1171     rest_two == rest rest
1172
1173     _Tree_T> == [dipd] cinf
1174     _Tree_T< == [dipdd] cinf
1175
1176     _Tree_add_P == over [popop popop first] nullary
1177     _Tree_add_T> == ccons _Tree_T<
1178     _Tree_add_T< == ccons _Tree_T>
1179     _Tree_add_Ee == pop swap roll< rest_two ccons
1180     _Tree_add_R == _Tree_add_P [_Tree_add_T>] [_Tree_add_Ee] [_Tree_add_T<] cmp
1181     _Tree_add_E == [pop] dipd Tree-new
1182
1183     _Tree_iter_order_left == [cons dip] dupdip
1184     _Tree_iter_order_current == [[F] dupdip] dip
1185     _Tree_iter_order_right == [fourth] dip i
1186     _Tree_iter_order_R == _Tree_iter_order_left _Tree_iter_order_current _Tree_iter_order_right
1187
1188     _Tree_get_P == over [pop popop first] nullary
1189     _Tree_get_T> == [fourth] dipd i
1190     _Tree_get_T< == [third] dipd i
1191     _Tree_get_E == popop second
1192     _Tree_get_R == _Tree_get_P [_Tree_get_T>] [_Tree_get_E] [_Tree_get_T<] cmp
1193
1194     _Tree_delete_rightmost == [?fourth] [fourth] while
1195     _Tree_delete_clear_stuff == roll> popop rest
1196     _Tree_delete_del == dip cons dipd swap
1197     _Tree_delete_W == dup _Tree_delete_rightmost first_two over
1198     _Tree_delete_E.0 == _Tree_delete_clear_stuff [_Tree_delete_W] _Tree_delete_del
1199     _Tree_delete_E == [[[pop third not] pop fourth] [[pop fourth not] pop third] [[_Tree_delete_E.0] cinf]] cond
1200     _Tree_delete_R0 == over first swap dup
1201     _Tree_delete_R1 == cons roll> [_Tree_T>] [_Tree_delete_E] [_Tree_T<] cmp
1202
1203     Tree-new == swap [[] []] ccons
1204     Tree-add == [popop not] [_Tree_add_E] [] [_Tree_add_R] genrec
1205     Tree-iter == [not] [pop] roll< [dupdip rest_two] cons [step] genrec
1206     Tree-iter-order == [not] [pop] [dup third] [_Tree_iter_order_R] genrec
1207     Tree-get == [pop not] swap [] [_Tree_get_R] genrec
1208     Tree-delete == [pop not] [pop] [_Tree_delete_R0] [_Tree_delete_R1] genrec
1209
1210