[Haskell-cafe] More experiments with ATs

[Sjoerd Visscher]

On Jul 4, 2010, at 11:31 AM, Andrew Coppin wrote:
 
>>> type family F f a :: *
>>> class RFunctor f where
>>>  (%) :: f a b -> (a -> b) -> F f a -> F f b
>>>    
> 
> I have literally no idea what a type family is. I understand ATs (I think!), but TFs make no sense to me.
> 
> (For this reason, most if not all of the rest of this post doesn't make sense.)

I would have liked to use ATs here, like this:

> class RFunctor f where
>   type F f a :: *
>   (%) :: f a b -> (a -> b) -> F f a -> F f b

But this isn't valid as ATs require all type variables to be in scope, and 'a' isn't. 
There's a GHC ticket for this: http://hackage.haskell.org/trac/ghc/ticket/3714

However, I think type families are actually easier to understand than ATs, you can see them as functions on types. So:

> type family F f a :: *

This declares a "function" F with two arguments, f and a, which "returns" a type of kind *

> type instance F BSFunctor Word8 = B.ByteString

This declares that F applied to BSFunctor and Word8 is the type ByteString.

So if we take all this together:

> data BSFunctor :: * -> * -> * where
>   BS :: BSFunctor Word8 Word8
> type instance F BSFunctor Word8 = B.ByteString
> instance RFunctor BSFunctor where
>   BS % g = B.map g

It helps to write out what the type of BS % g needs to be. BS is of type BSFunctor Word8 Word8, so a and b both are Word8, and F BSFunctor a and F BSFunctor b are both B.ByteString. So the specialized type of (%) is:

> BSFunctor Word8 Word8 -> (Word8 -> Word8) -> B.ByteString -> B.ByteString

I admit that 'F' and '%' aren't very enlightening names.

As functors map both types and functions, the following may be more readable, with TMap mapping types, and fmap mapping functions:

> type family TMap f a :: *
> class RFunctor f where
>   fmap :: f a b -> (a -> b) -> f `TMap` a -> f `TMap` b

With as example the list functor:

> data List a b = List
> type instance List `TMap` a = [a]
> instance RFunctor List where
>   List `fmap` f = map f

I hope this helps.

greetings,
Sjoerd Visscher