typeclasses without methods, used as constraints: do they get dictionaries?

Question

If I'm using a typeclass to overload methods, that's implemented in 'dictionary passing style'. That is, the method gets an extra argument (that doesn't appear in surface Haskell); to resolve overloading the method looks up the dictionary by type of its 'proper' argument(s); and pulls a method implementation out of the dictionary. As described in this q, for example.

But what about typeclasses without methods? They can be used as constraints. Is there a dictionary for them? What does it contain?

For a specific example:

module M  where

class C a             -- no methods
                      -- no instances in module M
f :: C a => a -> Bool
f x = blah

There's no instances for C in this module, so if M gets imported into some other module (with C instances) how is f's dictionary lookup encoded?

The usual situation would be that class C has method(s); there's calls to them on RHS of the equation for f; so the wanted C a is encoded as a dictionary lookup for the method call.

Supplementary q's: (if anybody's still listening)

2a. For no-method typeclasses with superclass constraints: Where do the constraints go in the dictionary? A comment on a ticket from SPJ seems to suggest it's an argument to the dictionary's data constructor.

2b. For no-method typeclass instances with constraints: Again where do the constraints go in the dictionary?

Motivation

@Daniel in the comments is asking the motivation for these q's. Apart from just understanding compiler internals a bit better ...

GHC translates surface Haskell into an Internal Representation: System F_C, which has aot explicit type signatures at every function application. (Those applications must include applying to the dictionaries for a class.) I'm trying to understand where all the type-related components of class and instance decls go inside the dictionaries; to figure out how a term in F_C gets to an equivalent representation to the original Haskell. Then I don't understand how [typeclasses without methods] fit in. Because those classes cannot appear directly as terms in surface Haskell, but only as constraints. Then it must be dictionar(ies) for such a class that represent it at term level.

If you want to ask where this is going: there seems to be a limitation in F_C that it can't represent Functional Dependencies. Something to do with being unable to generate type-level evidence. Then I want to understand how that limitation arises/what about FunDeps can't be (or currently isn't) represented?

Answer 1

Is there a dictionary for [typeclasses without methods]? What does it contain?

Yes, there is a dictionary with no fields.

Compare:

class Monoid a where
    mempty :: a
    mappend :: a -> a -> a
data DictMonoid a = DictMonoid a (a -> a -> a)

class C a
data DictC a = DictC

If M gets imported into some other module (with C instances) how is f's dictionary lookup encoded?

Type inference is used to determine what instance is needed when f is called; then GHC looks up that type in its collection of known instances (=known dictionaries).

One possible outcome of this process is that the instance we determine would be needed is polymorphic, and there is no fully polymorphic instance. Then the appropriate constraint (such as C a or C m or whatever) is attached to the inferred type of whatever term is calling f -- which is then compiled to a function which accepts a dictionary on f's behalf and passes it on.

For no-method typeclasses with superclass constraints: Where do the constraints go in the dictionary?

Somewhere. There's no observation you can make from the surface language to distinguish between different places. For example, consider:

class Semigroup a => Monoid a where mempty :: a
data DictMonoid1 a = DictMonoid1 (DictSemigroup a) a
data DictMonoid2 a = DictMonoid2 a (DictSemigroup a)

These are sort of the only two choices one could make for where to put the superclass' dictionary. But what difference could it possibly make?

Okay, but you asked about no-method typeclasses. But the answer is the same. You can't tell the order that superclass dictionaries are stored in.

class (A a, B a) => C a
data DictC1 a = DictC1 (DictA a) (DictB a)
data DictC2 a = DictC2 (DictB a) (DictA a)

What could you possibly do to tell the difference between these? Nothing.

For no-method typeclass instances with constraints: Again where do the constraints go in the dictionary?

Nowhere. They become arguments that the caller must supply to receive a dictionary. Particular fields of the supplied dictionary may be closed over by the new dictionary, of course. Example:

class Ord a where compare :: a -> a -> Ordering
data DictOrd a where DictOrd (a -> a -> Ordering)

instance (Ord a, Ord b) => Ord (a, b) where
    compare (a,b) (a',b') = compare a a' <> compare b b'
instanceOrdTuple :: DictOrd a -> DictOrd b -> DictOrd (a,b)
instanceOrdTuple (DictOrd comparea) (DictOrd compareb)
    = DictOrd $ \(a,b) (a',b') -> comparea a a' <> compareb b b'

Okay, but you asked about no-method typeclasses. But the answer is not significantly different. The instance's constraint dictionaries are not stored anywhere, just like before; the only difference is that now we can also be sure that even the fields of the supplied dictionaries are not closed over.

class A a where whateverA :: a -> Int
class B a where whateverB :: Int -> a
class C a
data DictA a = DictA (a -> Int)
data DictB a = DictB (Int -> a)
data DictC a = DictC

instance (A a, B a) => C [a]
instanceCList :: DictA a -> DictB a -> DictC [a]
instanceCList (DictA whateverAa) (DictB whateverBa) = DictC

The following commentary replies to an old version of the question.

There's no instances for C in this module, so the compiler can't discharge fs constraint.

It doesn't need to. f is compiled to a function which takes a dictionary as an argument; there's no need to create a dictionary to compile f, only to compile its callers.

The compiler can't discharge the C Char constraint arising from the equation for y. What does it do?

It reports that it can't discharge the C Char constraint and exits unsuccessfully. (This hardly even qualifies as a question -- just try it and see for yourself!)