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.

Answer 2

You want constraint kinds, available in ghc 7.4.