Playing with types in Haskell (Part 4)

A Queer Example

However, just to clarify things and hopefully get a better mental picture of how Haskell really treats types, let’s play with a really weird typeclass, and find a way to make an instance of it.

class Weird p where  
  weird :: j k -> p k j

The weird function takes one parameter, and returns a single, concrete type. We look for -> to determine parameters and return values. However, the type of the argument and the return value is a little more complicated. Let’s work it out.

Since (j k) must be a concrete type, we can derive the kinds of j and k quite easily, because k itself must be a concrete type, and j is clearly a type constructor, that takes a single concrete type (represented by k).

k :: *  
j :: * -> *

Since we have derived the kinds of j and k, we can figure out p, since p is also clearly a type constructor, taking two types, k and j. And we know the kinds of k and j.

p :: * -> (* -> *) -> *

What this Weird typeclass is saying, is that instances of it, represented by p, must be of kind: * -> (* -> *) -> *. This is no different from having a typeclass as follows:

class Eq a where  
  (==) :: a -> a -> Bool

In this case, a is obviously a concrete type, and has kind of a :: *.

Similarly,

class Functor f where  
  fmap :: (a -> b) -> f a -> f b

In this case, f is clearly a type constructor taking one concrete type, and hence f :: * -> *. Hence, instances of the Functor typeclass, as you are probably already familiar with by now, expects a type constructor taking one concrete type. Examples of those are [] and Maybe.

Hence, instances of Weird must be type constructors, taking one conrete type, and another type constructor (that takes one concrete type). Hence, the kind is

p :: * -> (* -> *) -> *.

Let’s construct everything ourselves.

Since k is a concrete type, we can construct one trivially. Note that we don’t really have to do this, we could just as well use any existing such type, such as Int. We can test this using:

:t SomeK

data SomeK = SomeK deriving (Show)

Since j is a type constructor that expects a concrete type we can also construct j quite easily. Again note that we don’t really have to do this construction, we could just use an existing such type, such as Maybe (I’m using this loosely). We can test this using:

:t SomeJ SomeK

data SomeJ a = SomeJ a deriving (Show)

And finally, we know that p is a type constructor that expects two parameters: first a concrete type, and then a type constructor that is going to take a single concrete type. We construct that as well. This we probably have to do, because there isn’t an easily available type that looks like this. In order to ensure that b is treated as a type constructor, we “apply” it to a. We also reverse the resulting type (constructing with SomeP b a results in type SomeP a b) because that’s what the weird function expects. We want to match it. We can test this using:

:t SomeP (SomeJ SomeK)

data SomeP a b = SomeP (b a) deriving (Show)

Now let’s make an instance of Weird. Remember that the weird function takes one argument, of type (j k). However, in the function itself, we don’t have to specify the type (since it’s already been specified in the class, obviously). We’ll just call that argument x, in Haskell style. Next, we want to create the function’s body such that it returns a (p k j). We don’t really care what the function body does, because this is a play on types. We just care about the return type.

class Weird where
  weird :: j k -> p k j

The easiest, immediate thing that is going to return a (p k j) is the SomeP that we constructed (again obviously because we were basing the construction on the requirements of weird. Hence, the SomeP value constructor is going to create a type of SomeP a b, where a represents k, and b represents j. In order for the SomeP value constructor to produce SomeP a b (or equivalently SomeP k j), it’s going to take SomeP b a (or equivalently SomeP j k). (j k) is exactly the type of x. Hence, SomeP x will trigger the type constructor of SomeP (j k), and create a type of SomeP k j. That’s exactly (p k j).

instance Weird SomeP where  
  weird x = SomeP x

We have an instance of Weird! Not saying it’s useful, but well, it’s just to help understanding.