1 Treating Trees II: ``treestep``
2 ===============================
4 Let’s consider a tree structure, similar to one described `“Why
5 functional programming matters” by John
6 Hughes <https://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf>`__,
7 that consists of a node value followed by zero or more child trees. (The
8 asterisk is meant to indicate the `Kleene
9 star <https://en.wikipedia.org/wiki/Kleene_star>`__.)
13 tree = [] | [node tree*]
15 In the spirit of ``step`` we are going to define a combinator
16 ``treestep`` which expects a tree and three additional items: a
17 base-case function ``[B]``, and two quoted programs ``[N]`` and ``[C]``.
21 tree [B] [N] [C] treestep
23 If the current tree node is empty then just execute ``B``:
27 [] [B] [N] [C] treestep
28 ---------------------------
31 Otherwise, evaluate ``N`` on the node value, ``map`` the whole function
32 (abbreviated here as ``K``) over the child trees recursively, and then
33 combine the result with ``C``.
37 [node tree*] [B] [N] [C] treestep
38 --------------------------------------- w/ K == [B] [N] [C] treestep
39 node N [tree*] [K] map C
41 (Later on we’ll experiment with making ``map`` part of ``C`` so you can
42 use other combinators.)
44 Derive the recursive function.
45 ------------------------------
47 We can begin to derive it by finding the ``ifte`` stage that ``genrec``
52 K == [not] [B] [R0] [R1] genrec
53 == [not] [B] [R0 [K] R1] ifte
55 So we just have to derive ``J``:
61 The behavior of ``J`` is to accept a (non-empty) tree node and arrive at
67 ------------------------------
68 node N [tree*] [K] map C
70 So ``J`` will have some form like:
74 J == ... [N] ... [K] ... [C] ...
76 Let’s dive in. First, unquote the node and ``dip`` ``N``.
80 [node tree*] uncons [N] dip
84 Next, ``map`` ``K`` over the child trees and combine with ``C``.
88 node N [tree*] [K] map C
89 node N [tree*] [K] map C
96 J == uncons [N] dip [K] map C
98 Plug it in and convert to ``genrec``:
102 K == [not] [B] [J ] ifte
103 == [not] [B] [uncons [N] dip [K] map C] ifte
104 == [not] [B] [uncons [N] dip] [map C] genrec
106 Extract the givens to parameterize the program.
107 -----------------------------------------------
113 [not] [B] [uncons [N] dip] [map C] genrec
114 [B] [not] swap [uncons [N] dip] [map C] genrec
115 [B] [uncons [N] dip] [[not] swap] dip [map C] genrec
117 [B] [[N] dip] [uncons] swoncat [[not] swap] dip [map C] genrec
118 [B] [N] [dip] cons [uncons] swoncat [[not] swap] dip [map C] genrec
119 ^^^^^^^^^^^^^^^^^^^^^^^^^^^
121 Extract a couple of auxiliary definitions:
125 TS.0 == [[not] swap] dip
126 TS.1 == [dip] cons [uncons] swoncat
130 [B] [N] TS.1 TS.0 [map C] genrec
131 [B] [N] [map C] [TS.1 TS.0] dip genrec
132 [B] [N] [C] [map] swoncat [TS.1 TS.0] dip genrec
134 The givens are all to the left so we have our definition.
136 (alternate) Extract the givens to parameterize the program.
137 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
143 [not] [B] [uncons [N] dip] [map C] genrec
144 [not] [B] [N] [dip] cons [uncons] swoncat [map C] genrec
145 [B] [N] [not] roll> [dip] cons [uncons] swoncat [map C] genrec
146 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
153 from notebook_preamble import D, J, V, define, DefinitionWrapper
157 DefinitionWrapper.add_definitions('''
159 _treestep_0 == [[not] swap] dip
160 _treestep_1 == [dip] cons [uncons] swoncat
161 treegrind == [_treestep_1 _treestep_0] dip genrec
162 treestep == [map] swoncat treegrind
169 Consider trees, the nodes of which are integers. We can find the sum of
170 all nodes in a tree with this function:
174 sumtree == [pop 0] [] [sum +] treestep
178 define('sumtree == [pop 0] [] [sum +] treestep')
180 Running this function on an empty tree value gives zero:
184 [] [pop 0] [] [sum +] treestep
185 ------------------------------------
190 J('[] sumtree') # Empty tree.
198 Running it on a non-empty node:
202 [n tree*] [pop 0] [] [sum +] treestep
203 n [tree*] [[pop 0] [] [sum +] treestep] map sum +
210 J('[23] sumtree') # No child trees.
220 J('[23 []] sumtree') # Child tree, empty.
230 J('[23 [2 [4]] [3]] sumtree') # Non-empty child trees.
240 J('[23 [2 [8] [9]] [3] [4 []]] sumtree') # Etc...
250 J('[23 [2 [8] [9]] [3] [4 []]] [pop 0] [] [cons sum] treestep') # Alternate "spelling".
260 J('[23 [2 [8] [9]] [3] [4 []]] [] [pop 23] [cons] treestep') # Replace each node.
265 [23 [23 [23] [23]] [23] [23 []]]
270 J('[23 [2 [8] [9]] [3] [4 []]] [] [pop 1] [cons] treestep')
275 [1 [1 [1] [1]] [1] [1 []]]
280 J('[23 [2 [8] [9]] [3] [4 []]] [] [pop 1] [cons] treestep sumtree')
290 J('[23 [2 [8] [9]] [3] [4 []]] [pop 0] [pop 1] [sum +] treestep') # Combine replace and sum into one function.
300 J('[4 [3 [] [7]]] [pop 0] [pop 1] [sum +] treestep') # Combine replace and sum into one function.
308 Redefining the Ordered Binary Tree in terms of ``treestep``.
309 ------------------------------------------------------------
313 Tree = [] | [[key value] left right]
315 What kind of functions can we write for this with our ``treestep``?
317 The pattern for processing a non-empty node is:
321 node N [tree*] [K] map C
323 Plugging in our BTree structure:
327 [key value] N [left right] [K] map C
334 [key value] first [left right] [K] map i
335 key [value] [left right] [K] map i
336 key [left right] [K] map i
340 This doesn’t quite work:
344 J('[[3 0] [[2 0] [][]] [[9 0] [[5 0] [[4 0] [][]] [[8 0] [[6 0] [] [[7 0] [][]]][]]][]]] ["B"] [first] [i] treestep')
352 Doesn’t work because ``map`` extracts the ``first`` item of whatever its
353 mapped function produces. We have to return a list, rather than
354 depositing our results directly on the stack.
358 [key value] N [left right] [K] map C
360 [key value] first [left right] [K] map flatten cons
361 key [left right] [K] map flatten cons
362 key [[lk] [rk] ] flatten cons
370 [] [first] [flatten cons] treestep
374 J('[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]] [] [first] [flatten cons] treestep')
394 [lk] [rk] key swons concat
402 [] [i roll< swons concat] [first] treestep
406 J('[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]] [] [uncons pop] [i roll< swons concat] treestep')
417 The ``treegrind`` function doesn’t include the ``map`` combinator, so
418 the ``[C]`` function must arrange to use some combinator on the quoted
419 recursive copy ``[K]``. With this function, the pattern for processing a
426 Plugging in our BTree structure:
430 [key value] N [left right] [K] C
434 J('[["key" "value"] ["left"] ["right"] ] ["B"] ["N"] ["C"] treegrind')
439 ['key' 'value'] 'N' [['left'] ['right']] [[not] ['B'] [uncons ['N'] dip] ['C'] genrec] 'C'
442 ``treegrind`` with ``step``
443 ---------------------------
445 Iteration through the nodes
449 J('[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]] [pop] ["N"] [step] treegrind')
454 [3 0] 'N' [2 0] 'N' [9 0] 'N' [5 0] 'N' [4 0] 'N' [8 0] 'N' [6 0] 'N' [7 0] 'N'
461 J('0 [[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]] [pop] [first +] [step] treegrind')
469 Rebuild the tree using ``map`` (imitating ``treestep``.)
473 J('[[3 0] [[2 0] [] []] [[9 0] [[5 0] [[4 0] [] []] [[8 0] [[6 0] [] [[7 0] [] []]] []]] []]] [] [[100 +] infra] [map cons] treegrind')
478 [[103 0] [[102 0] [] []] [[109 0] [[105 0] [[104 0] [] []] [[108 0] [[106 0] [] [[107 0] [] []]] []]] []]]
481 Do we have the flexibility to reimplement ``Tree-get``?
482 -------------------------------------------------------
488 [B] [N] [C] treegrind
490 We’ll start by saying that the base-case (the key is not in the tree) is
491 user defined, and the per-node function is just the query key literal:
495 [B] [query_key] [C] treegrind
497 This means we just have to define ``C`` from:
501 [key value] query_key [left right] [K] C
507 C == P [T>] [E] [T<] cmp
509 [key value] query_key [left right] [K] P [T>] [E] [T<] cmp
514 Seems pretty easy (we must preserve the value in case the keys are
519 [key value] query_key [left right] [K] P
520 [key value] query_key [left right] [K] roll<
521 [key value] [left right] [K] query_key [roll< uncons swap] dip
523 [key value] [left right] [K] roll< uncons swap query_key
524 [left right] [K] [key value] uncons swap query_key
525 [left right] [K] key [value] swap query_key
526 [left right] [K] [value] key query_key
528 P == roll< [roll< uncons swap] dip
530 (Possibly with a swap at the end? Or just swap ``T<`` and ``T>``.)
536 [left right] [K] [value] key query_key [T>] [E] [T<] cmp
538 Becomes one of these three:
542 [left right] [K] [value] T>
543 [left right] [K] [value] E
544 [left right] [K] [value] T<
553 E == roll> popop first
560 T< == pop [first] dip i
561 T> == pop [second] dip i
568 T> == pop [first] dip i
569 T< == pop [second] dip i
570 E == roll> popop first
571 P == roll< [roll< uncons swap] dip
573 Tree-get == [P [T>] [E] [T<] cmp] treegrind
575 To me, that seems simpler than the ``genrec`` version.
579 DefinitionWrapper.add_definitions('''
581 T> == pop [first] dip i
582 T< == pop [second] dip i
583 E == roll> popop first
584 P == roll< [roll< uncons swap] dip
586 Tree-get == [P [T>] [E] [T<] cmp] treegrind
594 [[3 13] [[2 12] [] []] [[9 19] [[5 15] [[4 14] [] []] [[8 18] [[6 16] [] [[7 17] [] []]] []]] []]]
610 [[3 13] [[2 12] [] []] [[9 19] [[5 15] [[4 14] [] []] [[8 18] [[6 16] [] [[7 17] [] []]] []]] []]]
612 [pop "nope"] [25] Tree-get