How far to go with type

General
1

I’d like some advice, either directly or referral to book/website that has some good material on defining types.

I’m implementing a red-black tree and was wondering whether coding the colour into the type is going too far … is a node either RED or BLK or does a node have a RED or BLK property. Six of one probably in this case …

type Tree<'a> =
  | Blk of Tree<'a> * 'a * Tree<'a>
  | Red of Tree<'a> * 'a * Tree<'a> 
  | Nil

or do this

type Colour = RED | BLK

type Tree<'a> = 
  | T of Colour * Tree<'a> * 'a * Tree<'a>
  | Nil

I implemented using the first option, and was pleasantly surprised at how easy it was to refactor to the second, and even better, it worked first time! I prefer the look of the second option code as it looks more concise - maybe that’s the simple answer?

Thanks.

2

As far as I can tell, these two alternatives are isomorphic.

In isolation, then, it doesn’t really matter, so boils down to subjective preference.

In a larger context, one may be superior to the other, but that depends on circumstances.

For example, if the Colour type is useful outside of Tree<'a>, the second option may be more useful. This would imply that if you have a value of the Colour type, you could pass it to the T case constructor without having to pattern-match.

On the other hand, if you don’t expect to have ‘disconnected’ Colour values, then perhaps the first alternative is better, since it’s simpler (it has fewer constituents).