{----------------------------------------------------------------} {--- Generalised divide-and-conquer ---} {----------------------------------------------------------------} list a ::= Nil | Cons a (list a); tree a ::= Leaf | Branch (tree a) a (tree a) ; ;; {----------------------------------------------------------------} map f l = case l of Nil -> Nil; Cons x xs -> Cons (f x) (map f xs) end; {----------------------------------------------------------------} {-- unfortunately, abstract interpretation is not powerful enough to see we never need this. --} error = error; {----------------------------------------------------------------} {-- list subscription --} {-- This is bound to get us a lousy abstract interpretation, since it means using different elements of the list in different ways --} nth n l = case l of Nil -> error; Cons x xs -> case n > 0 of False -> x; True -> nth (n-1) xs end end; {----------------------------------------------------------------} {-- divide & conquer --} {-- allow the merge function to access the original problem as well as solved subproblems --} divide_conq is_base base_fn merge_fn split_fn problem = case is_base problem of True -> base_fn problem; False -> merge_fn problem (map (divide_conq is_base base_fn merge_fn split_fn) (split_fn problem)) end; {----------------------------------------------------------------} {-- pretty straightforward stuff --} treeSum tree = let t_is_base = \t -> case t of Leaf -> True; Branch l x r -> False end; t_base_fn = \t -> 0; t_split_fn = \t -> case t of Branch l x r -> Cons l (Cons r Nil); Leaf -> error end; t_merge_fn = \original_tree solved_subproblems -> case original_tree of Leaf -> error; Branch original_l original_x original_r -> (nth 0 solved_subproblems) + (nth 1 solved_subproblems) + original_x end in divide_conq t_is_base t_base_fn t_merge_fn t_split_fn tree; {----------------------------------------------------------------} mirror tree = let m_is_base = \t -> case t of Leaf -> True; Branch l x r -> False end; m_base_fn = \t -> t; m_split_fn = \t -> case t of Branch l x r -> Cons l (Cons r Nil); Leaf -> error end; m_merge_fn = \original_tree solved_subproblems -> case original_tree of Leaf -> error; Branch original_l original_x original_r -> Branch (nth 1 solved_subproblems) original_x (nth 0 solved_subproblems) end in divide_conq m_is_base m_base_fn m_merge_fn m_split_fn tree; {----------------------------------------------------------------} {--- end divide.cor ---} {----------------------------------------------------------------}