OCaml option type in binary tree

1
votes

I have a few problems creating a tree size function with type 'a option tree -> int

type 'a tree = Leaf of 'a
         | Fork of 'a * 'a tree * 'a tree

How would I create a t_opt_size function with type 'a option tree -> int?

I know I would have to use Some and the None operate.

I have this so far, but it's complicated to match with the option type.

let rec t_size (tr: 'a tree): int = 
    match tr with
    | Leaf _ -> 1
    | Fork (_, t1, t2) -> t_size t1 + t_size t2 + 1
3
ocaml
What would t_opt_size do differently than t_size? Given that t_size works on all trees, it would work on trees of options just as well without needing to change anything. - Bergi
For example, I could set a tree to let t5 : string option tree = Fork (Some "a", Leaf (Some "b"), Fork (Some "c", Leaf None, Leaf (Some "d"))). I need the function to hand option types - user3460123
The function does hand that tree fine and will return 5 as expected. - Bergi
I want the function to handle the type 'a option tree. I don't think you understand - user3460123
Given that 'a option tree is a subtype of 'a tree, it already works. If you want to treat options different in that function, please tell us how different. - Bergi

3 Answers

3
votes

I assume from your comments that you want a leaf that looks like (Leaf None) not to be counted in your tree size calculation.

Seems like the key is to split this:

| Leaf _ -> 1

Into two cases:

| Leaf None -> (* Left as exercise *)
| Leaf (Some _) -> (* Left as exercise *)

Since OCaml will take the first match, you can abbreviate this as follows if you like:

| Leaf None -> (* Left as exercise *)
| Leaf _ -> (* Left as exercise *)

You should make a similar change to the Fork case, though I have to say that Fork (None, l, r) doesn't really work for constructing a search tree.

1
votes

If you want to generalize, you might need to write a generic tree walker which accepts a visitor function. I recommend you try to implement fold_tree, which accepts: (1) a fold function, taking some value, a tree and producing a new result ('a -> 'b t -> 'c), (2) an initial element of type 'a as well as (3) a tree. Then, fold_tree returns a value of type 'c. Then, you should be able to call fold_tree with a function that skips over None leaves but otherwise increment the count like you did.

0
votes

If you don't want to count all values in the tree as 1, but each depending on its contents, write a function that determines the count per value and use that:

let weight = function
    | _ -> 1 (* or anything else *)

let rec t_opt_size (tr: 'a tree): int = match tr with
    | Leaf v -> weight v
    | Fork (v, t1, t2) -> t_size t1 + t_size t2 + weight v

You even might want to generalise and pass the weight function as a parameter to t_size instead of writing different size functions that all use their own weighting.