Determine whether two trees have the same fringe, where the fringe of a tree is a list of its leaves, read from the tree in some determinate order. For example, where the leaves are read left-to-right, these two trees have the same fringe:
* *
/ \ / \
a * * c
/ \ / \
b c a b
namely
a b c
Two papers of interest are this article on Lisp by Richard Gabriel, and Jim Weirich's Ruby-oriented paper.
The work in this paper was triggered by a conversation between Slava Pestov and Chris Double on the concatenative languages mailing list.
A K script containing the code discussed in this paper is here.
A K programmer's first reaction is to flatten the trees, then match:
a:(`a;`b`c) b:(`a`b;`c) c:(`a`X;`c)flatten:,//flatten[a]~flatten b 1 flatten[a]~flatten c 0
Alternatively, find the paths, index out the atoms, then match:
lp:{:[@x;,();,/(!#x),/:'_f'x]}p:lp a q:lp b p / all paths into a (,0 1 0 1 1) q / all paths into b (0 0 0 1 ,1) r:a ./:p / get all atoms in a r 1 2 3 s:b ./:q / get all atoms in b s 1 2 3 r~s / match atom-lists 1
The array solution requires extra space for all the leaves of both trees. The recursive solution requires extra space for all the paths of both trees, plus the space and time required to access, hold, and compare the leaves. In practice, we K programmers will hardly ever not use one of these methods, but there remains the question how we would implement a K solution which requires no (or very little) additional storage, and which discovers fringe-difference as early as possible.
A K function f which recursively walks the paths of a tree is a conditional: if the argument x is an atom, we're done; else, we call f on each item of x. For example, a function which recursively retrieves the leaves of a tree
ra:{:[@x;x;,/_f'x]}
If x is an atom, return it; else flatten the result of applying the function to each item of x.
Can we simulate recursive descent through a tree? That is, achieve the same result without physical recursion?
Let (x;y;z) be a triple in which x is the last atom retrieved from tree y, and z is a push-down stack of index-paths into y. The basic idea is that, at any time, some number of atoms have been retrieved from y by paths which at some point appeared in z, and that the paths which are currently in z are either incomplete or untested. Our function will take an (x;y;z) and perform exactly one processing step. This step has the following logic:
if z is () we're done, so return (x;y;z) else where i is the next path in z and d is y at i, if d is atomic return (d;y;z without i) else return (x;y;z without i joined to i join each |!#d)
In K,
it:{:[~#z;(x;y;z);@d:y . i:*-1#z;:(d;y;-1_ z);(x;y;(-1_ z),i,/:|!#d)]}.
The function is re-entrant and O(1). The (x;y;z) triple contains all the information required to compute the next step, which is either (i) no action, (ii) an atom, or (iii) stack the next level of "recursion."
It's handy to have a function which takes a tree and returns the initial triple:
gt:{(;x;|!#x)}
gt a
( / null
(1 / the tree
2 3)
1 0) / two unprocessed paths: 1 0 - reversed because this is pushdown stack
We can use \ (scan converge) to see the results of repeatedly applying it to gt a:
it\gt a (( (1 2 3) 1 0) (1 (1 2 3) ,1) (1 (1 2 3) (1 1 1 0)) (2 (1 2 3) ,1 1) (3 (1 2 3) ()))
Since not every application of this function retrieves an atom from the tree, we must layer on a function which does do just that:
na:{{(#x 2)&~n~*x}x/@[y;0;:;_n]}
The function takes and returns a triple y. The first argument is the iterator function it will use to process x. Initially, it sets x 0 to null. It then repeatedly applies the iterator x to y until either null fails to match *y (we've succeeded in retrieving the next atom), or y 2 is empty (we've succeeded in processing all paths through the tree).
The scan-converge trace of na is a subset of the trace of the iterator it:
na[it]\gt a (( (1 2 3) 1 0) (1 (1 2 3) ,1) (2 (1 2 3) ,1 1) (3 (1 2 3) ()) ( (1 2 3) ()))
The iterative same-fringe function is now easily assembled:
sf:{while[#(x:na[it]x)2;if[~x[0]~*y:na[it]y;:0]];~#na[it;y]2}
That is:
while there are atoms left to retrieve in x:
if the atom-list of x doesn't match that of y, then exit with failure.
when you've run out of atoms in x, succeed if you've run out of atoms in y, else fail.
Alternate printing the leaves of isomorphic trees x and y. The display of a leaf z should indent d-many spaces, where d is the depth of z; i.e. the number of nodes one must traverse to reach z.
p2:{:[@y;`0:(x#" "),/:$(y;z);_f[x+1]'[y;z]];}
p2[0;a;a+100]
1
101
2
102
3
103
jt:{:[~#z;(x;y;z);@d:y . i:*-1#z;:((d;#i);y;-1_ z);(x;y;(-1_ z),i,/:|!#d)]}
pt:{while[#(x:na[jt]x)2;pr[x;y:na[jt]y]];pr[x;nb[jt]y];}
pr:{`0:{(y#" "),$x}.'(*x;*y)}
pt[gt a;gt a+100]
1
101
2
102
3
103
The iterative solution doesn't even require that the trees be structurally similar:
pt[gt a;gt b+100] 1 101 2 102 3 103