2 Treating Trees II: ``treestep``
3 ===============================
5 Let's consider a tree structure, similar to one described `"Why
6 functional programming matters" by John
7 Hughes <https://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf>`__,
8 that consists of a node value followed by zero or more child trees. (The
9 asterisk is meant to indicate the `Kleene
10 star <https://en.wikipedia.org/wiki/Kleene_star>`__.)
14 tree = [] | [node tree*]
16 In the spirit of ``step`` we are going to define a combinator
17 ``treestep`` which expects a tree and three additional items: a
18 base-case function ``[B]``, and two quoted programs ``[N]`` and ``[C]``.
22 tree [B] [N] [C] treestep
24 If the current tree node is empty then just execute ``B``:
28 [] [B] [N] [C] treestep
29 ---------------------------
32 Otherwise, evaluate ``N`` on the node value, ``map`` the whole function
33 (abbreviated here as ``K``) over the child trees recursively, and then
34 combine the result with ``C``.
38 [node tree*] [B] [N] [C] treestep
39 --------------------------------------- w/ K == [B] [N] [C] treestep
40 node N [tree*] [K] map C
42 (Later on we'll experiment with making ``map`` part of ``C`` so you can
43 use other combinators.)
45 Derive the recursive function.
46 ------------------------------
48 We can begin to derive it by finding the ``ifte`` stage that ``genrec``
53 K == [not] [B] [R0] [R1] genrec
54 == [not] [B] [R0 [K] R1] ifte
56 So we just have to derive ``J``:
62 The behavior of ``J`` is to accept a (non-empty) tree node and arrive at
68 ------------------------------
69 node N [tree*] [K] map C
71 So ``J`` will have some form like:
75 J == ... [N] ... [K] ... [C] ...
77 Let's dive in. First, unquote the node and ``dip`` ``N``.
81 [node tree*] uncons [N] dip
85 Next, ``map`` ``K`` over the child trees and combine with ``C``.
89 node N [tree*] [K] map C
90 node N [tree*] [K] map C
97 J == uncons [N] dip [K] map C
99 Plug it in and convert to ``genrec``:
103 K == [not] [B] [J ] ifte
104 == [not] [B] [uncons [N] dip [K] map C] ifte
105 == [not] [B] [uncons [N] dip] [map C] genrec
107 Extract the givens to parameterize the program.
108 -----------------------------------------------
114 [not] [B] [uncons [N] dip] [map C] genrec
115 [B] [not] swap [uncons [N] dip] [map C] genrec
116 [B] [uncons [N] dip] [[not] swap] dip [map C] genrec
118 [B] [[N] dip] [uncons] swoncat [[not] swap] dip [map C] genrec
119 [B] [N] [dip] cons [uncons] swoncat [[not] swap] dip [map C] genrec
120 ^^^^^^^^^^^^^^^^^^^^^^^^^^^
122 Extract a couple of auxiliary definitions:
126 TS.0 == [[not] swap] dip
127 TS.1 == [dip] cons [uncons] swoncat
131 [B] [N] TS.1 TS.0 [map C] genrec
132 [B] [N] [map C] [TS.1 TS.0] dip genrec
133 [B] [N] [C] [map] swoncat [TS.1 TS.0] dip genrec
135 The givens are all to the left so we have our definition.
137 (alternate) Extract the givens to parameterize the program.
138 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
144 [not] [B] [uncons [N] dip] [map C] genrec
145 [not] [B] [N] [dip] cons [uncons] swoncat [map C] genrec
146 [B] [N] [not] roll> [dip] cons [uncons] swoncat [map C] genrec
147 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
154 from notebook_preamble import D, J, V, define, DefinitionWrapper
158 DefinitionWrapper.add_definitions('''
160 _treestep_0 == [[not] swap] dip
161 _treestep_1 == [dip] cons [uncons] swoncat
162 treegrind == [_treestep_1 _treestep_0] dip genrec
163 treestep == [map] swoncat treegrind
170 Consider trees, the nodes of which are integers. We can find the sum of
171 all nodes in a tree with this function:
175 sumtree == [pop 0] [] [sum +] treestep
179 define('sumtree == [pop 0] [] [sum +] treestep')
181 Running this function on an empty tree value gives zero:
185 [] [pop 0] [] [sum +] treestep
186 ------------------------------------
191 J('[] sumtree') # Empty tree.
199 Running it on a non-empty node:
203 [n tree*] [pop 0] [] [sum +] treestep
204 n [tree*] [[pop 0] [] [sum +] treestep] map sum +
211 J('[23] sumtree') # No child trees.
221 J('[23 []] sumtree') # Child tree, empty.
231 J('[23 [2 [4]] [3]] sumtree') # Non-empty child trees.
241 J('[23 [2 [8] [9]] [3] [4 []]] sumtree') # Etc...
251 J('[23 [2 [8] [9]] [3] [4 []]] [pop 0] [] [cons sum] treestep') # Alternate "spelling".
261 J('[23 [2 [8] [9]] [3] [4 []]] [] [pop 23] [cons] treestep') # Replace each node.
266 [23 [23 [23] [23]] [23] [23 []]]
271 J('[23 [2 [8] [9]] [3] [4 []]] [] [pop 1] [cons] treestep')
276 [1 [1 [1] [1]] [1] [1 []]]
281 J('[23 [2 [8] [9]] [3] [4 []]] [] [pop 1] [cons] treestep sumtree')
291 J('[23 [2 [8] [9]] [3] [4 []]] [pop 0] [pop 1] [sum +] treestep') # Combine replace and sum into one function.
301 J('[4 [3 [] [7]]] [pop 0] [pop 1] [sum +] treestep') # Combine replace and sum into one function.
309 Redefining the Ordered Binary Tree in terms of ``treestep``.
310 ------------------------------------------------------------
314 Tree = [] | [[key value] left right]
316 What kind of functions can we write for this with our ``treestep``?
318 The pattern for processing a non-empty node is:
322 node N [tree*] [K] map C
324 Plugging in our BTree structure:
328 [key value] N [left right] [K] map C
335 [key value] first [left right] [K] map i
336 key [value] [left right] [K] map i
337 key [left right] [K] map i
341 This doesn't quite work:
345 J('[[3 0] [[2 0] [][]] [[9 0] [[5 0] [[4 0] [][]] [[8 0] [[6 0] [] [[7 0] [][]]][]]][]]] ["B"] [first] [i] treestep')
353 Doesn't work because ``map`` extracts the ``first`` item of whatever its
354 mapped function produces. We have to return a list, rather than
355 depositing our results directly on the stack.
359 [key value] N [left right] [K] map C
361 [key value] first [left right] [K] map flatten cons
362 key [left right] [K] map flatten cons
363 key [[lk] [rk] ] flatten cons
371 [] [first] [flatten cons] treestep
375 J('[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]] [] [first] [flatten cons] treestep')
395 [lk] [rk] key swons concat
403 [] [i roll< swons concat] [first] treestep
407 J('[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]] [] [uncons pop] [i roll< swons concat] treestep')
418 The ``treegrind`` function doesn't include the ``map`` combinator, so
419 the ``[C]`` function must arrange to use some combinator on the quoted
420 recursive copy ``[K]``. With this function, the pattern for processing a
427 Plugging in our BTree structure:
431 [key value] N [left right] [K] C
435 J('[["key" "value"] ["left"] ["right"] ] ["B"] ["N"] ["C"] treegrind')
440 ['key' 'value'] 'N' [['left'] ['right']] [[not] ['B'] [uncons ['N'] dip] ['C'] genrec] 'C'
443 ``treegrind`` with ``step``
444 ---------------------------
446 Iteration through the nodes
450 J('[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]] [pop] ["N"] [step] treegrind')
455 [3 0] 'N' [2 0] 'N' [9 0] 'N' [5 0] 'N' [4 0] 'N' [8 0] 'N' [6 0] 'N' [7 0] 'N'
462 J('0 [[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]] [pop] [first +] [step] treegrind')
470 Rebuild the tree using ``map`` (imitating ``treestep``.)
474 J('[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]] [] [[100 +] infra] [map cons] treegrind')
479 [[103 0] [[102 0] [] []] [[109 0] [[105 0] [[104 0] [] []] [[108 0] [[106 0] [] [[107 0] [] []]] []]] []]]
482 Do we have the flexibility to reimplement ``Tree-get``?
483 -------------------------------------------------------
489 [B] [N] [C] treegrind
491 We'll start by saying that the base-case (the key is not in the tree) is
492 user defined, and the per-node function is just the query key literal:
496 [B] [query_key] [C] treegrind
498 This means we just have to define ``C`` from:
502 [key value] query_key [left right] [K] C
508 C == P [T>] [E] [T<] cmp
510 [key value] query_key [left right] [K] P [T>] [E] [T<] cmp
515 Seems pretty easy (we must preserve the value in case the keys are
520 [key value] query_key [left right] [K] P
521 [key value] query_key [left right] [K] roll<
522 [key value] [left right] [K] query_key [roll< uncons swap] dip
524 [key value] [left right] [K] roll< uncons swap query_key
525 [left right] [K] [key value] uncons swap query_key
526 [left right] [K] key [value] swap query_key
527 [left right] [K] [value] key query_key
529 P == roll< [roll< uncons swap] dip
531 (Possibly with a swap at the end? Or just swap ``T<`` and ``T>``.)
537 [left right] [K] [value] key query_key [T>] [E] [T<] cmp
539 Becomes one of these three:
543 [left right] [K] [value] T>
544 [left right] [K] [value] E
545 [left right] [K] [value] T<
554 E == roll> popop first
561 T< == pop [first] dip i
562 T> == pop [second] dip i
569 T> == pop [first] dip i
570 T< == pop [second] dip i
571 E == roll> popop first
572 P == roll< [roll< uncons swap] dip
574 Tree-get == [P [T>] [E] [T<] cmp] treegrind
576 To me, that seems simpler than the ``genrec`` version.
580 DefinitionWrapper.add_definitions('''
582 T> == pop [first] dip i
583 T< == pop [second] dip i
584 E == roll> popop first
585 P == roll< [roll< uncons swap] dip
587 Tree-get == [P [T>] [E] [T<] cmp] treegrind
595 [[3 13] [[2 12] [] []] [[9 19] [[5 15] [[4 14] [] []] [[8 18] [[6 16] [] [[7 17] [] []]] []]] []]]
611 [[3 13] [[2 12] [] []] [[9 19] [[5 15] [[4 14] [] []] [[8 18] [[6 16] [] [[7 17] [] []]] []]] []]]
613 [pop "nope"] [25] Tree-get