(* 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 *)