docs/Trees.md

   1 # Treating Trees
   2 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.
   3
   4 The basic structure, in a [crude type notation](https://en.wikipedia.org/wiki/Algebraic_data_type), is:
   5
   6     BTree :: [] | [key value BTree BTree]
   7
   8 That says that a BTree is either the empty quote `[]` or a quote with four items: a key, a value, and two BTrees representing the left and right branches of the tree.
   9
  10 ## A Function to Traverse this Structure
  11 Let's take a crack at writing a function that can recursively iterate or traverse these trees.
  12
  13 #### Base case `[]`
  14 The stopping predicate just has to detect the empty list:
  15
  16     BTree-iter == [not] [E] [R0] [R1] genrec
  17
  18 And since there's nothing at this node, we just `pop` it:
  19
  20     BTree-iter == [not] [pop] [R0] [R1] genrec
  21
  22 #### Node case `[key value left right]`
  23 Now we need to figure out `R0` and `R1`:
  24
  25     BTree-iter == [not] [pop] [R0]            [R1] genrec
  26                == [not] [pop] [R0 [BTree-iter] R1] ifte
  27
  28 Let's look at it *in situ*:
  29
  30     [key value left right] R0 [BTree-iter] R1
  31
  32 #### Processing the current node.
  33
  34 `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:
  35
  36     [key value left right] [F] dupdip                 [BTree-iter] R1
  37     [key value left right]  F  [key value left right] [BTree-iter] R1
  38
  39 For example, if we're getting all the keys `F` would be `first`:
  40
  41     R0 == [first] dupdip
  42
  43     [key value left right] [first] dupdip                 [BTree-iter] R1
  44     [key value left right]  first  [key value left right] [BTree-iter] R1
  45     key                            [key value left right] [BTree-iter] R1
  46
  47 #### Recur
  48 Now `R1` needs to apply `[BTree-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:
  49
  50     key [key value left right] [BTree-iter] R1
  51     key [key value left right] [BTree-iter] [rest rest] dip
  52     key [key value left right] rest rest [BTree-iter]
  53     key [left right] [BTree-iter]
  54
  55 Hmm, will `step` do?
  56
  57     key [left right] [BTree-iter] step
  58     key left BTree-iter [right] [BTree-iter] step
  59     key left-keys [right] [BTree-iter] step
  60     key left-keys right BTree-iter
  61     key left-keys right-keys
  62
  63 Wow. So:
  64
  65     R1 == [rest rest] dip step
  66
  67 #### Putting it together
  68 We have:
  69
  70     BTree-iter == [not] [pop] [[F] dupdip] [[rest rest] dip step] genrec
  71
  72 When I was reading this over I realized `rest rest` could go in `R0`:
  73
  74     BTree-iter == [not] [pop] [[F] dupdip rest rest] [step] genrec
  75
  76 (And `[step] genrec` is such a cool and suggestive combinator!)
  77
  78 #### Parameterizing the `F` per-node processing function.
  79
  80     [F] BTree-iter == [not] [pop] [[F] dupdip rest rest] [step] genrec
  81
  82 Working backward:
  83
  84     [not] [pop] [[F] dupdip rest rest]            [step] genrec
  85     [not] [pop] [F]       [dupdip rest rest] cons [step] genrec
  86     [F] [not] [pop] roll< [dupdip rest rest] cons [step] genrec
  87
  88 Ergo:
  89
  90     BTree-iter == [not] [pop] roll< [dupdip rest rest] cons [step] genrec
  91
  92
  93 ```python
  94 from notebook_preamble import D, J, V, define, DefinitionWrapper
  95 ```
  96
  97
  98 ```python
  99 define('BTree-iter == [not] [pop] roll< [dupdip rest rest] cons [step] genrec')
 100 ```
 101
 102
 103 ```python
 104 J('[] [23] BTree-iter')  #  It doesn't matter what F is as it won't be used.
 105 ```
 106
 107
 108
 109
 110
 111 ```python
 112 J('["tommy" 23 [] []] [first] BTree-iter')
 113 ```
 114
 115     'tommy'
 116
 117
 118
 119 ```python
 120 J('["tommy" 23 ["richard" 48 [] []] ["jenny" 18 [] []]] [first] BTree-iter')
 121 ```
 122
 123     'tommy' 'richard' 'jenny'
 124
 125
 126
 127 ```python
 128 J('["tommy" 23 ["richard" 48 [] []] ["jenny" 18 [] []]] [second] BTree-iter')
 129 ```
 130
 131     23 48 18
 132
 133
 134 # Adding Nodes to the BTree
 135 Let's consider adding nodes to a BTree structure.
 136
 137     BTree value key BTree-add == BTree
 138
 139 #### Adding to an empty node.
 140 If the current node is `[]` then you just return `[key value [] []]`:
 141
 142     BTree-add == [popop not] [[pop] dipd BTree-new] [R0] [R1] genrec
 143
 144 Where `BTree-new` is:
 145
 146     value key BTree-new == [key value [] []]
 147
 148     value key swap [[] []] cons cons
 149     key value      [[] []] cons cons
 150     key      [value [] []]      cons
 151          [key value [] []]
 152
 153     BTree-new == swap [[] []] cons cons
 154
 155
 156 ```python
 157 define('BTree-new == swap [[] []] cons cons')
 158 ```
 159
 160
 161 ```python
 162 V('"v" "k" BTree-new')
 163 ```
 164
 165                     . 'v' 'k' BTree-new
 166                 'v' . 'k' BTree-new
 167             'v' 'k' . BTree-new
 168             'v' 'k' . swap [[] []] cons cons
 169             'k' 'v' . [[] []] cons cons
 170     'k' 'v' [[] []] . cons cons
 171     'k' ['v' [] []] . cons
 172     ['k' 'v' [] []] .
 173
 174
 175 (As an implementation detail, the `[[] []]` literal used in the definition of `BTree-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 `BTree-new`, all new nodes can reuse it as their own tail without fear that some other code somewhere will change it.)
 176
 177 #### If the current node isn't empty.
 178
 179 We now have to derive `R0` and `R1`, consider:
 180
 181     [key_n value_n left right] value key R0 [BTree-add] R1
 182
 183 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 `BTree-add`, so `R0` is pretty much out of the picture.
 184
 185     [R0] == []
 186
 187 #### A predicate to compare keys.
 188 The first thing we need to do is compare the the key we're adding to see if it is greater than the node key and `branch` accordingly, although in this case it's easier to write a destructive predicate and then use `ifte` to apply it `nullary`:
 189
 190     [key_n value_n left right] value key [BTree-add] R1
 191     [key_n value_n left right] value key [BTree-add] [P >] [T] [E] ifte
 192
 193     [key_n value_n left right] value key [BTree-add] P                   >
 194     [key_n value_n left right] value key [BTree-add] pop roll> pop first >
 195     [key_n value_n left right] value key                 roll> pop first >
 196     key [key_n value_n left right] value                 roll> pop first >
 197     key key_n                                                            >
 198     Boolean
 199
 200     P > == pop roll> pop first >
 201     P < == pop roll> pop first <
 202     P   == pop roll> pop first
 203
 204
 205 ```python
 206 define('P == pop roll> pop first')
 207 ```
 208
 209
 210 ```python
 211 V('["k" "v" [] []] "vv" "kk" [0] P >')
 212 ```
 213
 214                                   . ['k' 'v' [] []] 'vv' 'kk' [0] P >
 215                   ['k' 'v' [] []] . 'vv' 'kk' [0] P >
 216              ['k' 'v' [] []] 'vv' . 'kk' [0] P >
 217         ['k' 'v' [] []] 'vv' 'kk' . [0] P >
 218     ['k' 'v' [] []] 'vv' 'kk' [0] . P >
 219     ['k' 'v' [] []] 'vv' 'kk' [0] . pop roll> pop first >
 220         ['k' 'v' [] []] 'vv' 'kk' . roll> pop first >
 221         'kk' ['k' 'v' [] []] 'vv' . pop first >
 222              'kk' ['k' 'v' [] []] . first >
 223                          'kk' 'k' . >
 224                              True .
 225
 226
 227 #### If the key we're adding is greater than the node's key.
 228
 229 Here the parantheses are meant to signify that the right-hand side (RHS) is not literal, the code in the parentheses is meant to have been evaluated:
 230
 231     [key_n value_n left right] value key [BTree-add] T == [key_n value_n left (BTree-add key value right)]
 232
 233 #### Use `infra` on `K`.
 234 So how do we do this?  We know 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 `BTree-add` to apply somehow:
 235
 236     right left value_n key_n value key [BTree-add] K
 237         ...
 238     right value key BTree-add left value_n key_n
 239
 240 Pretty easy:
 241
 242     right left value_n key_n value key [BTree-add] cons cons dipdd
 243     right left value_n key_n [value key BTree-add]           dipdd
 244     right value key BTree-add left value_n key_n
 245
 246 So:
 247
 248     K == cons cons dipdd
 249
 250 And:
 251
 252     [key_n value_n left right] [value key [BTree-add] K] infra
 253
 254 #### Derive `T`.
 255 So now we're at getting from this to this:
 256
 257     [key_n value_n left right]  value key [BTree-add] T
 258         ...
 259     [key_n value_n left right] [value key [BTree-add] K] infra
 260
 261 And so `T` is just:
 262
 263     value key [BTree-add] T == [value key [BTree-add] K]                infra
 264                           T == [                      K] cons cons cons infra
 265
 266
 267 ```python
 268 define('K == cons cons dipdd')
 269 define('T == [K] cons cons cons infra')
 270 ```
 271
 272
 273 ```python
 274 V('"r" "l" "v" "k" "vv" "kk" [0] K')
 275 ```
 276
 277                                   . 'r' 'l' 'v' 'k' 'vv' 'kk' [0] K
 278                               'r' . 'l' 'v' 'k' 'vv' 'kk' [0] K
 279                           'r' 'l' . 'v' 'k' 'vv' 'kk' [0] K
 280                       'r' 'l' 'v' . 'k' 'vv' 'kk' [0] K
 281                   'r' 'l' 'v' 'k' . 'vv' 'kk' [0] K
 282              'r' 'l' 'v' 'k' 'vv' . 'kk' [0] K
 283         'r' 'l' 'v' 'k' 'vv' 'kk' . [0] K
 284     'r' 'l' 'v' 'k' 'vv' 'kk' [0] . K
 285     'r' 'l' 'v' 'k' 'vv' 'kk' [0] . cons cons dipdd
 286     'r' 'l' 'v' 'k' 'vv' ['kk' 0] . cons dipdd
 287     'r' 'l' 'v' 'k' ['vv' 'kk' 0] . dipdd
 288                               'r' . 'vv' 'kk' 0 'l' 'v' 'k'
 289                          'r' 'vv' . 'kk' 0 'l' 'v' 'k'
 290                     'r' 'vv' 'kk' . 0 'l' 'v' 'k'
 291                   'r' 'vv' 'kk' 0 . 'l' 'v' 'k'
 292               'r' 'vv' 'kk' 0 'l' . 'v' 'k'
 293           'r' 'vv' 'kk' 0 'l' 'v' . 'k'
 294       'r' 'vv' 'kk' 0 'l' 'v' 'k' .
 295
 296
 297
 298 ```python
 299 V('["k" "v" "l" "r"] "vv" "kk" [0] T')
 300 ```
 301
 302                                         . ['k' 'v' 'l' 'r'] 'vv' 'kk' [0] T
 303                       ['k' 'v' 'l' 'r'] . 'vv' 'kk' [0] T
 304                  ['k' 'v' 'l' 'r'] 'vv' . 'kk' [0] T
 305             ['k' 'v' 'l' 'r'] 'vv' 'kk' . [0] T
 306         ['k' 'v' 'l' 'r'] 'vv' 'kk' [0] . T
 307         ['k' 'v' 'l' 'r'] 'vv' 'kk' [0] . [K] cons cons cons infra
 308     ['k' 'v' 'l' 'r'] 'vv' 'kk' [0] [K] . cons cons cons infra
 309     ['k' 'v' 'l' 'r'] 'vv' 'kk' [[0] K] . cons cons infra
 310     ['k' 'v' 'l' 'r'] 'vv' ['kk' [0] K] . cons infra
 311     ['k' 'v' 'l' 'r'] ['vv' 'kk' [0] K] . infra
 312                         'r' 'l' 'v' 'k' . 'vv' 'kk' [0] K [] swaack
 313                    'r' 'l' 'v' 'k' 'vv' . 'kk' [0] K [] swaack
 314               'r' 'l' 'v' 'k' 'vv' 'kk' . [0] K [] swaack
 315           'r' 'l' 'v' 'k' 'vv' 'kk' [0] . K [] swaack
 316           'r' 'l' 'v' 'k' 'vv' 'kk' [0] . cons cons dipdd [] swaack
 317           'r' 'l' 'v' 'k' 'vv' ['kk' 0] . cons dipdd [] swaack
 318           'r' 'l' 'v' 'k' ['vv' 'kk' 0] . dipdd [] swaack
 319                                     'r' . 'vv' 'kk' 0 'l' 'v' 'k' [] swaack
 320                                'r' 'vv' . 'kk' 0 'l' 'v' 'k' [] swaack
 321                           'r' 'vv' 'kk' . 0 'l' 'v' 'k' [] swaack
 322                         'r' 'vv' 'kk' 0 . 'l' 'v' 'k' [] swaack
 323                     'r' 'vv' 'kk' 0 'l' . 'v' 'k' [] swaack
 324                 'r' 'vv' 'kk' 0 'l' 'v' . 'k' [] swaack
 325             'r' 'vv' 'kk' 0 'l' 'v' 'k' . [] swaack
 326          'r' 'vv' 'kk' 0 'l' 'v' 'k' [] . swaack
 327           ['k' 'v' 'l' 0 'kk' 'vv' 'r'] .
 328
 329
 330 #### If the key we're adding is less than the node's key.
 331 This is very very similar to the above:
 332
 333     [key_n value_n left right] value key [BTree-add] E
 334     [key_n value_n left right] value key [BTree-add] [P <] [Te] [Ee] ifte
 335
 336 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`:
 337
 338     Te == [cons cons dipd] cons cons cons infra
 339
 340 This suggests an alternate factorization:
 341
 342     ccons == cons cons
 343     T == [ccons dipdd] ccons cons infra
 344     Te == [ccons dipd] ccons cons infra
 345
 346 But whatever.
 347
 348
 349 ```python
 350 define('Te == [cons cons dipd] cons cons cons infra')
 351 ```
 352
 353
 354 ```python
 355 V('["k" "v" "l" "r"] "vv" "kk" [0] Te')
 356 ```
 357
 358                                                      . ['k' 'v' 'l' 'r'] 'vv' 'kk' [0] Te
 359                                    ['k' 'v' 'l' 'r'] . 'vv' 'kk' [0] Te
 360                               ['k' 'v' 'l' 'r'] 'vv' . 'kk' [0] Te
 361                          ['k' 'v' 'l' 'r'] 'vv' 'kk' . [0] Te
 362                      ['k' 'v' 'l' 'r'] 'vv' 'kk' [0] . Te
 363                      ['k' 'v' 'l' 'r'] 'vv' 'kk' [0] . [cons cons dipd] cons cons cons infra
 364     ['k' 'v' 'l' 'r'] 'vv' 'kk' [0] [cons cons dipd] . cons cons cons infra
 365     ['k' 'v' 'l' 'r'] 'vv' 'kk' [[0] cons cons dipd] . cons cons infra
 366     ['k' 'v' 'l' 'r'] 'vv' ['kk' [0] cons cons dipd] . cons infra
 367     ['k' 'v' 'l' 'r'] ['vv' 'kk' [0] cons cons dipd] . infra
 368                                      'r' 'l' 'v' 'k' . 'vv' 'kk' [0] cons cons dipd [] swaack
 369                                 'r' 'l' 'v' 'k' 'vv' . 'kk' [0] cons cons dipd [] swaack
 370                            'r' 'l' 'v' 'k' 'vv' 'kk' . [0] cons cons dipd [] swaack
 371                        'r' 'l' 'v' 'k' 'vv' 'kk' [0] . cons cons dipd [] swaack
 372                        'r' 'l' 'v' 'k' 'vv' ['kk' 0] . cons dipd [] swaack
 373                        'r' 'l' 'v' 'k' ['vv' 'kk' 0] . dipd [] swaack
 374                                              'r' 'l' . 'vv' 'kk' 0 'v' 'k' [] swaack
 375                                         'r' 'l' 'vv' . 'kk' 0 'v' 'k' [] swaack
 376                                    'r' 'l' 'vv' 'kk' . 0 'v' 'k' [] swaack
 377                                  'r' 'l' 'vv' 'kk' 0 . 'v' 'k' [] swaack
 378                              'r' 'l' 'vv' 'kk' 0 'v' . 'k' [] swaack
 379                          'r' 'l' 'vv' 'kk' 0 'v' 'k' . [] swaack
 380                       'r' 'l' 'vv' 'kk' 0 'v' 'k' [] . swaack
 381                        ['k' 'v' 0 'kk' 'vv' 'l' 'r'] .
 382
 383
 384 #### Else the keys must be equal.
 385 This means we must find:
 386
 387     [key_n value_n left right] value key [BTree-add] Ee
 388         ...
 389     [key value left right]
 390
 391 This is another easy one:
 392
 393     Ee == pop swap roll< rest rest cons cons
 394
 395     [key_n value_n left right] value key [BTree-add] pop swap roll< rest rest cons cons
 396     [key_n value_n left right] value key                 swap roll< rest rest cons cons
 397     [key_n value_n left right] key value                      roll< rest rest cons cons
 398     key value [key_n value_n left right]                            rest rest cons cons
 399     key value [              left right]                                      cons cons
 400               [key   value   left right]
 401
 402
 403 ```python
 404 define('Ee == pop swap roll< rest rest cons cons')
 405 ```
 406
 407
 408 ```python
 409 V('["k" "v" "l" "r"] "vv" "k" [0] Ee')
 410 ```
 411
 412                                    . ['k' 'v' 'l' 'r'] 'vv' 'k' [0] Ee
 413                  ['k' 'v' 'l' 'r'] . 'vv' 'k' [0] Ee
 414             ['k' 'v' 'l' 'r'] 'vv' . 'k' [0] Ee
 415         ['k' 'v' 'l' 'r'] 'vv' 'k' . [0] Ee
 416     ['k' 'v' 'l' 'r'] 'vv' 'k' [0] . Ee
 417     ['k' 'v' 'l' 'r'] 'vv' 'k' [0] . pop swap roll< rest rest cons cons
 418         ['k' 'v' 'l' 'r'] 'vv' 'k' . swap roll< rest rest cons cons
 419         ['k' 'v' 'l' 'r'] 'k' 'vv' . roll< rest rest cons cons
 420         'k' 'vv' ['k' 'v' 'l' 'r'] . rest rest cons cons
 421             'k' 'vv' ['v' 'l' 'r'] . rest cons cons
 422                 'k' 'vv' ['l' 'r'] . cons cons
 423                 'k' ['vv' 'l' 'r'] . cons
 424                 ['k' 'vv' 'l' 'r'] .
 425
 426
 427
 428 ```python
 429 define('E == [P <] [Te] [Ee] ifte')
 430 ```
 431
 432 #### Now we can define `BTree-add`
 433     BTree-add == [popop not] [[pop] dipd BTree-new] [] [[P >] [T] [E] ifte] genrec
 434
 435 Putting it all together:
 436
 437     BTree-new == swap [[] []] cons cons
 438     P == pop roll> pop first
 439     T == [cons cons dipdd] cons cons cons infra
 440     Te == [cons cons dipd] cons cons cons infra
 441     Ee == pop swap roll< rest rest cons cons
 442     E == [P <] [Te] [Ee] ifte
 443
 444     BTree-add == [popop not] [[pop] dipd BTree-new] [] [[P >] [T] [E] ifte] genrec
 445
 446
 447 ```python
 448 define('BTree-add == [popop not] [[pop] dipd BTree-new] [] [[P >] [T] [E] ifte] genrec')
 449 ```
 450
 451
 452 ```python
 453 J('[] 23 "b" BTree-add')  # Initial
 454 ```
 455
 456     ['b' 23 [] []]
 457
 458
 459
 460 ```python
 461 J('["b" 23 [] []] 88 "c" BTree-add')  # Less than
 462 ```
 463
 464     ['b' 23 [] ['c' 88 [] []]]
 465
 466
 467
 468 ```python
 469 J('["b" 23 [] []] 88 "a" BTree-add')  # Greater than
 470 ```
 471
 472     ['b' 23 ['a' 88 [] []] []]
 473
 474
 475
 476 ```python
 477 J('["b" 23 [] []] 88 "b" BTree-add')  # Equal to
 478 ```
 479
 480     ['b' 88 [] []]
 481
 482
 483
 484 ```python
 485 J('[] 23 "a" BTree-add 88 "b" BTree-add 44 "c" BTree-add')  # Series.
 486 ```
 487
 488     ['a' 23 [] ['b' 88 [] ['c' 44 [] []]]]
 489
 490
 491 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.
 492
 493
 494 ```python
 495 J('[] [3 9 5 2 8 6 7 8 4] [0 swap BTree-add] step')
 496 ```
 497
 498     [3 0 [2 0 [] []] [9 0 [5 0 [4 0 [] []] [8 0 [6 0 [] [7 0 [] []]] []]] []]]
 499
 500
 501
 502 ```python
 503 define('to_set == [] swap [0 swap BTree-add] step')
 504 ```
 505
 506
 507 ```python
 508 J('[3 9 5 2 8 6 7 8 4] to_set')
 509 ```
 510
 511     [3 0 [2 0 [] []] [9 0 [5 0 [4 0 [] []] [8 0 [6 0 [] [7 0 [] []]] []]] []]]
 512
 513
 514 And with that we can write a little program to remove duplicate items from a list.
 515
 516
 517 ```python
 518 define('unique == [to_set [first] BTree-iter] cons run')
 519 ```
 520
 521
 522 ```python
 523 J('[3 9 3 5 2 9 8 8 8 6 2 7 8 4 3] unique')  # Filter duplicate items.
 524 ```
 525
 526     [7 6 8 4 5 9 2 3]
 527
 528
 529 # `cmp` combinator
 530 Instead of all this mucking about with nested `ifte` let's just go whole hog and define `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:
 531
 532        a b [G] [E] [L] cmp
 533     ------------------------- a > b
 534             G
 535
 536        a b [G] [E] [L] cmp
 537     ------------------------- a = b
 538                 E
 539
 540        a b [G] [E] [L] cmp
 541     ------------------------- a < b
 542                     L
 543
 544 We need a new non-destructive predicate `P`:
 545
 546     [key_n value_n left right] value key [BTree-add] P
 547     [key_n value_n left right] value key [BTree-add] over [Q] nullary
 548     [key_n value_n left right] value key [BTree-add] key  [Q] nullary
 549     [key_n value_n left right] value key [BTree-add] key   Q
 550     [key_n value_n left right] value key [BTree-add] key   popop popop first
 551     [key_n value_n left right] value key                         popop first
 552     [key_n value_n left right]                                         first
 553      key_n
 554     [key_n value_n left right] value key [BTree-add] key  [Q] nullary
 555     [key_n value_n left right] value key [BTree-add] key key_n
 556
 557     P == over [popop popop first] nullary
 558
 559 Here are the definitions again, pruned and renamed in some cases:
 560
 561     BTree-new == swap [[] []] cons cons
 562     P == over [popop popop first] nullary
 563     T> == [cons cons dipdd] cons cons cons infra
 564     T< == [cons cons dipd] cons cons cons infra
 565     E == pop swap roll< rest rest cons cons
 566
 567 Using `cmp` to simplify [our code above at `R1`](#If-the-current-node-isn't-empty.):
 568
 569     [key_n value_n left right] value key [BTree-add] R1
 570     [key_n value_n left right] value key [BTree-add] P [T>] [E] [T<] cmp
 571
 572 The line above becomes one of the three lines below:
 573
 574     [key_n value_n left right] value key [BTree-add] T>
 575     [key_n value_n left right] value key [BTree-add] E
 576     [key_n value_n left right] value key [BTree-add] T<
 577
 578 The definition is a little longer but, I think, more elegant and easier to understand:
 579
 580     BTree-add == [popop not] [[pop] dipd BTree-new] [] [P [T>] [E] [T<] cmp] genrec
 581
 582
 583
 584 ```python
 585 from joy.library import FunctionWrapper
 586 from joy.utils.stack import concat
 587 from notebook_preamble import D
 588
 589
 590 @FunctionWrapper
 591 def cmp_(stack, expression, dictionary):
 592     '''
 593     cmp takes two values and three quoted programs on the stack and runs
 594     one of the three depending on the results of comparing the two values:
 595
 596            a b [G] [E] [L] cmp
 597         ------------------------- a > b
 598                 G
 599
 600            a b [G] [E] [L] cmp
 601         ------------------------- a = b
 602                     E
 603
 604            a b [G] [E] [L] cmp
 605         ------------------------- a < b
 606                         L
 607     '''
 608     L, (E, (G, (b, (a, stack)))) = stack
 609     expression = concat(G if a > b else L if a < b else E, expression)
 610     return stack, expression, dictionary
 611
 612
 613 D['cmp'] = cmp_
 614 ```
 615
 616
 617 ```python
 618 from joy.library import FunctionWrapper, S_ifte
 619
 620
 621 @FunctionWrapper
 622 def cond(stack, expression, dictionary):
 623   '''
 624   like a case statement; works by rewriting into a chain of ifte.
 625
 626   [..[[Bi] Ti]..[D]] -> ...
 627
 628
 629         [[[B0] T0] [[B1] T1] [D]] cond
 630   -----------------------------------------
 631      [B0] [T0] [[B1] [T1] [D] ifte] ifte
 632
 633   '''
 634   conditions, stack = stack
 635   if conditions:
 636     expression = _cond(conditions, expression)
 637     try:
 638       # Attempt to preload the args to first ifte.
 639       (P, (T, (E, expression))) = expression
 640     except ValueError:
 641       # If, for any reason, the argument to cond should happen to contain
 642       # only the default clause then this optimization will fail.
 643       pass
 644     else:
 645       stack = (E, (T, (P, stack)))
 646   return stack, expression, dictionary
 647
 648
 649 def _cond(conditions, expression):
 650   (clause, rest) = conditions
 651   if not rest:  # clause is [D]
 652     return clause
 653   P, T = clause
 654   return (P, (T, (_cond(rest, ()), (S_ifte, expression))))
 655
 656
 657
 658 D['cond'] = cond
 659 ```
 660
 661
 662 ```python
 663 J("1 0 ['G'] ['E'] ['L'] cmp")
 664 ```
 665
 666     'G'
 667
 668
 669
 670 ```python
 671 J("1 1 ['G'] ['E'] ['L'] cmp")
 672 ```
 673
 674     'E'
 675
 676
 677
 678 ```python
 679 J("0 1 ['G'] ['E'] ['L'] cmp")
 680 ```
 681
 682     'L'
 683
 684
 685
 686 ```python
 687 from joy.library import DefinitionWrapper
 688
 689
 690 DefinitionWrapper.add_definitions('''
 691
 692 P == over [popop popop first] nullary
 693 T> == [cons cons dipdd] cons cons cons infra
 694 T< == [cons cons dipd] cons cons cons infra
 695 E == pop swap roll< rest rest cons cons
 696
 697 BTree-add == [popop not] [[pop] dipd BTree-new] [] [P [T>] [E] [T<] cmp] genrec
 698
 699 ''', D)
 700 ```
 701
 702
 703 ```python
 704 J('[] 23 "b" BTree-add')  # Initial
 705 ```
 706
 707     ['b' 23 [] []]
 708
 709
 710
 711 ```python
 712 J('["b" 23 [] []] 88 "c" BTree-add')  # Less than
 713 ```
 714
 715     ['b' 23 [] ['c' 88 [] []]]
 716
 717
 718
 719 ```python
 720 J('["b" 23 [] []] 88 "a" BTree-add')  # Greater than
 721 ```
 722
 723     ['b' 23 ['a' 88 [] []] []]
 724
 725
 726
 727 ```python
 728 J('["b" 23 [] []] 88 "b" BTree-add')  # Equal to
 729 ```
 730
 731     ['b' 88 [] []]
 732
 733
 734
 735 ```python
 736 J('[] 23 "a" BTree-add 88 "b" BTree-add 44 "c" BTree-add')  # Series.
 737 ```
 738
 739     ['a' 23 [] ['b' 88 [] ['c' 44 [] []]]]
 740
 741
 742 # Factoring and naming
 743 It may seem silly, but a big part of programming in Forth (and therefore in Joy) is the idea of small, highly-factored definitions.  If you choose names carefully the resulting definitions can take on a semantic role.
 744
 745     get-node-key == popop popop first
 746     remove-key-and-value-from-node == rest rest
 747     pack-key-and-value == cons cons
 748     prep-new-key-and-value == pop swap roll<
 749     pack-and-apply == [pack-key-and-value] swoncat cons pack-key-and-value infra
 750
 751     BTree-new == swap [[] []] pack-key-and-value
 752     P == over [get-node-key] nullary
 753     T> == [dipdd] pack-and-apply
 754     T< == [dipd] pack-and-apply
 755     E == prep-new-key-and-value remove-key-and-value-from-node pack-key-and-value
 756
 757
 758 # A Version of `BTree-iter` that does In-Order Traversal
 759
 760 If you look back to the [non-empty case of the `BTree-iter` function](#Node-case-[key-value-left-right]) we can design a varient 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.
 761
 762     BTree-iter-order == [not] [pop] [R0 [BTree-iter] R1] ifte
 763
 764 To define `R0` and `R1` it helps to look at them as they will appear when they run:
 765
 766     [key value left right] R0 [BTree-iter-order] R1
 767
 768 #### Process the left child.
 769 Staring at this for a bit suggests `dup third` to start:
 770
 771     [key value left right] R0        [BTree-iter-order] R1
 772     [key value left right] dup third [BTree-iter-order] R1
 773     [key value left right] left      [BTree-iter-order] R1
 774
 775 Now maybe:
 776
 777     [key value left right] left [BTree-iter-order] [cons dip] dupdip
 778     [key value left right] left [BTree-iter-order] cons dip [BTree-iter-order]
 779     [key value left right] [left BTree-iter-order]      dip [BTree-iter-order]
 780     left BTree-iter-order [key value left right]            [BTree-iter-order]
 781
 782 #### Process the current node.
 783 So far, so good.  Now we need to process the current node's values:
 784
 785     left BTree-iter-order [key value left right] [BTree-iter-order] [[F] dupdip] dip
 786     left BTree-iter-order [key value left right] [F] dupdip [BTree-iter-order]
 787     left BTree-iter-order [key value left right] F [key value left right] [BTree-iter-order]
 788
 789 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.
 790
 791     left BTree-iter-order [key value left right] first [key value left right] [BTree-iter-order]
 792     left BTree-iter-order key [key value left right] [BTree-iter-order]
 793
 794 #### Process the right child.
 795 First ditch the rest of the node and get the right child:
 796
 797     left BTree-iter-order key [key value left right] [BTree-iter-order] [rest rest rest first] dip
 798     left BTree-iter-order key right [BTree-iter-order]
 799
 800 Then, of course, we just need `i` to run `BTree-iter-order` on the right side:
 801
 802     left BTree-iter-order key right [BTree-iter-order] i
 803     left BTree-iter-order key right BTree-iter-order
 804
 805 #### Defining `BTree-iter-order`
 806 The result is a little awkward:
 807
 808     R1 == [cons dip] dupdip [[F] dupdip] dip [rest rest rest first] dip i
 809
 810 Let's do a little semantic factoring:
 811
 812     fourth == rest rest rest first
 813
 814     proc_left == [cons dip] dupdip
 815     proc_current == [[F] dupdip] dip
 816     proc_right == [fourth] dip i
 817
 818     BTree-iter-order == [not] [pop] [dup third] [proc_left proc_current proc_right] genrec
 819
 820 Now we can sort sequences.
 821
 822
 823 ```python
 824 define('BTree-iter-order == [not] [pop] [dup third] [[cons dip] dupdip [[first] dupdip] dip [rest rest rest first] dip i] genrec')
 825 ```
 826
 827
 828 ```python
 829 J('[3 9 5 2 8 6 7 8 4] to_set BTree-iter-order')
 830 ```
 831
 832     2 3 4 5 6 7 8 9
 833
 834
 835 # Getting values by key
 836 Let's derive a function that accepts a tree and a key and returns the value associated with that key.
 837
 838        tree key BTree-get
 839     ------------------------
 840             value
 841
 842 #### The base case `[]`
 843 As before, the stopping predicate just has to detect the empty list:
 844
 845     BTree-get == [pop not] [E] [R0] [R1] genrec
 846
 847 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", methinks.)
 848
 849 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.
 850
 851
 852        tree key [E] BTree-get
 853     ---------------------------- key in tree
 854                value
 855
 856        tree key [E] BTree-get
 857     ---------------------------- key not in tree
 858              tree key E
 859
 860 Now we define:
 861
 862     BTree-get == [pop not] swap [R0] [R1] genrec
 863
 864 Note that this `BTree-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.
 865
 866     tree key [E] [pop not] swap [R0] [R1] genrec
 867     tree key [pop not] [E] [R0] [R1] genrec
 868
 869 The anonymous specialized recursive function that will do the real work.
 870
 871     [pop not] [E] [R0] [R1] genrec
 872
 873 #### Node case `[key value left right]`
 874 Now we need to figure out `R0` and `R1`:
 875
 876     [key value left right] key R0 [BTree-get] R1
 877
 878 We want to compare the search key with the key in the node, and if they are the same return the value and if they differ then recurse on one of the child nodes.  So it's very similar to the above funtion, with `[R0] == []` and `R1 == P [T>] [E] [T<] cmp`:
 879
 880     [key value left right] key [BTree-get] P [T>] [E] [T<] cmp
 881
 882 So:
 883
 884     get-node-key == pop popop first
 885     P == over [get-node-key] nullary
 886
 887 The only difference is that `get-node-key` does one less `pop` because there's no value to discard.  Now we have to derive the branches:
 888
 889     [key_n value_n left right] key [BTree-get] T>
 890     [key_n value_n left right] key [BTree-get] E
 891     [key_n value_n left right] key [BTree-get] T<
 892
 893 The cases of `T>` and `T<` are similar to above but instead of using `infra` we have to discard the rest of the structure:
 894
 895     [key_n value_n left right] key [BTree-get] T> == right key BTree-get
 896     [key_n value_n left right] key [BTree-get] T< == left key BTree-get
 897
 898 So:
 899
 900     T> == [fourth] dipd i
 901     T< == [third] dipd i
 902
 903 E.g.:
 904
 905     [key_n value_n left right]        key [BTree-get] [fourth] dipd i
 906     [key_n value_n left right] fourth key [BTree-get]               i
 907                         right         key [BTree-get]               i
 908                         right         key  BTree-get
 909
 910 And:
 911
 912     [key_n value_n left right] key [BTree-get] E == value_n
 913
 914     E == popop second
 915
 916 So:
 917
 918     fourth == rest rest rest first
 919     get-node-key == pop popop first
 920     P == over [get-node-key] nullary
 921     T> == [fourth] dipd i
 922     T< == [third] dipd i
 923     E == popop second
 924
 925     BTree-get == [pop not] swap [] [P [T>] [E] [T<] cmp] genrec
 926
 927
 928 ```python
 929 # I don't want to deal with name conflicts with the above so I'm inlining everything here.
 930 # The original Joy system has "hide" which is a meta-command which allows you to use named
 931 # definitions that are only in scope for a given definition.  I don't want to implement
 932 # that (yet) so...
 933
 934
 935 define('''
 936 BTree-get == [pop not] swap [] [
 937   over [pop popop first] nullary
 938   [[rest rest rest first] dipd i]
 939   [popop second]
 940   [[third] dipd i]
 941   cmp
 942   ] genrec
 943 ''')
 944 ```
 945
 946
 947 ```python
 948 J('[] "gary" [popop "err"] BTree-get')
 949 ```
 950
 951     'err'
 952
 953
 954
 955 ```python
 956 J('["gary" 23 [] []] "gary" [popop "err"] BTree-get')
 957 ```
 958
 959     23
 960
 961
 962
 963 ```python
 964 J('''
 965
 966     [] [[0 'a'] [1 'b'] [2 'c']] [i BTree-add] step
 967
 968     'c' [popop 'not found'] BTree-get
 969
 970 ''')
 971 ```
 972
 973     2
 974
 975
 976 # BTree-delete
 977
 978 Now let's write a function that can return a tree datastructure with a key, value pair deleted:
 979
 980        tree key BTree-delete
 981     ---------------------------
 982            tree
 983
 984
 985 If the key is not in tree it just returns the tree unchanged.
 986
 987 So:
 988
 989     BTree-Delete == [pop not] swap [R0] [R1] genrec
 990
 991
 992                  [Er] BTree-delete
 993     -------------------------------------
 994        [pop not] [Er] [R0] [R1] genrec
 995
 996     [n_key n_value left right] [BTree-get]
 997     [n_key n_value left right] [BTree-get] E
 998     [n_key n_value left right] [BTree-get] T<
 999
1000 Now we get to figure out the recursive case:
1001
1002     w/ D == [pop not] [Er] [R0] [R1] genrec
1003
1004     [node_key node_value left right] key R0                  [D] R1
1005     [node_key node_value left right] key over first swap dup [D] R1
1006     [node_key node_value left right] node_key key key        [D] R1
1007
1008 And then:
1009
1010     [node_key node_value left right] node_key key key [D] R1
1011     [node_key node_value left right] node_key key key [D] cons roll> [T>] [E] [T<] cmp
1012     [node_key node_value left right] node_key key [key D]      roll> [T>] [E] [T<] cmp
1013     [node_key node_value left right] [key D] node_key key            [T>] [E] [T<] cmp
1014
1015 Now this:;
1016
1017     [node_key node_value left right] [key D] node_key key [T>] [E] [T<] cmp
1018
1019 Becomes one of these three:;
1020
1021     [node_key node_value left right] [key D] T>
1022     [node_key node_value left right] [key D] E
1023     [node_key node_value left right] [key D] T<
1024
1025 ### Greater than case and less than case
1026
1027        [node_key node_value left right] [key D] T>
1028     -------------------------------------------------
1029        [node_key node_value left key D right]
1030
1031 First:
1032
1033     right left       node_value node_key [key D] dipd
1034     right left key D node_value node_key
1035     right left'      node_value node_key
1036
1037 Ergo:
1038
1039     [node_key node_value left right] [key D] [dipd] cons infra
1040
1041 So:
1042
1043     T> == [dipd] cons infra
1044     T< == [dipdd] cons infra
1045
1046 ### The else case
1047
1048     [node_key node_value left right] [key D] E
1049
1050 We have to handle three cases, so let's use `cond`.
1051
1052 The first two cases are symmetrical, if we only have one non-empty child node return it.
1053
1054     E == [
1055         [[pop third not] pop fourth]
1056         [[pop fourth not] pop third]
1057         [default]
1058     ] cond
1059
1060 (If both child nodes are empty return an empty node.)
1061
1062 The initial structure of the default function:
1063
1064     default == [E'] cons infra
1065
1066     [node_key node_value left right] [key D] default
1067     [node_key node_value left right] [key D] [E'] cons infra
1068     [node_key node_value left right] [[key D] E']      infra
1069
1070     right left node_value node_key [key D] E'
1071
1072 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.
1073
1074 (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.)
1075
1076 First things first, we no longer need this node's key and value:
1077
1078     right left node_value node_key [key D] roll> popop E''
1079     right left [key D] node_value node_key       popop E''
1080     right left [key D]                                 E''
1081
1082 Then we have to we find the highest (right-most) node in our lower (left) sub-tree:
1083
1084     right left [key D] E''
1085
1086 Ditch the key:
1087
1088     right left [key D] rest E'''
1089     right left     [D]      E'''
1090
1091 Find the right-most node:
1092
1093     right left        [D] [dup W] dip E''''
1094     right left dup  W [D]             E''''
1095     right left left W [D]             E''''
1096
1097 Consider:
1098
1099     left W
1100
1101 We know left is not empty:
1102
1103     [L_key L_value L_left L_right] W
1104
1105 We want to keep extracting the right node as long as it is not empty:
1106
1107     left [P] [B] while W'
1108
1109 The predicate:
1110
1111     [L_key L_value L_left L_right] P
1112     [L_key L_value L_left L_right] fourth
1113                           L_right
1114
1115 (This has a bug, can run on `[]` so must be guarded:
1116
1117     if_not_empty == [] swap [] ifte
1118     ?fourth == [fourth] if_not_empty
1119     W.rightmost == [?fourth] [fourth] while
1120
1121 The body is also `fourth`:
1122
1123     left [fourth] [fourth] while W'
1124     rightest                     W'
1125
1126 We know rightest is not empty:
1127
1128     [R_key R_value R_left R_right] W'
1129     [R_key R_value R_left R_right] uncons uncons pop
1130     R_key [R_value R_left R_right]        uncons pop
1131     R_key R_value [R_left R_right]               pop
1132     R_key R_value
1133
1134 So:
1135
1136     W == [fourth] [fourth] while uncons uncons pop
1137
1138 And:
1139
1140     right left left W        [D] E''''
1141     right left R_key R_value [D] E''''
1142
1143 Final stretch.  We want to end up with something like:
1144
1145     right left [R_key D] i R_value R_key
1146     right left  R_key D    R_value R_key
1147     right left'            R_value R_key
1148
1149 If we adjust our definition of `W` to include `over` at the end:
1150
1151     W == [fourth] [fourth] while uncons uncons pop over
1152
1153 That will give us:
1154
1155     right left R_key R_value R_key [D] E''''
1156
1157     right left         R_key R_value R_key [D] cons dipdd E'''''
1158     right left         R_key R_value [R_key D]      dipdd E'''''
1159     right left R_key D R_key R_value                      E'''''
1160     right left'        R_key R_value                      E'''''
1161     right left'        R_key R_value                      swap
1162     right left' R_value R_key
1163
1164 So:
1165
1166     E' == roll> popop E''
1167
1168     E'' == rest E'''
1169
1170     E''' == [dup W] dip E''''
1171
1172     E'''' == cons dipdd swap
1173
1174 Substituting:
1175
1176     W == [fourth] [fourth] while uncons uncons pop over
1177     E' == roll> popop rest [dup W] dip cons dipdd swap
1178     E == [
1179         [[pop third not] pop fourth]
1180         [[pop fourth not] pop third]
1181         [[E'] cons infra]
1182     ] cond
1183
1184 Minor rearrangement:
1185
1186     W == dup [fourth] [fourth] while uncons uncons pop over
1187     E' == roll> popop rest [W] dip cons dipdd swap
1188     E == [
1189         [[pop third not] pop fourth]
1190         [[pop fourth not] pop third]
1191         [[E'] cons infra]
1192     ] cond
1193
1194 ### Refactoring
1195
1196     W.rightmost == [fourth] [fourth] while
1197     W.unpack == uncons uncons pop
1198     E.clear_stuff == roll> popop rest
1199     E.delete == cons dipdd
1200     W == dup W.rightmost W.unpack over
1201     E.0 == E.clear_stuff [W] dip E.delete swap
1202     E == [
1203         [[pop third not] pop fourth]
1204         [[pop fourth not] pop third]
1205         [[E.0] cons infra]
1206     ] cond
1207     T> == [dipd] cons infra
1208     T< == [dipdd] cons infra
1209     R0 == over first swap dup
1210     R1 == cons roll> [T>] [E] [T<] cmp
1211     BTree-Delete == [pop not] swap [R0] [R1] genrec
1212
1213 By the standards of the code I've written so far, this is a *huge* Joy program.
1214
1215
1216 ```python
1217 DefinitionWrapper.add_definitions('''
1218 first_two == uncons uncons pop
1219 fourth == rest rest rest first
1220 ?fourth == [] [fourth] [] ifte
1221 W.rightmost == [?fourth] [fourth] while
1222 E.clear_stuff == roll> popop rest
1223 E.delete == cons dipdd
1224 W == dup W.rightmost first_two over
1225 E.0 == E.clear_stuff [W] dip E.delete swap
1226 E == [[[pop third not] pop fourth] [[pop fourth not] pop third] [[E.0] cons infra]] cond
1227 T> == [dipd] cons infra
1228 T< == [dipdd] cons infra
1229 R0 == over first swap dup
1230 R1 == cons roll> [T>] [E] [T<] cmp
1231 BTree-Delete == [pop not] swap [R0] [R1] genrec''', D)
1232 ```
1233
1234
1235 ```python
1236 J("['a' 23 [] ['b' 88 [] ['c' 44 [] []]]] 'c' ['Er'] BTree-Delete ")
1237 ```
1238
1239     ['a' 23 [] ['b' 88 [] []]]
1240
1241
1242
1243 ```python
1244 J("['a' 23 [] ['b' 88 [] ['c' 44 [] []]]] 'b' ['Er'] BTree-Delete ")
1245 ```
1246
1247     ['a' 23 [] ['c' 44 [] []]]
1248
1249
1250
1251 ```python
1252 J("['a' 23 [] ['b' 88 [] ['c' 44 [] []]]] 'a' ['Er'] BTree-Delete ")
1253 ```
1254
1255     ['b' 88 [] ['c' 44 [] []]]
1256
1257
1258
1259 ```python
1260 J("['a' 23 [] ['b' 88 [] ['c' 44 [] []]]] 'der' ['Er'] BTree-Delete ")
1261 ```
1262
1263     ['a' 23 [] ['b' 88 [] ['c' 44 [] 'Er' 'der' []]]]
1264
1265
1266
1267 ```python
1268 J("['a' 23 [] ['b' 88 [] ['c' 44 [] []]]] 'der' [pop] BTree-Delete ")
1269 ```
1270
1271     ['a' 23 [] ['b' 88 [] ['c' 44 [] []]]]
1272
1273
1274 One bug, I forgot to put `not` in the first two clauses of the `cond`.
1275
1276 The behavior of the `[Er]` function should maybe be different: either just silently fail, or maybe implement some sort of function that can grab the pending expression up to a sentinel value or something, allowing for a kind of "except"-ish control-flow?
1277
1278 Then, once we have add, get, and delete we can see about abstracting them.
1279
1280
1281 # Tree with node and list of trees.
1282 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 and a sequence of zero or more child trees.  (The asterisk is meant to indicate the [Kleene star](https://en.wikipedia.org/wiki/Kleene_star).)
1283
1284     tree = [] | [node [tree*]]
1285
1286 ### `treestep`
1287 In the spirit of `step` we are going to define a combinator `treestep` which expects a tree and three additional items: a base-case value `z`, and two quoted programs `[C]` and `[N]`.
1288
1289     tree z [C] [N] treestep
1290
1291 If the current tree node is empty then just leave `z` on the stack in lieu:
1292
1293        [] z [C] [N] treestep
1294     ---------------------------
1295           z
1296
1297 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`.
1298
1299        [node [tree*]] z [C] [N] treestep
1300     --------------------------------------- w/ K == z [C] [N] treestep
1301            node N [tree*] [K] map C
1302
1303 ### Derive the recursive form.
1304 Since this is a recursive function, we can begin to derive it by finding the `ifte` stage that `genrec` will produce.  The predicate and base-case functions are trivial, so we just have to derive `J`.
1305
1306     K == [not] [pop z] [J] ifte
1307
1308 The behavior of `J` is to accept a (non-empty) tree node and arrive at the desired outcome.
1309
1310            [node [tree*]] J
1311     ------------------------------
1312        node N [tree*] [K] map C
1313
1314 So `J` will have some form like:
1315
1316     J == .. [N] .. [K] .. [C] ..
1317
1318 Let's dive in.  First, unquote the node and `dip` `N`.
1319
1320     [node [tree*]] i [N] dip
1321      node [tree*]    [N] dip
1322     node N [tree*]
1323
1324 Next, `map` `K` over teh child trees and combine with `C`.
1325
1326     node N [tree*] [K] map C
1327     node N [tree*] [K] map C
1328     node N [K.tree*]       C
1329
1330 So:
1331
1332     J == i [N] dip [K] map C
1333
1334 Plug it in and convert to `genrec`:
1335
1336     K == [not] [pop z] [i [N] dip [K] map C] ifte
1337     K == [not] [pop z] [i [N] dip]   [map C] genrec
1338
1339 ### Extract the givens to parameterize the program.
1340
1341     [not] [pop z] [i [N] dip]   [map C] genrec
1342
1343     [not] [pop z]                   [i [N] dip] [map C] genrec
1344     [not] [z]         [pop] swoncat [i [N] dip] [map C] genrec
1345     [not]  z     unit [pop] swoncat [i [N] dip] [map C] genrec
1346     z [not] swap unit [pop] swoncat [i [N] dip] [map C] genrec
1347       \  .........TS0............./
1348        \/
1349     z TS0 [i [N] dip]                       [map C] genrec
1350     z     [i [N] dip]             [TS0] dip [map C] genrec
1351     z       [[N] dip] [i] swoncat [TS0] dip [map C] genrec
1352     z  [N] [dip] cons [i] swoncat [TS0] dip [map C] genrec
1353            \  ......TS1........./
1354             \/
1355     z [N] TS1 [TS0] dip [map C]                      genrec
1356     z [N]               [map C]  [TS1 [TS0] dip] dip genrec
1357     z [N] [C]      [map] swoncat [TS1 [TS0] dip] dip genrec
1358     z [C] [N] swap [map] swoncat [TS1 [TS0] dip] dip genrec
1359
1360 The givens are all to the left so we have our definition.
1361
1362 ### Define `treestep`
1363          TS0 == [not] swap unit [pop] swoncat
1364          TS1 == [dip] cons [i] swoncat
1365     treestep == swap [map] swoncat [TS1 [TS0] dip] dip genrec
1366
1367
1368 ```python
1369 DefinitionWrapper.add_definitions('''
1370
1371      TS0 == [not] swap unit [pop] swoncat
1372      TS1 == [dip] cons [i] swoncat
1373 treestep == swap [map] swoncat [TS1 [TS0] dip] dip genrec
1374
1375 ''', D)
1376 ```
1377
1378        [] 0 [C] [N] treestep
1379     ---------------------------
1380           0
1381
1382
1383           [n [tree*]] 0 [sum +] [] treestep
1384        --------------------------------------------------
1385            n [tree*] [0 [sum +] [] treestep] map sum +
1386
1387
1388 ```python
1389 J('[] 0 [sum +] [] treestep')
1390 ```
1391
1392     0
1393
1394
1395
1396 ```python
1397 J('[23 []] 0 [sum +] [] treestep')
1398 ```
1399
1400     23
1401
1402
1403
1404 ```python
1405 J('[23 [[2 []] [3 []]]] 0 [sum +] [] treestep')
1406 ```
1407
1408     28
1409
1410
1411 ## A slight modification.
1412 Let's simplify the tree datastructure definition slightly by just letting the children be the `rest` of the tree:
1413
1414     tree = [] | [node tree*]
1415
1416 The `J` function changes slightly.
1417
1418             [node tree*] J
1419     ------------------------------
1420        node N [tree*] [K] map C
1421
1422
1423     [node tree*] uncons [N] dip [K] map C
1424     node [tree*]        [N] dip [K] map C
1425     node N [tree*]              [K] map C
1426     node N [tree*]              [K] map C
1427     node N [K.tree*]                    C
1428
1429     J == uncons [N] dip [K] map C
1430
1431     K == [not] [pop z] [uncons [N] dip] [map C] genrec
1432
1433
1434
1435 ```python
1436 define('TS1 == [dip] cons [uncons] swoncat')  # We only need to redefine one word.
1437 ```
1438
1439
1440 ```python
1441 J('[23 [2] [3]] 0 [sum +] [] treestep')
1442 ```
1443
1444     28
1445
1446
1447
1448 ```python
1449 J('[23 [2 [8] [9]] [3] [4 []]] 0 [sum +] [] treestep')
1450 ```
1451
1452     49
1453
1454
1455 I think these trees seem a little easier to read.
1456
1457 ## Redefining our BTree in terms of this form.
1458
1459     BTree = [] | [[key value] left right]
1460
1461 What kind of functions can we write for this with our `treestep`?  The pattern for processing a non-empty node is:
1462
1463     node N [tree*] [K] map C
1464
1465 Plugging in our BTree structure:
1466
1467     [key value] N [left right] [K] map C
1468
1469
1470     [key value] uncons pop [left right] [K] map i
1471     key [value]        pop [left right] [K] map i
1472     key                    [left right] [K] map i
1473     key                    [lkey rkey ]         i
1474     key                     lkey rkey
1475
1476
1477
1478 ```python
1479 J('[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]]   23 [i] [uncons pop] treestep')
1480 ```
1481
1482     3 23 23
1483
1484
1485 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.
1486
1487
1488     [key value] N     [left right] [K] map C
1489
1490     [key value] first [left right] [K] map flatten cons
1491     key               [left right] [K] map flatten cons
1492     key               [[lk] [rk] ]         flatten cons
1493     key               [ lk   rk  ]                 cons
1494                       [key  lk   rk  ]
1495
1496 So:
1497
1498     [] [flatten cons] [first] treestep
1499
1500
1501 ```python
1502 J('[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]]   [] [flatten cons] [first] treestep')
1503 ```
1504
1505     [3 2 9 5 4 8 6 7]
1506
1507
1508 There we go.
1509 #### In-order traversal with `treestep`.
1510
1511 From here:
1512
1513     key [[lk] [rk]] C
1514     key [[lk] [rk]] i
1515     key  [lk] [rk] roll<
1516     [lk] [rk] key swons concat
1517     [lk] [key rk]       concat
1518     [lk   key rk]
1519
1520 So:
1521
1522     [] [i roll< swons concat] [first] treestep
1523
1524
1525 ```python
1526 J('[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]]   [] [i roll< swons concat] [uncons pop] treestep')
1527 ```
1528
1529     [2 3 4 5 6 7 8 9]
1530
1531
1532 ## Miscellaneous Crap
1533
1534 ### Toy with it.
1535 Let's reexamine:
1536
1537     [key value left right] R0 [BTree-iter-order] R1
1538         ...
1539     left BTree-iter-order key value F right BTree-iter-order
1540
1541
1542     [key value left right] unstack swap
1543      key value left right               swap
1544      key value right left
1545
1546     key value right left [BTree-iter-order] [cons dipdd] dupdip
1547     key value right left [BTree-iter-order] cons dipdd [BTree-iter-order]
1548     key value right [left BTree-iter-order]      dipdd [BTree-iter-order]
1549     left BTree-iter-order key value right              [BTree-iter-order]
1550
1551     left BTree-iter-order key value   right [F] dip [BTree-iter-order]
1552     left BTree-iter-order key value F right         [BTree-iter-order] i
1553     left BTree-iter-order key value F right          BTree-iter-order
1554
1555 So:
1556
1557     R0 == unstack swap
1558     R1 == [cons dipdd [F] dip] dupdip i
1559
1560     [key value left right] R0                [BTree-iter-order] R1
1561     [key value left right] unstack swap [BTree-iter-order] [cons dipdd [F] dip] dupdip i
1562      key value right left                    [BTree-iter-order] [cons dipdd [F] dip] dupdip i
1563
1564      key value right left [BTree-iter-order] cons dipdd [F] dip [BTree-iter-order] i
1565      key value right [left BTree-iter-order]      dipdd [F] dip [BTree-iter-order] i
1566      left BTree-iter-order key value   right            [F] dip [BTree-iter-order] i
1567      left BTree-iter-order key value F right                    [BTree-iter-order] i
1568      left BTree-iter-order key value F right                     BTree-iter-order
1569
1570
1571     BTree-iter-order == [not] [pop] [unstack swap] [[cons dipdd [F] dip] dupdip i] genrec
1572
1573 #### Refactor `cons cons`
1574     cons2 == cons cons
1575
1576 Refactoring:
1577
1578     BTree-new == swap [[] []] cons2
1579     T == [cons2 dipdd] cons2 cons infra
1580     Te == [cons2 dipd] cons2 cons infra
1581     Ee == pop swap roll< rest rest cons2
1582
1583 It's used a lot because it's tied to the fact that there are two "data items" in each node.  This point to a more general factorization that would render a combinator that could work for other geometries of trees.
1584
1585 ## A General Form for Trees
1586 A general form for tree data with N children per node:
1587
1588     [[data] [child0] ... [childN-1]]
1589
1590 Suggests a general form of recursive iterator, but I have to go walk the dogs at the mo'.
1591
1592 For a given structure, you would have a structure of operator functions and sort of merge them and run them, possibly in a different order (pre- post- in- y'know).  The `Cn` functions could all be the same and use the `step` trick if the children nodes are all of the right kind.  If they are heterogeneous then we need a way to get the different `Cn` into the structure in the right order.  If I understand correctly, the "Bananas..." paper shows how to do this automatically from a type description.  They present, if I have it right, a tiny machine that accepts [some sort of algebraic data type description and returns a function that can recusre over it](https://en.wikipedia.org/wiki/Catamorphism#General_case), I think.
1593
1594        [data.. [c0] [c1] ... [cN]] [F C0 C1 ... CN] infil
1595     --------------------------------------------------------
1596        data F [c0] C0 [c1] C1 ... [cN] CN
1597
1598
1599
1600 #### Just make `[F]` a parameter.
1601 We can generalize to a sort of pure form:
1602
1603     BTree-iter == [not] [pop] [[F]]            [R1] genrec
1604                == [not] [pop] [[F] [BTree-iter] R1] ifte
1605
1606 Putting `[F]` to the left as a given:
1607
1608      [F] unit [not] [pop] roll< [R1] genrec
1609     [[F]]     [not] [pop] roll< [R1] genrec
1610               [not] [pop] [[F]] [R1] genrec
1611
1612 Let's us define a parameterized form:
1613
1614     BTree-iter == unit [not] [pop] roll< [R1] genrec
1615
1616 So in the general case of non-empty nodes:
1617
1618     [key value left right] [F] [BTree-iter] R1
1619
1620 We just define `R1` to do whatever it has to to process the node.  For example:
1621
1622     [key value left right] [F] [BTree-iter] R1
1623         ...
1624     key value F   left BTree-iter   right BTree-iter
1625     left BTree-iter   key value F   right BTree-iter
1626     left BTree-iter   right BTree-iter   key value F
1627
1628 Pre-, ??-, post-order traversals.
1629
1630     [key value  left right] uncons uncons
1631      key value [left right]
1632
1633 For pre- and post-order we can use the `step` trick:
1634
1635     [left right] [BTree-iter] step
1636         ...
1637     left BTree-iter right BTree-iter
1638
1639 We worked out one scheme for ?in-order? traversal above, but maybe we can do better?
1640
1641     [key value left right]              [F] [BTree-iter] [unstack] dipd
1642     [key value left right] unstack [F] [BTree-iter]
1643      key value left right               [F] [BTree-iter]
1644
1645     key value left right [F] [BTree-iter] R1.1
1646
1647 Hmm...
1648
1649     key value left right              [F] [BTree-iter] tuck
1650     key value left right [BTree-iter] [F] [BTree-iter]
1651
1652
1653     [key value left right]                          [F] [BTree-iter] [unstack [roll>] dip] dipd
1654     [key value left right] unstack [roll>] dip [F] [BTree-iter]
1655      key value left right               [roll>] dip [F] [BTree-iter]
1656      key value left roll> right                     [F] [BTree-iter]
1657      left key value right                           [F] [BTree-iter]
1658
1659     left            key value   right              [F] [BTree-iter] tuck foo
1660     left            key value   right [BTree-iter] [F] [BTree-iter] foo
1661         ...
1662     left BTree-iter key value F right  BTree-iter
1663
1664 We could just let `[R1]` be a parameter too, for maximum flexibility.
1665
1666 #### Automatically deriving the recursion combinator for a data type?
1667
1668 If I understand it correctly, the "Bananas..." paper talks about a way to build the processor function automatically from the description of the type.  I think if we came up with an elegant way for the Joy code to express that, it would be cool.  In Joypy the definitions can be circular because lookup happens at evaluation, not parsing.  E.g.:
1669
1670     A == ... B ...
1671     B == ... A ...
1672
1673 That's fine.  Circular datastructures can't be made though.
1674
1675
1676
1677
1678 ```python
1679
1680 ```
1681
1682
1683 ```python
1684
1685 ```
1686
1687
1688 ```python
1689
1690 ```
1691
1692
1693 ```python
1694
1695 ```
1696
1697
1698 ```python
1699
1700 ```
1701
1702
1703 ```python
1704
1705 ```
1706
1707
1708 ```python
1709
1710 ```
1711
1712
1713 ```python
1714
1715 ```
1716
1717
1718 ```python
1719
1720 ```
1721
1722
1723 ```python
1724
1725 ```
1726
1727
1728 ```python
1729
1730 ```
1731
1732
1733 ```python
1734
1735 ```