On Types, Part V: Algebraic Datatypes

Let’s go a step further and try to do more with types than just simple enumerations. How about a type for binary trees?

typedef bintree (LeafNode _), (InnerNode (_, _ : bintree, _ : bintree))

Now all bintrees are wellformed binary trees. The tree

   / \
  2   3

can be created like this:

bintree (InnerNode (1, bintree (LeafNode 2), bintree (LeafNode 3)))

Note that for example the expression

bintree (InnerNode (1, 2, 3))

would result in an exception TypeError. If you prefer binary trees such that the above expression is also OK, you can define bintree like this instead:

typedef bintree (LeafNode _), (InnerNode ( _ , _ , _ ))

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: