(* Solving the puzzle of printing the outline of the pruned tree *)
(*
This problem was posed by `rici' on LtU:
http://lambda-the-ultimate.org/node/1872#comment-22974
``You have a labeled tree [see 'a tree below]
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 satisfy
some predicate function and the branches necessary to reach those leaves.
You should assume that the tree is wide and shallow.
I find this problem interesting, in part because it is practical (my
original implementation was to produce a view of an Apache configuration
file showing only directives which pertained to a given module), but
mostly because the nature of the solution seems to vary considerably
between languages. For example, the C solution (or at least a C solution)
requires no heap allocation.''
This problem truly lends itself to `stack marks', or stack
traversal facility described in the paper `Delimited dynamic binding'
(see, in particular Section 6.2 of the paper and the `nub' example).
The following is the OCaml code, assuming the Dynvar library introduced
in that paper, and whose source is available from this web site.
It is easy to see that the problem can indeed be solved without any
heap allocation, requiring only Theta(tree-depth) stack space. The
dynvar library is implemented in terms of delimited continuation
library. The latter is not efficient at the moment: shift, for
example, will always eagerly copy the captured delimited continuation
in a heap-allocated data structure. One can see however that to print
the leaf label and the corresponding branch we never need more than
Theta(tree-depth) of the heap space, all of which can be garbage
collected after we finished with that leaf. Thus the total space
complexity remains Theta(tree-depth). If stack marks were offered to
us as a primitive of the language, we would have needed only half of
the space we use now (the asymptotic complexity remains the same
though).
Incidentally, the solution below does not assume a particular shape
of the tree (wide and shallow, etc). There is no need for that,
*)
open Dynvar;;
#load "dynvar.cmo";;
type 'a tree =
Leaf of string * 'a
| Branch of string * 'a tree list
;;
(* Print the subset of the tree in the outline format, using only
those leaves that satisfy a predicate
*)
let print_outline pr tree =
let d = dnew () in
let indent n = for i = 1 to n do print_string " " done in
let rec print_branch r =
match !r with
None -> ()
| Some (depth,label) ->
dupp d print_branch;
indent depth;
print_endline label;
r := None in
let rec loop depth =
function
| Leaf (label, v) ->
if pr v then print_branch (ref (Some (depth,label))) else ()
| Branch (label, kids) ->
dlet d (ref (Some (depth,label)))
(fun () -> List.iter (loop (succ depth)) kids)
in
dlet d (ref None) (fun () -> loop 0 tree)
;;
(* for testing: make the full binary tree for the given depth *)
let rec full_tree d c = if d <= 0 then Leaf (string_of_int c,c)
else Branch
(((string_of_int d) ^ ": " ^ (string_of_int c)),
[full_tree (pred d) (2*c);
full_tree (pred d) (2*c+1)])
;;
let tree1 = full_tree 3 0;;
(*
val tree1 : int tree =
Branch ("3: 0",
[Branch ("2: 0",
[Branch ("1: 0", [Leaf ("0", 0); Leaf ("1", 1)]);
Branch ("1: 1", [Leaf ("2", 2); Leaf ("3", 3)])]);
Branch ("2: 1",
[Branch ("1: 2", [Leaf ("4", 4); Leaf ("5", 5)]);
Branch ("1: 3", [Leaf ("6", 6); Leaf ("7", 7)])])])
*)
let t1 = print_outline (fun i -> true) tree1;;
(* Compare with the pretty-printing of the tree above:
3: 0
2: 0
1: 0
0
1
1: 1
2
3
2: 1
1: 2
4
5
1: 3
6
7
*)
let t2 = print_outline (fun i -> i mod 3 = 0) tree1;;
(* Prune the tree: print only those leaves whose label is the multiple of 3.
3: 0
2: 0
1: 0
0
1: 1
3
2: 1
1: 3
6
*)