haskell : making a superclass of Num

Question

I want to make a superclass of Num, called Linear

class Linear a where 
  add :: a -> a -> a

instance (Num a) => Linear a where
  add = (+)

I get the error :

Illegal instance declaration for `Linear a'
  (All instance types must be of the form (T a1 ... an)
   where a1 ... an are *distinct type variables*,
   and each type variable appears at most once in the instance head.
   Use -XFlexibleInstances if you want to disable this.)
In the instance declaration for `Linear a'

From what I understand, something about the line instance (Num a) => Linear a where is incorrect. (It compiles if I use the flags : -XFlexibleInstances -XUndecidableInstances)

Is there a way to achieve this without using those scary flags? (and what in the world is undecidable about the code above??)

UPDATE : Added Polynomial type to Linear.

newtype Polynomial a = Polynomial (a,[a]) deriving Show-- list of coeffients 

instance (Linear a) => Linear (Polynomial a)
         where 
           add (Polynomial (c1, l1)) (Polynomial (c2, l2))
             = Polynomial (add c1 c2, zipWith (add) l1 l2)

p1 = Polynomial (0, [3,4,5])
p2 = Polynomial (0, [])

main = putStrLn $ show ((add p1 p2):: Polynomial Int)

After adding polynomial, it doesn't compile with even those flags and give the error:

Overlapping instances for Linear (Polynomial Int)
  arising from a use of `add'
Matching instances:
  instance Num a => Linear a -- Defined at Algebra.hs:22:10-28
  instance Linear a => Linear (Polynomial a)
    -- Defined at Algebra.hs:25:10-44
In the first argument of `show', namely
  `((add p1 p2) :: Polynomial Int)'
In the second argument of `($)', namely
  `show ((add p1 p2) :: Polynomial Int)'
In the expression: putStrLn $ show ((add p1 p2) :: Polynomial Int)

Answer 1

The language report doesn't allow instances of the form instance Class a where..., so the only way to avoid FlexibleInstances (which is not scary in the least) would be to use a newtype wrapper,

newtype LinearType a = Linear a

liftLin2 :: (a -> b -> c) -> LinearType a -> LinearType b -> LinearType c
liftLin2 op (Linear x) (Linear y) = Linear (op x y)

instance Num a => Linear (LinearType a) where
    add = liftLin2 (+)

Yuck.

The UndecidableInstances extension is needed because the constraint Num a is not smaller than the instance head (it uses the same type variables the same number of times), so the compiler can't prove in advance that type checking will terminate. Thus you have to promise to the compiler that type checking will terminate for it to accept the programme (it won't actually loop with GHC, that has a context stack that controls recursion-depth of the type checker, so if type checking doesn't finish soon enough, it will fail the compilation with "context stack exceeded" - you can set the size with -fcontext-stack=N).

This extension sounds much scarier than it is. Basically all it does is tell the compiler "Trust me, type checking will terminate" so the compiler will start without knowing for sure that it will finish.

But, what are you trying to achieve? What you currently have,

instance (Num a) => Linear a where
  add = (+)

says "every type is an instance of Linear, and if you try to use add at a type not an instance of Num, that is a compile-time error". It's not very useful. You cannot add further instances for types not belonging to Num, unless you enable also OverlappingInstances and possibly IncoherentInstances. And those extensions are scary, they should be used scarcely and only when you know what you're doing.

Answer 2

There is a proposal to allow the declaration of superclasses. AFAIK it's not implemented yet, but as GHC is open source, you may change that if you want ;)