Enumerating an associated type in a typeclass

Question

Given a typeclass definition like the following, I'd like to enumerate the MyClassId a type for any type that is an instance of MyClass.

{-# LANGUAGE TypeFamilies     #-}
{-# LANGUAGE FlexibleContexts #-}

class
  ( Enum (MyClassId e)
  , Bounded (MyClassId e))
  => MyClass e where
    type MyClassId e :: *

enumMyClassId :: MyClass a => [MyClassId a]
enumMyClassId = enumFrom minBound

However, when I try to compile this snippet of code, GHC 7.10.2 complains with the following message:

enumTypeClass.hs:12:18:
    Couldn't match type ‘MyClassId a0’ with ‘MyClassId a’
    NB: ‘MyClassId’ is a type function, and may not be injective
    The type variable ‘a0’ is ambiguous
    Expected type: [MyClassId a]
      Actual type: [MyClassId a0]
    In the ambiguity check for the type signature for ‘enumMyClassId’:
      enumMyClassId :: forall a. MyClass a => [MyClassId a]
    To defer the ambiguity check to use sites, enable AllowAmbiguousTypes
    In the type signature for ‘enumMyClassId’:
      enumMyClassId :: MyClass a => [MyClassId a]

I am not exactly sure why it can't infer that the a type variable is the same as the a in the constraint for the function enumMyClassId. One possible fix is to change the function enumMyClassId to the following:

enumMyClassId :: MyClass a => a -> [MyClassId a]
enumMyClassId _ = enumFrom minBound

But this is not very elegant as it introduces an unused variable just to make the program typecheck. Is there some solution that doesn't involve the trick above?

You may also like the universe family of packages, which offers universe :: Universe a => [a] as a canonical way to enumerate a given type. It has many instances that are not covered by the (Enum a, Bounded a) constraint -- and skips a few instances that would be covered by that, but in the wrong way, like Double. — Daniel Wagner

dfeuer dfeuer · Accepted Answer · 2015-12-05T21:59:15

The reason your function is rejected is that any attempt to use it will result in ambiguity. At the use site, you can give a signature that constrains MyClassId a, but you can't specify a. You should be able to defer the error message to the use site (where it will be easier to understand) by temporarily enabling AllowAmbiguousTypes.

There are two idiomatic fixes:

Use a proxy

enumMyClassId :: MyClass a => proxy a -> [MyClassId a]

You'd typically pass this a Proxy from Data.Proxy, but you can also use an arbitrary value whose type's last argument is a.

Use a tagged type

This approach is typically less convenient, but sometimes is important for getting things to be memoized.

Edward Kmett's tagged package gives you

newtype Tagged s b = Tagged {unTagged :: b}

Then you'd write

enumMyClassId :: MyClass a => Tagged a [MyClassId a]

And call it

enumMyClassId :: Tagged a [MyClassId a]

There's also a GHC-special approach that's not even intended ever to be portable, but that gives performance like tagged types with proxy convenience.

Magic proxy

You can use the magical Proxy# type that GHC completely erases in compilation. This works just like the first solution, but uses a Proxy# a type instead of a proxy a one. When calling such a function, you pass proxy#, which is a totally fake value.

Enumerating an associated type in a typeclass

1 Answers

Use a proxy

Use a tagged type

Magic proxy