Haskell "Could not deduce..."

Question

I'm a beginner to Haskell and was implementing some basic algebra, like

class (Eq g) => AbelianGroup g where
    gplus :: g -> g -> g
    gnegate :: g -> g 
    gzero :: g
    gminus :: g -> g -> g
    gminus a b = gplus a (gnegate b)
    gmult :: Integer -> g -> g

class (AbelianGroup d) => IntegralDomain d where
    idtimes :: d -> d -> d
    idone :: d            

{- you can ignore upper code, it is added only for sake of completeness -}

class (IntegralDomain d) => EuclideanDomain d where
    edeg :: d -> Integer
    edivision :: d -> d -> (d, d)
    egcd :: d -> d -> d
    egcd f g | g == gzero = f 
             | f == gzero = g
             | otherwise = let (q, r) = edivision f g in egcd g r

class (IntegralDomain f) => Field f where
    finvert :: f -> f
    fdivide :: f -> f -> f
    fdivide a b = idtimes a (finvert b)

instance (Field f, IntegralDomain f) => EuclideanDomain f where
    edeg x = 0
    edivision x y = (fdivide x y, gzero)

when I got the error

* Could not deduce (Field d) arising from a use of `edivision'
  from the context: EuclideanDomain d
  bound by the class declaration for `EuclideanDomain'
  at ...
  Possible fix:
  add (Field d) to the context of
  the class declaration for `EuclideanDomain'
* In the expression: edivision f g
  In a pattern binding: (q, r) = edivision f g
  In the expression: let (q, r) = edivision f g in egcd g r

where the error comes - as in error statement - from "edivision f g" in the dafault definiton of "egcd" in "EuclideanDomain". So as I am new to Haskell, my question is

Why is there this error?

If I put (Field d) in the declaration of EuclideanDomain, this error vanishes. But then of course, the whole code becomes useless (not every Euclidean Domain is a Field etc.)

Answer 1

tl;dr You probably don't want to do what you're trying to do. It creates too much complexity within the type system. The easy solution is to just not write an instance as generic as the one you're trying to write.

The Long Version

instance (Field f, IntegralDomain f) => EuclideanDomain f where

You don't want to do this. I don't believe Haskell will even let you do this by default (you may have turned on some compiler extensions to get it to work at some point). What you're saying here is "every field is a Euclidean domain in the way that I say so". If someone comes along and makes a new type Foo, they may want to define an instance for EuclideanDomain and Field, but if they do then there are two instances of EuclideanDomain for the same type.

This is a problem. You can tell GHC to ignore this problem and just hope things work out with the OverlappingInstances compiler extension, but like I said, you probably don't want to do that, because it makes your code significantly more confusing. You'll probably also need FlexibleInstances and perhaps a few other ones to get a typeclass instance that generic to pass the typechecker. Now, you've got two options.

Option 1

Just let sleeping dogs lie and assume the user is smart enough to implement both Field and EuclideanDomain. If you want to do this, you can make it easy for them by providing "default" functionality that they can just copy into their instance declaration if they truly want to derive EuclideanDomain from Field.

edegDefault :: Field f => f -> Integer
edegDefault x = 0
edivisionDefault :: Field f => f -> f -> (f, f)
edivisionDefault x y = (fdivide x y, gzero)

Then the user can implement EuclideanDomain of their own accord. If they want to implement the functionality themselves, they can do so freely, but if they don't, they can always do this.

instance EuclideanDomain f where
    edeg = edegDefault
    edivision = edivisionDefault

Option 2

The other option, which you see from time to time, is more for the cases where the user might genuinely forget to implement EuclideanDomain. In this case, we would wrap our Field instance in a newtype and declare that newtype to be a EuclideanDomain.

newtype WrappedField f = WrappedField f

instance Field f => EuclideanDomain (WrappedField f) where
    ...

Then you still get the functionality without intruding on the user's instance space. This pattern is seen in the Haskell standard library. For the longest time, Monad was not a subclass of Applicative for historical reasons, even though mathematically it should have been. So, the Haskell language designers implemented a WrappedMonad newtype which took a Monad instance and provided the Applicative instance for it.