Associated types and container elements

Question

I think I may have asked this on Haskell-Cafe at some point, but damned if I can find the answer now... So I'm asking it again here, so hopefully in future I can find the answer!

Haskell is fantastic at dealing with parametric polymorphism. But the trouble is that not everything is parametric. As a trivial example, suppose we want to fetch the first element of data out of a container. For a parametric type, that's trivial:

 class HasFirst c where   first :: c x -> Maybe x  instance HasFirst [] where   first []    = Nothing   first (x:_) = Just x 

Now try and write an instance for ByteString. You can't. Its type doesn't mention the element type. You also cannot write an instance for Set, because it requires an Ord constraint - but the class head doesn't mention the element type, so you cannot constrain it.

Associated types provide a neat way to completely fix these problems:

 class HasFirst c where   type Element c :: *   first :: c -> Maybe (Element c)  instance HasFirst [x] where   type Element [x] = x   first []    = Nothing   first (x:_) = Just x  instance HasFirst ByteString where   type Element ByteString = Word8   first b = b ! 0  instance Ord x => HasFirst (Set x) where   type Element (Set x) = x   first s = findMin s 

We now have a new problem, however. Consider trying to "fix" Functor so that it works for all container types:

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

This doesn't work at all. It says that if we have a function from the element type of f to the element type of f2, then we can turn an f into an f2. So far so good. However, there is apparently no way to demand that f and f2 are the same sort of container!

Under the existing Functor definition, we have

 fmap :: (x -> y) -> [x] -> [y] fmap :: (x -> y) -> Seq x -> Seq y fmap :: (x -> y) -> IO x -> IO y 

But we do not have fmap :: (x -> y) -> IO x -> [y]. That is quite impossible. But the class definition above allows it.

Does anybody know how to explain to the type system what I actually meant?

Edit

The above works by defining a way to compute an element type from a container type. What happens if you try to do it the other way around? Define a function to compute a container type from an element type? Does that work out any easier?

Answer 1

Well, the problem is that it's not clear what the revised Functor is supposed to mean. For instance, consider ByteString. A ByteString can only be mapped by replacing each Word8 element with an element of the same type. But Functor is for parametric mappable structures. There are really two conflicting notions of mapping here:

• Rigid mapping (i.e. transforming each element of a structure without changing its type)
• Parametric mapping (i.e. transforming each element of a structure to any type)

So, in this case, you can't explain to the type system what you meant, because it doesn't make much sense. You can, however, change what you mean :)

Rigid mapping is easy to express with type families:

class RigidMap f where   type Element f :: *   rigidMap :: (Element f -> Element f) -> f -> f 

As far as parametric mapping, there are multiple ways to do it. The simplest way would be to retain the current Functor as-is. Together, these classes covers structures like ByteString, [], Seq, and so on. However, they all fall down on Set and Map, because of the Ord constraint on values. Happily, the constraint kinds extension coming in GHC 7.4 lets us fix this problem:

class RFunctor f where   type Element f a :: Constraint   type Element f a = ()  -- default empty constraint   fmap :: (Element f a, Element f b) => (a -> b) -> f a -> f b 

Here, we're saying that every instance should have an associated typeclass constraint. For instance, the Set instance will have Element Set a = Ord a, to denote that Sets can only be constructed if an Ord instance is available for the type. Anything that can appear on the left hand of => is accepted. We can define our previous instances exactly as they were, but we can also do Set and Map:

instance RFunctor Set where   type Element Set a = Ord a   fmap = Set.map  instance RFunctor Map where   type Element Map a = Ord a   fmap = Map.map 

However, it's pretty annoying to have to use two separate interfaces for rigid mapping and restricted parametric mapping. In fact, isn't the latter a generalisation of the former? Consider the difference between Set, which can only contain instances of Ord, and ByteString, which can only contain Word8s. Surely we can express that as just another constraint?

We apply the same trick done to HasFirst (i.e. give instances for the whole structure and use a type family to expose the element type), and introduce a new associated constraint family:

class Mappable f where   type Element f :: *   type Result f a r :: Constraint   map :: (Result f a r) => (Element f -> a) -> f -> r 

The idea here is that Result f a r expresses the constraints it needs on the value type (like Ord a), and also constrains the resulting container type however it needs to; presumably, to ensure it has the type of a same-sort-of-container of as. For instance, Result [a] b r will presumably require that r is [b], and Result ByteString b r will require that b is Word8, and r is ByteString.

Type families already give us what we need to express "is" here: a type equality constraint. We can say (a ~ b) => ... to require that a and b are the same type. We can, of course, use this in constraint family definitions. So, we have everything we need; on to the instances:

instance Mappable [a] where   type Element [a] = a   type Result [a] b r = r ~ [b]   -- The type in this case works out as:   --   map :: (r ~ [b]) => (a -> b) -> [a] -> r   -- which simplifies to:   --   map :: (a -> b) -> [a] -> [b]   map = Prelude.map  instance Mappable ByteString where   type Element ByteString = Word8   type Result ByteString a r = (a ~ Word8, r ~ ByteString)   -- The type is:   --   map :: (b ~ Word8, r ~ ByteString) => (Word8 -> b) -> ByteString -> r   -- which simplifies to:   --   map :: (Word8 -> Word8) -> ByteString -> ByteString   map = ByteString.map  instance (Ord a) => Mappable (Set a) where   type Element (Set a) = a   type Result (Set a) b r = (Ord b, r ~ Set b)   -- The type is:   --   map :: (Ord a, Ord b, r ~ Set b) => (a -> b) -> Set a -> r   -- (note the (Ord a) constraint from the instance head)   -- which simplifies to:   --   map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b   map = Set.map 

Perfect! We can define instances for any type of container we want, rigid, parametric or parametric-but-restricted, and the types work out perfectly.

Disclaimer: I haven't tried GHC 7.4 yet, so I don't know if any of this actually compiles or works, but I think the basic ideas are sound.