from Programming (language) puzzles | Lambda the Ultimate:
You have a labeled tree, which (if my Haskell is not too rusty) is defined by:
data LTree a = Leaf String a | Branch String [LTree a]
That might correspond to a normal file system, ignoring . and .., where the leaves are files and the branches are directories. You are to produce an outline view of this tree, showing only those leaves which satisify some predicate function and the branches necessary to reach those leaves. You should assume that the tree is wide and shallow.
A recursive solution using dictionaries:
st:{(./)._n,+{:[5=4:z;,/_f'[x,/:!z;y;z[]];y z;,(x;:;z);()]}[();y;x]}
A "semi-recursive" solution, also using dictionaries:
/ paths to leaves (recursive)
pl:{{:[5=4:y;,/(x,/:!y)_f'y[];,x]}[();x]}
/ subtree where leaf x is f x (non-recursive)
st:{[t;f] / subtree of t where leaves are f
p:pl t / paths to leaves
d:t ./:p / data at leaves
i:&f d / where leaves are f
./[.();p i;:;d i]} / subtree
The solution is "semi-recursive" because it packages up the recursion in the function pl, which, given a nested dictionary, returns a list of the paths to the leaves. The function st indexes out the leaf-data as a vector, applies the predicate f, and then builds a new dictionary from the paths and data which satisfy the predicate.
A non-recursive solution in "open code": t, n, and d are vector inputs representing the tree, the nodes, and the data respectively. T, N, and D are output, representing the subtree, nodes of the subtree, and data of the subtree.
t:0 0 0 2 2 2 4 4 7 7 / tree
c:#t / count of tree
n:!c / nodes (labels)
f:50< / predicate
l:~n _lin t / leaves
d:l*(c _draw 100)%l / data (NaN at non-leaves)
b:&l&f d / leaves where f
p:t\'b / paths to leaves where f
N:{x@<x}@?,//p / subtree labels
z:&#N / zeros
i:N?/:/:p / path indices (renumbering)
k:,'/(-1 1_'2#,:)'i / path indices -> pairwise links
T:@[z;*k;:;k 1] / subtree = renumbered tree
D:@[z%z;i[;0];:;d b] / subtree data
We can do better in K4. A non-recursive solution using maps:
n:!10 / nodes t:n!0 0 0 2 2 2 4 4 7 7 / tree l:~n in t / leaves d:n!l*(10?100)%l / data (NaN at non-leaves) f:50< / predicate N@:<N:?,/t\'&l&f d / subtree nodes T:N#t / subtree D:N#d / subtree data
Every submap of a tree-as-map is a tree-as-map. This is not true for vectors: not every subvector of a tree-as-vector is a tree-as-vector.
Finally, K4 and Q versions of a solution where we represent a tree as a "key table": a map from a node-table to a table containing pointers-to-nodes and data-at-nodes:
t:(+(,`n)!,!10)!+(`p`d!(0 0 0 2 2 2 4 4 7 7;10?100)) / tree (as key table) t:![t;,(in;`n;`p);0b;(,`d)!,0N] / null out non-leaves f:50< / predicate s:?[t;,(in;`n;?,/(. t[;`p])\'?[t;,(f;`d);();`n]);0b;()] / select subtree
t:([n:key 10];p:0 0 0 2 2 2 4 4 7 7;d:10?100) / tree (as key table) t:update d:0N from t where n in p / null out non-leaves f:50< / predicate s:select from t where n in distinct raze((exec p from t)scan)each exec n from t where f d / select subtree
Note: scan:{x\y} added to q.k.
Thanks to Mike Rosenberg for help with the Q version, and to Felix Lungu for translation from Q to K.