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.
4 The basic structure, in a [crude type notation](https://en.wikipedia.org/wiki/Algebraic_data_type), is:
6 BTree :: [] | [key value BTree BTree]
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.
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.
14 The stopping predicate just has to detect the empty list:
16 BTree-iter == [not] [E] [R0] [R1] genrec
18 And since there's nothing at this node, we just `pop` it:
20 BTree-iter == [not] [pop] [R0] [R1] genrec
22 #### Node case `[key value left right]`
23 Now we need to figure out `R0` and `R1`:
25 BTree-iter == [not] [pop] [R0] [R1] genrec
26 == [not] [pop] [R0 [BTree-iter] R1] ifte
28 Let's look at it *in situ*:
30 [key value left right] R0 [BTree-iter] R1
32 #### Processing the current node.
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:
36 [key value left right] [F] dupdip [BTree-iter] R1
37 [key value left right] F [key value left right] [BTree-iter] R1
39 For example, if we're getting all the keys `F` would be `first`:
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
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:
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]
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
65 R1 == [rest rest] dip step
67 #### Putting it together
70 BTree-iter == [not] [pop] [[F] dupdip] [[rest rest] dip step] genrec
72 When I was reading this over I realized `rest rest` could go in `R0`:
74 BTree-iter == [not] [pop] [[F] dupdip rest rest] [step] genrec
76 (And `[step] genrec` is such a cool and suggestive combinator!)
78 #### Parameterizing the `F` per-node processing function.
80 [F] BTree-iter == [not] [pop] [[F] dupdip rest rest] [step] genrec
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
90 BTree-iter == [not] [pop] roll< [dupdip rest rest] cons [step] genrec
94 from notebook_preamble import D, J, V, define, DefinitionWrapper
99 define('BTree-iter == [not] [pop] roll< [dupdip rest rest] cons [step] genrec')
104 J('[] [23] BTree-iter') # It doesn't matter what F is as it won't be used.
112 J('["tommy" 23 [] []] [first] BTree-iter')
120 J('["tommy" 23 ["richard" 48 [] []] ["jenny" 18 [] []]] [first] BTree-iter')
123 'tommy' 'richard' 'jenny'
128 J('["tommy" 23 ["richard" 48 [] []] ["jenny" 18 [] []]] [second] BTree-iter')
134 # Adding Nodes to the BTree
135 Let's consider adding nodes to a BTree structure.
137 BTree value key BTree-add == BTree
139 #### Adding to an empty node.
140 If the current node is `[]` then you just return `[key value [] []]`:
142 BTree-add == [popop not] [[pop] dipd BTree-new] [R0] [R1] genrec
144 Where `BTree-new` is:
146 value key BTree-new == [key value [] []]
148 value key swap [[] []] cons cons
149 key value [[] []] cons cons
150 key [value [] []] cons
153 BTree-new == swap [[] []] cons cons
157 define('BTree-new == swap [[] []] cons cons')
162 V('"v" "k" BTree-new')
168 'v' 'k' . swap [[] []] cons cons
169 'k' 'v' . [[] []] cons cons
170 'k' 'v' [[] []] . cons cons
171 'k' ['v' [] []] . cons
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.)
177 #### If the current node isn't empty.
179 We now have to derive `R0` and `R1`, consider:
181 [key_n value_n left right] value key R0 [BTree-add] R1
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.
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`:
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
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 >
200 P > == pop roll> pop first >
201 P < == pop roll> pop first <
202 P == pop roll> pop first
206 define('P == pop roll> pop first')
211 V('["k" "v" [] []] "vv" "kk" [0] P >')
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 >
227 #### If the key we're adding is greater than the node's key.
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:
231 [key_n value_n left right] value key [BTree-add] T == [key_n value_n left (BTree-add key value right)]
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:
236 right left value_n key_n value key [BTree-add] K
238 right value key BTree-add left value_n key_n
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
252 [key_n value_n left right] [value key [BTree-add] K] infra
255 So now we're at getting from this to this:
257 [key_n value_n left right] value key [BTree-add] T
259 [key_n value_n left right] [value key [BTree-add] K] infra
263 value key [BTree-add] T == [value key [BTree-add] K] infra
264 T == [ K] cons cons cons infra
268 define('K == cons cons dipdd')
269 define('T == [K] cons cons cons infra')
274 V('"r" "l" "v" "k" "vv" "kk" [0] K')
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' .
299 V('["k" "v" "l" "r"] "vv" "kk" [0] T')
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'] .
330 #### If the key we're adding is less than the node's key.
331 This is very very similar to the above:
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
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`:
338 Te == [cons cons dipd] cons cons cons infra
340 This suggests an alternate factorization:
343 T == [ccons dipdd] ccons cons infra
344 Te == [ccons dipd] ccons cons infra
350 define('Te == [cons cons dipd] cons cons cons infra')
355 V('["k" "v" "l" "r"] "vv" "kk" [0] Te')
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'] .
384 #### Else the keys must be equal.
385 This means we must find:
387 [key_n value_n left right] value key [BTree-add] Ee
389 [key value left right]
391 This is another easy one:
393 Ee == pop swap roll< rest rest cons cons
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]
404 define('Ee == pop swap roll< rest rest cons cons')
409 V('["k" "v" "l" "r"] "vv" "k" [0] Ee')
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
429 define('E == [P <] [Te] [Ee] ifte')
432 #### Now we can define `BTree-add`
433 BTree-add == [popop not] [[pop] dipd BTree-new] [] [[P >] [T] [E] ifte] genrec
435 Putting it all together:
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
444 BTree-add == [popop not] [[pop] dipd BTree-new] [] [[P >] [T] [E] ifte] genrec
448 define('BTree-add == [popop not] [[pop] dipd BTree-new] [] [[P >] [T] [E] ifte] genrec')
453 J('[] 23 "b" BTree-add') # Initial
461 J('["b" 23 [] []] 88 "c" BTree-add') # Less than
464 ['b' 23 [] ['c' 88 [] []]]
469 J('["b" 23 [] []] 88 "a" BTree-add') # Greater than
472 ['b' 23 ['a' 88 [] []] []]
477 J('["b" 23 [] []] 88 "b" BTree-add') # Equal to
485 J('[] 23 "a" BTree-add 88 "b" BTree-add 44 "c" BTree-add') # Series.
488 ['a' 23 [] ['b' 88 [] ['c' 44 [] []]]]
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.
495 J('[] [3 9 5 2 8 6 7 8 4] [0 swap BTree-add] step')
498 [3 0 [2 0 [] []] [9 0 [5 0 [4 0 [] []] [8 0 [6 0 [] [7 0 [] []]] []]] []]]
503 define('to_set == [] swap [0 swap BTree-add] step')
508 J('[3 9 5 2 8 6 7 8 4] to_set')
511 [3 0 [2 0 [] []] [9 0 [5 0 [4 0 [] []] [8 0 [6 0 [] [7 0 [] []]] []]] []]]
514 And with that we can write a little program to remove duplicate items from a list.
518 define('unique == [to_set [first] BTree-iter] cons run')
523 J('[3 9 3 5 2 9 8 8 8 6 2 7 8 4 3] unique') # Filter duplicate items.
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:
533 ------------------------- a > b
537 ------------------------- a = b
541 ------------------------- a < b
544 We need a new non-destructive predicate `P`:
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
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
557 P == over [popop popop first] nullary
559 Here are the definitions again, pruned and renamed in some cases:
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
567 Using `cmp` to simplify [our code above at `R1`](#If-the-current-node-isn't-empty.):
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
572 The line above becomes one of the three lines below:
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<
578 The definition is a little longer but, I think, more elegant and easier to understand:
580 BTree-add == [popop not] [[pop] dipd BTree-new] [] [P [T>] [E] [T<] cmp] genrec
585 from joy.library import FunctionWrapper
586 from joy.utils.stack import concat
587 from notebook_preamble import D
591 def cmp_(stack, expression, dictionary):
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:
597 ------------------------- a > b
601 ------------------------- a = b
605 ------------------------- a < b
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
618 from joy.library import FunctionWrapper, S_ifte
622 def cond(stack, expression, dictionary):
624 like a case statement; works by rewriting into a chain of ifte.
626 [..[[Bi] Ti]..[D]] -> ...
629 [[[B0] T0] [[B1] T1] [D]] cond
630 -----------------------------------------
631 [B0] [T0] [[B1] [T1] [D] ifte] ifte
634 conditions, stack = stack
636 expression = _cond(conditions, expression)
638 # Attempt to preload the args to first ifte.
639 (P, (T, (E, expression))) = expression
641 # If, for any reason, the argument to cond should happen to contain
642 # only the default clause then this optimization will fail.
645 stack = (E, (T, (P, stack)))
646 return stack, expression, dictionary
649 def _cond(conditions, expression):
650 (clause, rest) = conditions
651 if not rest: # clause is [D]
654 return (P, (T, (_cond(rest, ()), (S_ifte, expression))))
663 J("1 0 ['G'] ['E'] ['L'] cmp")
671 J("1 1 ['G'] ['E'] ['L'] cmp")
679 J("0 1 ['G'] ['E'] ['L'] cmp")
687 from joy.library import DefinitionWrapper
690 DefinitionWrapper.add_definitions('''
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
697 BTree-add == [popop not] [[pop] dipd BTree-new] [] [P [T>] [E] [T<] cmp] genrec
704 J('[] 23 "b" BTree-add') # Initial
712 J('["b" 23 [] []] 88 "c" BTree-add') # Less than
715 ['b' 23 [] ['c' 88 [] []]]
720 J('["b" 23 [] []] 88 "a" BTree-add') # Greater than
723 ['b' 23 ['a' 88 [] []] []]
728 J('["b" 23 [] []] 88 "b" BTree-add') # Equal to
736 J('[] 23 "a" BTree-add 88 "b" BTree-add 44 "c" BTree-add') # Series.
739 ['a' 23 [] ['b' 88 [] ['c' 44 [] []]]]
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.
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
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
758 # A Version of `BTree-iter` that does In-Order Traversal
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.
762 BTree-iter-order == [not] [pop] [R0 [BTree-iter] R1] ifte
764 To define `R0` and `R1` it helps to look at them as they will appear when they run:
766 [key value left right] R0 [BTree-iter-order] R1
768 #### Process the left child.
769 Staring at this for a bit suggests `dup third` to start:
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
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]
782 #### Process the current node.
783 So far, so good. Now we need to process the current node's values:
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]
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.
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]
794 #### Process the right child.
795 First ditch the rest of the node and get the right child:
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]
800 Then, of course, we just need `i` to run `BTree-iter-order` on the right side:
802 left BTree-iter-order key right [BTree-iter-order] i
803 left BTree-iter-order key right BTree-iter-order
805 #### Defining `BTree-iter-order`
806 The result is a little awkward:
808 R1 == [cons dip] dupdip [[F] dupdip] dip [rest rest rest first] dip i
810 Let's do a little semantic factoring:
812 fourth == rest rest rest first
814 proc_left == [cons dip] dupdip
815 proc_current == [[F] dupdip] dip
816 proc_right == [fourth] dip i
818 BTree-iter-order == [not] [pop] [dup third] [proc_left proc_current proc_right] genrec
820 Now we can sort sequences.
824 define('BTree-iter-order == [not] [pop] [dup third] [[cons dip] dupdip [[first] dupdip] dip [rest rest rest first] dip i] genrec')
829 J('[3 9 5 2 8 6 7 8 4] to_set BTree-iter-order')
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.
839 ------------------------
842 #### The base case `[]`
843 As before, the stopping predicate just has to detect the empty list:
845 BTree-get == [pop not] [E] [R0] [R1] genrec
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.)
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.
852 tree key [E] BTree-get
853 ---------------------------- key in tree
856 tree key [E] BTree-get
857 ---------------------------- key not in tree
862 BTree-get == [pop not] swap [R0] [R1] genrec
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.
866 tree key [E] [pop not] swap [R0] [R1] genrec
867 tree key [pop not] [E] [R0] [R1] genrec
869 The anonymous specialized recursive function that will do the real work.
871 [pop not] [E] [R0] [R1] genrec
873 #### Node case `[key value left right]`
874 Now we need to figure out `R0` and `R1`:
876 [key value left right] key R0 [BTree-get] R1
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`:
880 [key value left right] key [BTree-get] P [T>] [E] [T<] cmp
884 get-node-key == pop popop first
885 P == over [get-node-key] nullary
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:
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<
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:
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
900 T> == [fourth] dipd i
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
912 [key_n value_n left right] key [BTree-get] E == value_n
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
925 BTree-get == [pop not] swap [] [P [T>] [E] [T<] cmp] genrec
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
936 BTree-get == [pop not] swap [] [
937 over [pop popop first] nullary
938 [[rest rest rest first] dipd i]
948 J('[] "gary" [popop "err"] BTree-get')
956 J('["gary" 23 [] []] "gary" [popop "err"] BTree-get')
966 [] [[0 'a'] [1 'b'] [2 'c']] [i BTree-add] step
968 'c' [popop 'not found'] BTree-get
978 Now let's write a function that can return a tree datastructure with a key, value pair deleted:
980 tree key BTree-delete
981 ---------------------------
985 If the key is not in tree it just returns the tree unchanged.
989 BTree-Delete == [pop not] swap [R0] [R1] genrec
993 -------------------------------------
994 [pop not] [Er] [R0] [R1] genrec
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<
1000 Now we get to figure out the recursive case:
1002 w/ D == [pop not] [Er] [R0] [R1] genrec
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
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
1017 [node_key node_value left right] [key D] node_key key [T>] [E] [T<] cmp
1019 Becomes one of these three:;
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<
1025 ### Greater than case and less than case
1027 [node_key node_value left right] [key D] T>
1028 -------------------------------------------------
1029 [node_key node_value left key D right]
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
1039 [node_key node_value left right] [key D] [dipd] cons infra
1043 T> == [dipd] cons infra
1044 T< == [dipdd] cons infra
1048 [node_key node_value left right] [key D] E
1050 We have to handle three cases, so let's use `cond`.
1052 The first two cases are symmetrical, if we only have one non-empty child node return it.
1055 [[pop third not] pop fourth]
1056 [[pop fourth not] pop third]
1060 (If both child nodes are empty return an empty node.)
1062 The initial structure of the default function:
1064 default == [E'] cons infra
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
1070 right left node_value node_key [key D] E'
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.
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.)
1076 First things first, we no longer need this node's key and value:
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''
1082 Then we have to we find the highest (right-most) node in our lower (left) sub-tree:
1084 right left [key D] E''
1088 right left [key D] rest E'''
1091 Find the right-most node:
1093 right left [D] [dup W] dip E''''
1094 right left dup W [D] E''''
1095 right left left W [D] E''''
1101 We know left is not empty:
1103 [L_key L_value L_left L_right] W
1105 We want to keep extracting the right node as long as it is not empty:
1107 left [P] [B] while W'
1111 [L_key L_value L_left L_right] P
1112 [L_key L_value L_left L_right] fourth
1115 (This has a bug, can run on `[]` so must be guarded:
1117 if_not_empty == [] swap [] ifte
1118 ?fourth == [fourth] if_not_empty
1119 W.rightmost == [?fourth] [fourth] while
1121 The body is also `fourth`:
1123 left [fourth] [fourth] while W'
1126 We know rightest is not empty:
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
1136 W == [fourth] [fourth] while uncons uncons pop
1140 right left left W [D] E''''
1141 right left R_key R_value [D] E''''
1143 Final stretch. We want to end up with something like:
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
1149 If we adjust our definition of `W` to include `over` at the end:
1151 W == [fourth] [fourth] while uncons uncons pop over
1155 right left R_key R_value R_key [D] E''''
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
1166 E' == roll> popop E''
1170 E''' == [dup W] dip E''''
1172 E'''' == cons dipdd swap
1176 W == [fourth] [fourth] while uncons uncons pop over
1177 E' == roll> popop rest [dup W] dip cons dipdd swap
1179 [[pop third not] pop fourth]
1180 [[pop fourth not] pop third]
1184 Minor rearrangement:
1186 W == dup [fourth] [fourth] while uncons uncons pop over
1187 E' == roll> popop rest [W] dip cons dipdd swap
1189 [[pop third not] pop fourth]
1190 [[pop fourth not] pop third]
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
1203 [[pop third not] pop fourth]
1204 [[pop fourth not] pop third]
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
1213 By the standards of the code I've written so far, this is a *huge* Joy program.
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)
1236 J("['a' 23 [] ['b' 88 [] ['c' 44 [] []]]] 'c' ['Er'] BTree-Delete ")
1239 ['a' 23 [] ['b' 88 [] []]]
1244 J("['a' 23 [] ['b' 88 [] ['c' 44 [] []]]] 'b' ['Er'] BTree-Delete ")
1247 ['a' 23 [] ['c' 44 [] []]]
1252 J("['a' 23 [] ['b' 88 [] ['c' 44 [] []]]] 'a' ['Er'] BTree-Delete ")
1255 ['b' 88 [] ['c' 44 [] []]]
1260 J("['a' 23 [] ['b' 88 [] ['c' 44 [] []]]] 'der' ['Er'] BTree-Delete ")
1263 ['a' 23 [] ['b' 88 [] ['c' 44 [] 'Er' 'der' []]]]
1268 J("['a' 23 [] ['b' 88 [] ['c' 44 [] []]]] 'der' [pop] BTree-Delete ")
1271 ['a' 23 [] ['b' 88 [] ['c' 44 [] []]]]
1274 One bug, I forgot to put `not` in the first two clauses of the `cond`.
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?
1278 Then, once we have add, get, and delete we can see about abstracting them.
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).)
1284 tree = [] | [node [tree*]]
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]`.
1289 tree z [C] [N] treestep
1291 If the current tree node is empty then just leave `z` on the stack in lieu:
1293 [] z [C] [N] treestep
1294 ---------------------------
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`.
1299 [node [tree*]] z [C] [N] treestep
1300 --------------------------------------- w/ K == z [C] [N] treestep
1301 node N [tree*] [K] map C
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`.
1306 K == [not] [pop z] [J] ifte
1308 The behavior of `J` is to accept a (non-empty) tree node and arrive at the desired outcome.
1311 ------------------------------
1312 node N [tree*] [K] map C
1314 So `J` will have some form like:
1316 J == .. [N] .. [K] .. [C] ..
1318 Let's dive in. First, unquote the node and `dip` `N`.
1320 [node [tree*]] i [N] dip
1321 node [tree*] [N] dip
1324 Next, `map` `K` over teh child trees and combine with `C`.
1326 node N [tree*] [K] map C
1327 node N [tree*] [K] map C
1332 J == i [N] dip [K] map C
1334 Plug it in and convert to `genrec`:
1336 K == [not] [pop z] [i [N] dip [K] map C] ifte
1337 K == [not] [pop z] [i [N] dip] [map C] genrec
1339 ### Extract the givens to parameterize the program.
1341 [not] [pop z] [i [N] dip] [map C] genrec
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............./
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........./
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
1360 The givens are all to the left so we have our definition.
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
1369 DefinitionWrapper.add_definitions('''
1371 TS0 == [not] swap unit [pop] swoncat
1372 TS1 == [dip] cons [i] swoncat
1373 treestep == swap [map] swoncat [TS1 [TS0] dip] dip genrec
1378 [] 0 [C] [N] treestep
1379 ---------------------------
1383 [n [tree*]] 0 [sum +] [] treestep
1384 --------------------------------------------------
1385 n [tree*] [0 [sum +] [] treestep] map sum +
1389 J('[] 0 [sum +] [] treestep')
1397 J('[23 []] 0 [sum +] [] treestep')
1405 J('[23 [[2 []] [3 []]]] 0 [sum +] [] treestep')
1411 ## A slight modification.
1412 Let's simplify the tree datastructure definition slightly by just letting the children be the `rest` of the tree:
1414 tree = [] | [node tree*]
1416 The `J` function changes slightly.
1419 ------------------------------
1420 node N [tree*] [K] map C
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
1429 J == uncons [N] dip [K] map C
1431 K == [not] [pop z] [uncons [N] dip] [map C] genrec
1436 define('TS1 == [dip] cons [uncons] swoncat') # We only need to redefine one word.
1441 J('[23 [2] [3]] 0 [sum +] [] treestep')
1449 J('[23 [2 [8] [9]] [3] [4 []]] 0 [sum +] [] treestep')
1455 I think these trees seem a little easier to read.
1457 ## Redefining our BTree in terms of this form.
1459 BTree = [] | [[key value] left right]
1461 What kind of functions can we write for this with our `treestep`? The pattern for processing a non-empty node is:
1463 node N [tree*] [K] map C
1465 Plugging in our BTree structure:
1467 [key value] N [left right] [K] map C
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
1479 J('[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]] 23 [i] [uncons pop] treestep')
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.
1488 [key value] N [left right] [K] map C
1490 [key value] first [left right] [K] map flatten cons
1491 key [left right] [K] map flatten cons
1492 key [[lk] [rk] ] flatten cons
1498 [] [flatten cons] [first] treestep
1502 J('[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]] [] [flatten cons] [first] treestep')
1509 #### In-order traversal with `treestep`.
1516 [lk] [rk] key swons concat
1517 [lk] [key rk] concat
1522 [] [i roll< swons concat] [first] treestep
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')
1532 ## Miscellaneous Crap
1537 [key value left right] R0 [BTree-iter-order] R1
1539 left BTree-iter-order key value F right BTree-iter-order
1542 [key value left right] unstack swap
1543 key value left right swap
1544 key value right left
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]
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
1558 R1 == [cons dipdd [F] dip] dupdip i
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
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
1571 BTree-iter-order == [not] [pop] [unstack swap] [[cons dipdd [F] dip] dupdip i] genrec
1573 #### Refactor `cons cons`
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
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.
1585 ## A General Form for Trees
1586 A general form for tree data with N children per node:
1588 [[data] [child0] ... [childN-1]]
1590 Suggests a general form of recursive iterator, but I have to go walk the dogs at the mo'.
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.
1594 [data.. [c0] [c1] ... [cN]] [F C0 C1 ... CN] infil
1595 --------------------------------------------------------
1596 data F [c0] C0 [c1] C1 ... [cN] CN
1600 #### Just make `[F]` a parameter.
1601 We can generalize to a sort of pure form:
1603 BTree-iter == [not] [pop] [[F]] [R1] genrec
1604 == [not] [pop] [[F] [BTree-iter] R1] ifte
1606 Putting `[F]` to the left as a given:
1608 [F] unit [not] [pop] roll< [R1] genrec
1609 [[F]] [not] [pop] roll< [R1] genrec
1610 [not] [pop] [[F]] [R1] genrec
1612 Let's us define a parameterized form:
1614 BTree-iter == unit [not] [pop] roll< [R1] genrec
1616 So in the general case of non-empty nodes:
1618 [key value left right] [F] [BTree-iter] R1
1620 We just define `R1` to do whatever it has to to process the node. For example:
1622 [key value left right] [F] [BTree-iter] R1
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
1628 Pre-, ??-, post-order traversals.
1630 [key value left right] uncons uncons
1631 key value [left right]
1633 For pre- and post-order we can use the `step` trick:
1635 [left right] [BTree-iter] step
1637 left BTree-iter right BTree-iter
1639 We worked out one scheme for ?in-order? traversal above, but maybe we can do better?
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]
1645 key value left right [F] [BTree-iter] R1.1
1649 key value left right [F] [BTree-iter] tuck
1650 key value left right [BTree-iter] [F] [BTree-iter]
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]
1659 left key value right [F] [BTree-iter] tuck foo
1660 left key value right [BTree-iter] [F] [BTree-iter] foo
1662 left BTree-iter key value F right BTree-iter
1664 We could just let `[R1]` be a parameter too, for maximum flexibility.
1666 #### Automatically deriving the recursion combinator for a data type?
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.:
1673 That's fine. Circular datastructures can't be made though.