OSDN Git Service

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