How to define trees with more than one type in ML programing language
- by user550413
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:
Any inner vertex (not a leaf) must be of the type 'a or 'b and the leafs have no value.
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.