How to define trees with more than one type in ML programing language

Question

Well, I am asked to do the next thing:

To define a binary tree which can contain 2 different types: ('a,'b) abtree and these are the requirements:

1. Any inner vertex (not a leaf) must be of the type 'a or 'b and the leafs have no value.

2. For every path in the tree all 'a values must appear before the 'b value: examples of paths:

   'a->'a->'a-'b (legal)
   'a->'b->'b (legal)
   'a->'a->'a (legal)
   'b->'b->'b (legal)
   'a->'b->'a (ILLEGAL)
   

and also I need to define another tree which is like the one described above but now I have got also 'c and in the second requirement it says that for every path I 'a values appear before the 'b values and all the 'b values appear before the 'c values.

First, I am not sure how to define binary trees to have more than 1 type in them. I mean the simplest binary tree is:

datatype 'a tree =
          leaf
         | br of 'a * 'a tree * 'a tree;

And also how I can define a tree to have these requirements.

Any help will be appreciated.

Thanks.

---

OK, thanks a lot. So you mean something like that:

datatype 'b bTree = 
          leaf
        | bBranch of 'b * 'b bTree * 'b bTree
;
datatype ('a,'b) abTree = 
          leaf
        | aBranch of 'a * ('a, 'b) abTree * ('a,'b) abTree
        | bBranch of 'b * 'b bTree * 'b bTree
;

and that's what I did for the case it's a 3 type tree as I mentioned above:

datatype 'c cTree =  
    leaf
    | cBranch of 'c * 'c cTree * 'c cTree
;


datatype ('b, 'c) bcTree = 
            leaf
    | bBranch of 'b * ('b, 'c) bcTree * ('b,'c) bcTree
    | cBranch of 'c * 'c cTree * 'c cTree

;

datatype ('a, 'b, 'c) abcTree = 
    leaf
            | aBranch of 'a * ('a, 'b, 'c) abcTree * ('a, 'b, 'c) abcTree
            | bBranch of 'b * ('b, 'c) bcTree * ('b, 'c) bcTree
    | cBranch of 'c * 'c cTree * 'c cTree
;

Am I right?

Also, what does the requirement of leafs means? The one that says that the leafs should have no value?

Answer 1

First, I am not sure how to define binary trees to have more than 1 type in them.

datatype ('a, 'b) twotypetree = ...

And also how I can define a tree to have these requirements.

Define a twotypetree to be either an abranch which contains an 'a value and two ('a, 'b) twotypetrees or a bbranch which contains a 'b tree.

Since a 'b tree can't contain any 'as, a bnode can't have any child nodes which contain 'as, so the requirement is met.