[Haskell-cafe] type classes

[Dan Doel]

On Wednesday 02 July 2008, Cotton Seed wrote:
> Hi everyone,
>
> I'm working on a computational algebra program and I've run into a problem.
> In my program, I have types for instances of algebraic objects, e.g. ZModN
> for modular integers, and types for the objects themselves, e.g. ZModNTy
> for the ring of modular integers.
>
> Now, I want to subclass ZModNTy from something like
>
> class RingTy a b where
>   order :: a -> Integer
>   units :: a -> [b]
>
> where `a' represents algebraic object, and `b' the type of instances of
> that object.  I want an instance
>
> instance RingTy ZModNTy ZModN where ...
>
> but then code that only uses order fails with errors like
>
>     No instance for (RingTy ZModNTy b)
>       arising from a use of `order' at Test2.hs:16:8-15
>
> since there is no constraint on the second type variable.
>
> I think what I really want is
>
> class RingTy a where
>   order :: a b -> Integer
>   units :: a b -> [b]
>
> but this doesn't work either since ZModNTy is not parametric in its type
> like, say, `Polynomial a' is.
>
> Is this a common problem?  Is there a standard way to handle it?

Correct me if I'm wrong, but wouldn't the a uniquely determine the b? In that 
case, you'd probably want a functional dependency:

  class RingTy a b | a -> b where
    order :: a -> Integer
    units :: a -> [b]

This solves the problem with order, because with multi-parameter type classes, 
all the variables should be determined for a use of a method. Since b is not 
involved with order, it could be anything, so it's rather ambiguous. The 
functional dependency solves this by uniquely determined b from a, so order 
is no longer ambiguous.

Alternately, with the new type families, this can become:

  class RingTy a where
    type RingElem a :: *
    order :: a -> Integer
    units :: a -> [RingElem a]

Or something along those lines.

Hope that helps.
-- Dan