[Haskell-cafe] Type class context propagation investigation

[Ryan Ingram]

Think of classes like data declarations; an instance with no context
is a constant, and one with context is a function.  Here's a simple
translation of your code into data; this is very similar to the
implementation used by GHC for typeclasses:

> data EqDict a = EqDict { eq :: a -> a -> Bool }
> data ShowDict a = ShowDict { show :: a -> String }
> data NumDict a = NumDict { num_eq :: EqDict a, num_show :: ShowDict a, plus :: a -> a -> a }

The goal of the compiler is to turn your instance declarations into
these structures automatically.  Here's a translation of your original
instance:

> eq_foo :: EqDict (Foo a)
> eq_foo = EqDict { eq = undefined }

> show_foo :: ShowDict (Foo a)
> show_foo = ShowDict { show = undefined }

> num_foo :: NumDict (Foo a)
> num_foo = NumDict { num_eq = eq_foo, num_show = show_foo, plus = undefined }

Now if you add a constraint on the "Eq" instance, this means that eq
from eq_foo might refer to eq in the dictionary for "a".  How do we
get that dictionary?  We just pass it as an argument!

> eq_foo :: EqDict a -> EqDict (Foo a)
> eq_foo eq_a = EqDict { eq = undefined }

However, you don't have a similar constraint on the Num instance:

> num_foo :: NumDict (Foo a)
> num_foo = NumDict { num_eq = eq_foo <something>, num_show = show_foo, plus = undefined }

The compiler wants to fill in <something>, but it can't; it doesn't
have a dictionary of the type EqDict a.  So it tells you so, saying
that Eq a is missing!

Once you add the (Eq a) constraint to the Num instance, it works:

> num_foo :: EqDict a -> NumDict (Foo a)
> num_foo eq_a = NumDict { num_eq = eq_foo eq_a, num_show = show_foo, plus = undefined }

You can also add a (Num a) constraint instead, and the compiler can
use it to get the Eq instance out:

> num_foo :: NumDict a -> NumDict (Foo a)
> num_foo num_a = NumDict { num_eq = eq_foo (num_eq num_a), num_show = show_foo, plus = undefined }

Of course, I'm glossing over the interesting details of the search,
but the basic idea is to attempt to fill in the blanks in these
definitions.

  -- ryan

On Wed, May 27, 2009 at 2:10 PM, Paul Keir <pkeir at dcs.gla.ac.uk> wrote:
> Hi,
>
> How does the context of a class instance declaration affect its subclasses?
>
> The Num class instance outlined below has its requirement for Eq and Show
> satisfied on the preceding lines, and the code will compile. But if I, say,
> add an (Eq a) constraint to the Eq instance, in preparation for a simple
> (==) definition, I find that the Num instance declaration is left lacking.
> If I add the same (Eq a) constraint now to Num, calm is restored.
>
> data Foo a = F a
>
> instance Eq (Foo a) where
>  (==) = undefined
>
> instance Show (Foo a) where
>  show = undefined
>
> instance Num (Foo a)
>  (+) = undefined
>  ... etc.
>
> The thing that confuses me with this is that it seems like Num "knows" that
> an (Eq a) context has been applied, and so what it sees as a problem, is
> somehow also the solution. Any advice/rules of thumb? Does this situation
> occur elsewhere? How do these constraints propagate?
>
> Thanks,
> Paul
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>