[Haskell-cafe] Overlapping instance problem
Robert Dockins
robdockins at fastmail.fm
Mon Feb 13 15:48:54 EST 2006
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
More information about the Haskell-Cafe
mailing list