Generate all trees of height n with only 3 values and 2 operators

Question

I have this type of tree:

type op = Add | Mult ;;

type tree =
  | Value of int
  | Node of tree * op * tree
;;

It is a syntaxic binary tree. It means each nodes is an operator and each leaves represent a number. Here I need to work modulo 3 so my values are [0;1;2].

For instance the expression let e1 = Node(Node(Value 1,Add,Value 2),Add,Value 2) in represents the folling expression : ((1+2)+2).

Now I need to create a function generate_height : int n -> tree list which returns all possible trees of height n.

A little drawing can help :

My initial idea was to generate all empty trees (we don't care about values in leaves we just se them to 0 but we need all combination of nodes)

let generate_empty n =

  let rec gen_rec n op =
    match n with 
    | 0 -> Value 0
    | _ -> Node(gen_rec (n-1) op,op, gen_rec (n-1) op)
  in

 
  (gen_rec n Add)::[gen_rec n Mult]

;;

But it just return two trees : one with only an add op and the other one with mult. I don't know how to make all combinations of operators.

And secondly if this function was successful I wanted to iterate through all "empty trees" and change leaves with all combinations of [0;1;2].

I have a beginning of something

let modify_trees_empty list =

  let rec modify_leaf empty_tree = 

    match empty_tree with 
    | Value x -> Value x
    | Node(Value x, op, Value y) -> Node(Val 1, op, Val 1);(*here I want Node(0,op,0),(0,1)..(2,2)*)
    | Node (g, op, d) -> Node(modify_leaf g, op, modify_leaf d)  
  
  in

  let rec iterate_list_and_apply list =
    match list with 
    | [] -> []
    | el :: tl -> [modify_leaf el] @ iterate_list_and_apply tl
  in

  iterate_list_and_apply list
;;

But It just changes leaves to one and that's not what I wanted ^^

Answer 1

Problem :

you want all trees of size n

Solution :

• if n = 0 then it's the list of all the Value i (in your case, i is 0, 1 or 2)
• if n > 0 then :
  • list all the trees of length n-1 in a list named sub_trees for example.
  • Then make a function cartesian_product that, given a list, returns all the possible couple of list's elements. For example, cartesian_product [1,2,3] returns [(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)]
  • Then for each possible operator (here Mult and Add), returns all the trees made with this operator and a couple from cartesian_product sub_trees

Remarks concerning your current code

Here are some remarks about your code that could help you to discover new things.

For

let rec iterate_list_and_apply list =
    match list with 
    | [] -> []
    | el :: tl -> [modify_leaf el] @ iterate_list_and_apply tl
  in

You should not use the @ operator to add an only element to a list, instead use the :: operator

| el :: tl -> modify_leaf el :: iterate_list_and_apply tl

Also note that you can also use List.iter modify_leaf list which does the same as iterate_list_and_apply list, if you want to make your program shorter (but coding those simple function is a good exercise too)

Also, here is a syntactic sugar you may not know :
Instead of

let rec modify_leaf empty_tree = 
   match empty_tree with 
    | ... -> ...
    | ... -> ...

you can do

let rec modify_leaf = function
    | ... -> ...
    | ... -> ...