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

Question

Well, I am asked to do the following:

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

• Any inner vertex (not a leaf) must be of type "a" or "b", and the leaves do not matter.

• For each path in the tree, all values ​​should appear before the value "b": 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 similar to the one described above, but now I also have “c”, and the second requirement says that for each path I “values ​​appear before the values ​​of b and all values ​​of“ b ”appear before the values c.

Firstly, I’m not sure how to define binary trees in order to have more than one type in them. I mean the simplest binary tree:

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

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

Any help would be appreciated.

Thanks.

---

OK thank you very much. So you mean something like this:

 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 what I did for the case is a tree of type 3, 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 ; 

I'm right?

Also, what does the requirement of leaves mean? One that says leaves shouldn't matter?

Answer 1

Firstly, I'm not sure how to define binary trees in order to have more than 1 type in them.

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

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

Define twotypetree as a abranch that contains the value of 'a , and two ('a, 'b) twotypetree or bbranch that contains the 'b tree .

Since a 'b tree cannot contain any 'a s, a bnode cannot have any child nodes that contain 'a s, so the requirement is fulfilled.