[Haskell-cafe] Type families again

[Andrew Coppin]

Yes, it's me. And yes, I come with yet more questions.

With Haskell 98 (or, indeed, Haskell 2010) it is impossible to define a 
polymorphic version of "head" that works for [], Set and ByteString. You 
can use a higher-kinded type class for [], but that fails for Set 
(because you can't specify the Ord constraint) and fails spectacularly 
for ByteString (because it has the wrong kind). The basic problem is 
that the function's type needs to refer to the type of the container and 
the type of elements it contains, but the relationship between these 
types can be arbitrary.

Type families allow you to neatly and cleanly fix the problem:

   class Head c where
     type Element c :: *
     head :: c -> Element c

It's simple, comprehensible, and it /actually works/.

Following this success, we can define functions such as tail, join, and 
so forth.

What we /can't/ do is define a polymorphic map function. One might try 
to do something like

   class Functor f where
     type Element f :: *
     fmap :: (Element f2 ~ y) => (x -> y) -> f -> f2

   instance Functor [x] where
     type Element [x] = x
     fmap = map

However, this fails. Put simply, the type for fmap fails to specify that 
f and f2 must be /the same type of thing/, just with different element 
types.

The trouble is, after spending quite a bit of brainpower, I literally 
cannot think of a way of writing such a constraint. Does anybody have 
any suggestions?



Second, what's the difference between using "type", "newtype" and "data" 
in a class definition?