how to collect heterogeneous elements without fixing the collection type

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}

Angela: What should be the type of the following function?

ins c = insert 'x' (insert False c)

Zachary: Wait, we cannot give insert a type. It is applied to a character and to a boolean. There is a conflict!

Angela: How about polymorphism?

Zachary: Hmm, well ok. I can define insert as

insert _ x = x

Then the type of your functions is a -> a. It's the identity function. That will do it but it's not very useful.

Angela: Yes, that is true... Can we give more useful definitions? How can a useful function be applied to arguments of different types?

Zachary: Hmm... overloading! We need a type class:

class Collects e
insert :: e -> [Either Char Bool] -> [Either Char Bool]

instance Collects Char
insert x xs = Left x : xs

instance Collects Bool
insert x xs = Right x : xs

Now ins [] evaluates to [Left 'x',Right False].

Angela: What is its type?

Zachary: Its type is [Either Char Bool]

Angela: I don't like this. The function I gave you doesn't tell much about the type of its argument. The argument type should be an arbitrary collection that can collect characters and booleans and not fixed to a specific one. There are many others: [Either Bool Char], ([Char],[Bool]), or ([Bool],[Char]) to name a few.

The argument of ins might even be a collection that cannot only collect characters and booleans but also integers or file handles. We might later insert something of a different type in the result of calling ins.

Could we generalize your type class such that the type of the collection is not fixed but only constrained to be able to collect characters and booleans?

Zachary: We can make the type of the collection a second parameter to the type class such that the type-class constraint Collects e c means that a value of type c is a collection where elements of type e can be inserted:

class Collects e c
insert :: e -> c -> c

Now, ins has the type (Collects Char c, Collects Bool c) => c -> c.

Angela: Wow, that's pretty. Now we can have many different collections for the same element type and elements of many different types can be collected in a single collection. The type class Collects is really a relation on types!

Let's see... Obviously, a list can collect elements of its element type:

instance Collects a [a]
insert = (:)

Zachary: And the previously defined instances become:

instance Collects Char [Either Char Bool]
insert x xs = Left x : xs

instance Collects Bool [Either Char Bool]
insert x xs = Right x : xs

Angela: Yes. But we can also define another type for collecting characters and booleans:

instance Collects Bool (Int,Int,String)
insert False (fs,ts,cs) = (fs+1,ts,cs)
insert True (fs,ts,cs) = (fs,ts+1,cs)

instance Collects Char (Int,Int,String)
insert c (fs,ts,cs) = (fs,ts,c:cs)

Zachary: Interesting. Now, ins [] :: [Either Char Bool] is evaluated to the list [Left 'x',Right False] and ins (0,0,"") :: (Int,Int,String) yields (1,0,"x"). Everybody who calls ins can decide what kind of collection to provide if they make sure it can collect characters and booleans.

Angela: Congratulations!