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 we define a new data type. It is called
and it will contain values whose type is
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
Finally we need to derive the
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
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
Asking the data type of
holds it will return:
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:
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.
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.