Yesterday I was writing some Haskell code to implement a union-find data structure.

I wanted to experiment with algebraic data types and generic types and I ended up writing the following data structure:

1
2
3
4

data UnionFindElement valueType =
  RootElement valueType |
  ElementWithParent valueType (UnionFindElement valueType)
  deriving (Eq, Show)

With data UnionFindElement valueType we define a new data type. It is called UnionFindElement and it will contain values whose type is valueType. This is a slightly different syntax to achieve the very same thing we can get with Java or C# generics.

I defined the type as an algebraic data type, so UnionFindElement is defined as either a RootElement or an ElementWithParent.

Finally we need to derive the Eq and Show typeclasses that, respectively, gives to our types an equality relation and the possibility of being printed.

We now need some functions that actually use the data structure.

Let’s do the simplest thing possible: checking whether an UnionFindElement holds a given value. The Haskell equations behind the function are simply:

1
2
3

holds :: UnionFindElement valueType -> valueType -> Bool
holds (RootElement v) value = v == value
holds (ElementWithParent v root) value = v == value

That is the implementation we want, but the Haskell compiler will complain because we still miss the right definition of the type of the function. We have to figure out how to tell the compiler that we need to constrain the type of valueType to something supporting equality.

I asked on StackOverflow how to do that and I found both an answer with a theoretical explaination and a useful trick: when you can’t figure out what type you need, just ask the type inferencer.

All you need to do is to run the interpreter ghci, define the data types and the implementation of the function. The interpreter won’t complain and you can ask it what is the type it inferred for the function with :t FUNCTION_NAME.

Asking the data type of holds it will return:

1
2

ghci> :t holds
holds :: Eq a => UnionFindElement a -> a -> Bool

You should note that in addition to the type of the funciton the type inference figured out that we need to specify Eq a =>. It simply means that, since we are using == on the value contained by our element, we need to require that the type contained in an UnionFindElement supports equality.

Hence, the type we need for our holds function is:

1

holds :: (Eq valueType) => UnionFindElement valueType -> valueType -> Bool

Of course I could have find the solution to my problem by studying Haskell syntax deeply, but I think that having a powerful tool as the type inferencer may come in hand and it could help quickly solve several problems.

UPDATE 1: crntaylor in an Hacker News comment made an interesting point:

Most of the time, you don’t need to supply types in Haskell, as the compiler is perfectly capable of figuring them out for itself.

UPDATE 2: Gabriele blogged about another way to specify type constraints. Instead of specifying them for each function, he found an approach that allows you to declare them, once for all, together with the data structure.