[Haskell-cafe] Overlapping instance problem

[Robert Dockins]

On Feb 13, 2006, at 2:26 PM, Jeff.Harper at handheld.com wrote:

>
> Hi,
>
> I've posted a couple messages to the Haskell Cafe in the last few  
> months.  I'm new to Haskell.  But, I've set out to implement my own  
> vectors, matrices, complex numbers, etc.
>
> One goal I have, is to overload operators to work with my new  
> types.  The pursuit of this goal, has pushed me to learn a lot  
> about the
> Haskell type system. When I get stuck from time-to-time, the kind  
> folks on this list have pointed me in the right direction.
>
> I'm stuck now.  One thing I want to avoid is adding new  
> multiplication operators to handle multiplication of dissimilar  
> types.  For instance, I'd like to be able to have an expression  
> like k * m where k is a Double and m is a Matrix.  This doesn't  
> work with the prelude's (*) operator because the prelude's (*) has  
> signature:
>
> (*) :: (Num a) => a -> a -> a.
>
> To get around this, I wrote my own versions of a Multiply class  
> that allows dissimilar types to be multiplied.  You can see my  
> Multiply class in the module at the end of this Email.

[snip error message]

> I don't understand how m1 * m2 can match the scalar multiplication  
> instances.  For instance, the scalar * matrix instance has signature:
>
> instance (Multiply a b c, Num a, Num b, Num c)
>                                => Multiply a (Matrix b) (Matrix c)  
> where
>
> m1 in my expression would correspond to the 'a' type variable.   
> But, 'a' is constrained to be a Num.  However, I never made my  
> Matrix type an instance of Num.
>
> Is there a work around for this?  In my first implementation, I did  
> not have the Num constraints in the matrix Multiply instances.  I  
> added the Num constraints specifically, to remove the ambiguity of  
> the overlapping instance.  Why didn't this work?

I'm pretty sure this is due to a misfeature of the way class class  
instance selection works.  Essentially, the typechecker IGNORES the  
instance context (everything before the =>) when looking for matches,  
and it only checks the context after it has irrevocably selected an  
instance.  Thus, rather than backtracking and trying to find another  
instance, the typechecker just gives you errors about unsatisfied  
constraints or overlapping instance errors.  Often this isn't what  
you want (as in this case).

To be fair, doing better than this (in general) seems pretty  
difficult.  The typechecker sometimes needs to have more information  
than it can currently gather.  I think the following extension  
proposal might address this problem (if its ever implemented...)

http://www.haskell.org/pipermail/haskell-prime/2006-February/000423.html

As of now, the typechecker can't be absolutely certain that 'Matrix'  
isn't (and will never be) an instance of 'Num'.  Just because you  
haven't make it a member of 'Num' doesn't mean someone else  
couldn't!  For it to do what you want, the typechecker needs to be  
able to prove that, given any legal collection of instances, the  
instance declarations in question will not overlap.  It can't to that.


As to workarounds... that becomes more difficult.  Essentially you  
need to replace the bare type variable 'a' in your instance  
declarations with something that can guide the typechecker to select  
the 'correct' instance.  Two options come to mind:

1) create a 'newtype' for scalars.  Now you have to wrap and unwrap  
your scalars, which is a bit of a pain, but it is a fully general  
solution.  Judicious use of newtype deriving may eliminate some of  
this pain.

2) Create separate 'Multiply' instances for each type of scalar you  
want to use.  Eliminates the ugly wrapping/unwrapping, but limits the  
types of scalars you can use.




Rob Dockins

Speak softly and drive a Sherman tank.
Laugh hard; it's a long way to the bank.
           -- TMBG



-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org//pipermail/haskell-cafe/attachments/20060213/92759193/attachment.htm