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