docs/Treestep.md

   1 # Treating Trees II: `treestep`
   2 Let's consider a tree structure, similar to one described ["Why functional programming matters" by John Hughes](https://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf), that consists of a node value followed by zero or more child trees.  (The asterisk is meant to indicate the [Kleene star](https://en.wikipedia.org/wiki/Kleene_star).)
   3
   4     tree = [] | [node tree*]
   5
   6 In the spirit of `step` we are going to define a combinator `treestep` which expects a tree and three additional items: a base-case function `[B]`, and two quoted programs `[N]` and `[C]`.
   7
   8     tree [B] [N] [C] treestep
   9
  10 If the current tree node is empty then just execute `B`:
  11
  12        [] [B] [N] [C] treestep
  13     ---------------------------
  14        []  B
  15
  16 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`.
  17
  18        [node tree*] [B] [N] [C] treestep
  19     --------------------------------------- w/ K == [B] [N] [C] treestep
  20            node N [tree*] [K] map C
  21
  22 (Later on we'll experiment with making `map` part of `C` so you can use other combinators.)
  23
  24 ## Derive the recursive function.
  25 We can begin to derive it by finding the `ifte` stage that `genrec` will produce.
  26
  27     K == [not] [B] [R0]   [R1] genrec
  28       == [not] [B] [R0 [K] R1] ifte
  29
  30 So we just have to derive `J`:
  31
  32     J == R0 [K] R1
  33
  34 The behavior of `J` is to accept a (non-empty) tree node and arrive at the desired outcome.
  35
  36            [node tree*] J
  37     ------------------------------
  38        node N [tree*] [K] map C
  39
  40 So `J` will have some form like:
  41
  42     J == ... [N] ... [K] ... [C] ...
  43
  44 Let's dive in.  First, unquote the node and `dip` `N`.
  45
  46     [node tree*] uncons [N] dip
  47     node [tree*]        [N] dip
  48     node N [tree*]
  49
  50 Next, `map` `K` over the child trees and combine with `C`.
  51
  52     node N [tree*] [K] map C
  53     node N [tree*] [K] map C
  54     node N [K.tree*]       C
  55
  56 So:
  57
  58     J == uncons [N] dip [K] map C
  59
  60 Plug it in and convert to `genrec`:
  61
  62     K == [not] [B] [J                       ] ifte
  63       == [not] [B] [uncons [N] dip [K] map C] ifte
  64       == [not] [B] [uncons [N] dip]   [map C] genrec
  65
  66 ## Extract the givens to parameterize the program.
  67 Working backwards:
  68
  69     [not] [B]          [uncons [N] dip]                  [map C] genrec
  70     [B] [not] swap     [uncons [N] dip]                  [map C] genrec
  71     [B]                [uncons [N] dip] [[not] swap] dip [map C] genrec
  72                                         ^^^^^^^^^^^^^^^^
  73     [B] [[N] dip]      [uncons] swoncat [[not] swap] dip [map C] genrec
  74     [B] [N] [dip] cons [uncons] swoncat [[not] swap] dip [map C] genrec
  75             ^^^^^^^^^^^^^^^^^^^^^^^^^^^
  76
  77 Extract a couple of auxiliary definitions:
  78
  79     TS.0 == [[not] swap] dip
  80     TS.1 == [dip] cons [uncons] swoncat
  81
  82     [B] [N] TS.1 TS.0 [map C]                         genrec
  83     [B] [N]           [map C]         [TS.1 TS.0] dip genrec
  84     [B] [N] [C]         [map] swoncat [TS.1 TS.0] dip genrec
  85
  86 The givens are all to the left so we have our definition.
  87
  88 ### (alternate) Extract the givens to parameterize the program.
  89 Working backwards:
  90
  91     [not] [B]           [uncons [N] dip]            [map C] genrec
  92     [not] [B] [N]       [dip] cons [uncons] swoncat [map C] genrec
  93     [B] [N] [not] roll> [dip] cons [uncons] swoncat [map C] genrec
  94             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  95
  96 ## Define `treestep`
  97
  98
  99 ```python
 100 from notebook_preamble import D, J, V, define, DefinitionWrapper
 101 ```
 102
 103
 104 ```python
 105 DefinitionWrapper.add_definitions('''
 106
 107     _treestep_0 == [[not] swap] dip
 108     _treestep_1 == [dip] cons [uncons] swoncat
 109     treegrind == [_treestep_1 _treestep_0] dip genrec
 110     treestep == [map] swoncat treegrind
 111
 112 ''', D)
 113 ```
 114
 115 ## Examples
 116 Consider trees, the nodes of which are integers.  We can find the sum of all nodes in a tree with this function:
 117
 118     sumtree == [pop 0] [] [sum +] treestep
 119
 120
 121 ```python
 122 define('sumtree == [pop 0] [] [sum +] treestep')
 123 ```
 124
 125 Running this function on an empty tree value gives zero:
 126
 127        [] [pop 0] [] [sum +] treestep
 128     ------------------------------------
 129                0
 130
 131
 132 ```python
 133 J('[] sumtree')  # Empty tree.
 134 ```
 135
 136     0
 137
 138
 139 Running it on a non-empty node:
 140
 141     [n tree*]  [pop 0] [] [sum +] treestep
 142     n [tree*] [[pop 0] [] [sum +] treestep] map sum +
 143     n [ ... ]                                   sum +
 144     n m                                             +
 145     n+m
 146
 147
 148
 149 ```python
 150 J('[23] sumtree')  # No child trees.
 151 ```
 152
 153     23
 154
 155
 156
 157 ```python
 158 J('[23 []] sumtree')  # Child tree, empty.
 159 ```
 160
 161     23
 162
 163
 164
 165 ```python
 166 J('[23 [2 [4]] [3]] sumtree')  # Non-empty child trees.
 167 ```
 168
 169     32
 170
 171
 172
 173 ```python
 174 J('[23 [2 [8] [9]] [3] [4 []]] sumtree')  # Etc...
 175 ```
 176
 177     49
 178
 179
 180
 181 ```python
 182 J('[23 [2 [8] [9]] [3] [4 []]] [pop 0] [] [cons sum] treestep')  # Alternate "spelling".
 183 ```
 184
 185     49
 186
 187
 188
 189 ```python
 190 J('[23 [2 [8] [9]] [3] [4 []]] [] [pop 23] [cons] treestep')  # Replace each node.
 191 ```
 192
 193     [23 [23 [23] [23]] [23] [23 []]]
 194
 195
 196
 197 ```python
 198 J('[23 [2 [8] [9]] [3] [4 []]] [] [pop 1] [cons] treestep')
 199 ```
 200
 201     [1 [1 [1] [1]] [1] [1 []]]
 202
 203
 204
 205 ```python
 206 J('[23 [2 [8] [9]] [3] [4 []]] [] [pop 1] [cons] treestep sumtree')
 207 ```
 208
 209     6
 210
 211
 212
 213 ```python
 214 J('[23 [2 [8] [9]] [3] [4 []]] [pop 0] [pop 1] [sum +] treestep')  # Combine replace and sum into one function.
 215 ```
 216
 217     6
 218
 219
 220
 221 ```python
 222 J('[4 [3 [] [7]]] [pop 0] [pop 1] [sum +] treestep')  # Combine replace and sum into one function.
 223 ```
 224
 225     3
 226
 227
 228 ## Redefining the Ordered Binary Tree in terms of `treestep`.
 229
 230     Tree = [] | [[key value] left right]
 231
 232 What kind of functions can we write for this with our `treestep`?
 233
 234 The pattern for processing a non-empty node is:
 235
 236     node N [tree*] [K] map C
 237
 238 Plugging in our BTree structure:
 239
 240     [key value] N [left right] [K] map C
 241
 242 ### Traversal
 243     [key value] first [left right] [K] map i
 244     key [value]       [left right] [K] map i
 245     key               [left right] [K] map i
 246     key               [lkey rkey ]         i
 247     key                lkey rkey
 248
 249 This doesn't quite work:
 250
 251
 252 ```python
 253 J('[[3 0] [[2 0] [][]] [[9 0] [[5 0] [[4 0] [][]] [[8 0] [[6 0] [] [[7 0] [][]]][]]][]]] ["B"] [first] [i] treestep')
 254 ```
 255
 256     3 'B' 'B'
 257
 258
 259 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.
 260
 261
 262     [key value] N     [left right] [K] map C
 263
 264     [key value] first [left right] [K] map flatten cons
 265     key               [left right] [K] map flatten cons
 266     key               [[lk] [rk] ]         flatten cons
 267     key               [ lk   rk  ]                 cons
 268                       [key  lk   rk  ]
 269
 270 So:
 271
 272     [] [first] [flatten cons] treestep
 273
 274
 275 ```python
 276 J('[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]]   [] [first] [flatten cons] treestep')
 277 ```
 278
 279     [3 2 9 5 4 8 6 7]
 280
 281
 282 There we go.
 283
 284 ### In-order traversal
 285
 286 From here:
 287
 288     key [[lk] [rk]] C
 289     key [[lk] [rk]] i
 290     key  [lk] [rk] roll<
 291     [lk] [rk] key swons concat
 292     [lk] [key rk]       concat
 293     [lk   key rk]
 294
 295 So:
 296
 297     [] [i roll< swons concat] [first] treestep
 298
 299
 300 ```python
 301 J('[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]]   [] [uncons pop] [i roll< swons concat] treestep')
 302 ```
 303
 304     [2 3 4 5 6 7 8 9]
 305
 306
 307 ## With `treegrind`?
 308 The `treegrind` function doesn't include the `map` combinator, so the `[C]` function must arrange to use some combinator on the quoted recursive copy `[K]`.  With this function, the pattern for processing a non-empty node is:
 309
 310     node N [tree*] [K] C
 311
 312 Plugging in our BTree structure:
 313
 314     [key value] N [left right] [K] C
 315
 316
 317 ```python
 318 J('[["key" "value"] ["left"] ["right"] ] ["B"] ["N"] ["C"] treegrind')
 319 ```
 320
 321     ['key' 'value'] 'N' [['left'] ['right']] [[not] ['B'] [uncons ['N'] dip] ['C'] genrec] 'C'
 322
 323
 324 ## `treegrind` with `step`
 325
 326 Iteration through the nodes
 327
 328
 329 ```python
 330 J('[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]]   [pop] ["N"] [step] treegrind')
 331 ```
 332
 333     [3 0] 'N' [2 0] 'N' [9 0] 'N' [5 0] 'N' [4 0] 'N' [8 0] 'N' [6 0] 'N' [7 0] 'N'
 334
 335
 336 Sum the nodes' keys.
 337
 338
 339 ```python
 340 J('0 [[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]]   [pop] [first +] [step] treegrind')
 341 ```
 342
 343     44
 344
 345
 346 Rebuild the tree using `map` (imitating `treestep`.)
 347
 348
 349 ```python
 350 J('[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]]   [] [[100 +] infra] [map cons] treegrind')
 351 ```
 352
 353     [[103 0] [[102 0] [] []] [[109 0] [[105 0] [[104 0] [] []] [[108 0] [[106 0] [] [[107 0] [] []]] []]] []]]
 354
 355
 356 ## Do we have the flexibility to reimplement `Tree-get`?
 357 I think we do:
 358
 359     [B] [N] [C] treegrind
 360
 361 We'll start by saying that the base-case (the key is not in the tree) is user defined, and the per-node function is just the query key literal:
 362
 363     [B] [query_key] [C] treegrind
 364
 365 This means we just have to define `C` from:
 366
 367     [key value] query_key [left right] [K] C
 368
 369
 370 Let's try `cmp`:
 371
 372     C == P [T>] [E] [T<] cmp
 373
 374     [key value] query_key [left right] [K] P [T>] [E] [T<] cmp
 375
 376 ### The predicate `P`
 377 Seems pretty easy (we must preserve the value in case the keys are equal):
 378
 379     [key value] query_key [left right] [K] P
 380     [key value] query_key [left right] [K] roll<
 381     [key value] [left right] [K] query_key       [roll< uncons swap] dip
 382
 383     [key value] [left right] [K] roll< uncons swap query_key
 384     [left right] [K] [key value]       uncons swap query_key
 385     [left right] [K] key [value]              swap query_key
 386     [left right] [K] [value] key                   query_key
 387
 388     P == roll< [roll< uncons swap] dip
 389
 390 (Possibly with a swap at the end?  Or just swap `T<` and `T>`.)
 391
 392 So now:
 393
 394     [left right] [K] [value] key query_key [T>] [E] [T<] cmp
 395
 396 Becomes one of these three:
 397
 398     [left right] [K] [value] T>
 399     [left right] [K] [value] E
 400     [left right] [K] [value] T<
 401
 402
 403 ### `E`
 404 Easy.
 405
 406     E == roll> popop first
 407
 408 ### `T<` and `T>`
 409
 410     T< == pop [first] dip i
 411     T> == pop [second] dip i
 412
 413 ## Putting it together
 414
 415
 416     T> == pop [first] dip i
 417     T< == pop [second] dip i
 418     E == roll> popop first
 419     P == roll< [roll< uncons swap] dip
 420
 421     Tree-get == [P [T>] [E] [T<] cmp] treegrind
 422
 423 To me, that seems simpler than the `genrec` version.
 424
 425
 426 ```python
 427 DefinitionWrapper.add_definitions('''
 428
 429     T> == pop [first] dip i
 430     T< == pop [second] dip i
 431     E == roll> popop first
 432     P == roll< [roll< uncons swap] dip
 433
 434     Tree-get == [P [T>] [E] [T<] cmp] treegrind
 435
 436 ''', D)
 437 ```
 438
 439
 440 ```python
 441 J('''\
 442
 443 [[3 13] [[2 12] [] []] [[9 19] [[5 15] [[4 14] [] []] [[8 18] [[6 16] [] [[7 17] [] []]] []]] []]]
 444
 445 [] [5] Tree-get
 446
 447 ''')
 448 ```
 449
 450     15
 451
 452
 453
 454 ```python
 455 J('''\
 456
 457 [[3 13] [[2 12] [] []] [[9 19] [[5 15] [[4 14] [] []] [[8 18] [[6 16] [] [[7 17] [] []]] []]] []]]
 458
 459 [pop "nope"] [25] Tree-get
 460
 461 ''')
 462 ```
 463
 464     'nope'
 465