6

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)
Karan
  • 559
  • 5
  • 12

2 Answers2

10

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.

Daniel Fischer
  • 181,706
  • 17
  • 308
  • 431
  • thanks for explaining this, but isn't there a standard/default way of making a superclass that doesn't require the user to give the compiler any assurances ? – Karan Mar 26 '12 at 11:27
  • I want to make some instances of Linear, and I want everything this is Num to also be Linear. (i.e. Linear is superclass of Num and has more instances than Num) – Karan Mar 26 '12 at 11:45
  • I came to suspect such. That's not what usually is called a superclass, though. However, that would take you into `OverlappingInstances` territory, and that's not very cozy. For `Polynomial`, it would make sense to have an `instance Num a => Num (Polynomial a) where...`. `abs` and `signum` would be a little suspicious, but everything else in `Num` makes immediate sense for polynomials. – Daniel Fischer Mar 26 '12 at 11:53
  • that means everything of type Linear will have to have instance definition for Num with absurd definitions - not a good workaround !! – Karan Mar 26 '12 at 11:54
  • Well, the instance resolution (in GHC at least) takes only the part after the "=>" into account, so `instance (Context a) => Foo a` does say every type is an instance of `Foo`. Only when it's used, then the compiler tries to look up the `Context a` instance. It's unintuitive, but there are good reasons for that. – Daniel Fischer Mar 26 '12 at 11:59
  • You can provide instances for `Linear` that aren't instances of `Num` with `OverlappingInstances`. Sometimes that is the right thing, maybe here. – Daniel Fischer Mar 26 '12 at 12:01
  • using OverlappingInstances works but all this work just to get superclass/supertype makes me think if I should be doing this in a dynamically typed language instead :) – Karan Mar 26 '12 at 12:08
  • @Karan - this used to bother me too, but do you really need an `instance Linear` for *every* `Num`? I usually end up just writing instances for `Int` and `Double`, and possibly `Integer`, and that's enough. Or you could use metaprogramming (CPP or template Haskell) to generate instance declarations, but that's usually not worth the trouble. – John L Mar 26 '12 at 13:31
  • Forgot to mention, but if you're using a new GHC you can use the DefaultSignatures extension when defining Linear to do what you want. – John L Mar 26 '12 at 13:34
  • Honestly, I'd say that it's mostly just that introducing "superclasses" for type classes you don't control is just much more awkward than when you do control them. – Louis Wasserman Mar 26 '12 at 14:28
  • @JohnL - I don't have a specific real-world aim that I was trying for. I was just trying to do some algebra and wanted that already existing and user(me)-defined instances of Num should automatically become part of Linear. And I will try DefaultSignature, though I am not able to find a web-page that says what it is (google returns some mailing list entries). Can you point me to one ? – Karan Mar 26 '12 at 15:19
  • @Karan: sorry, the GHC docs are at http://www.haskell.org/ghc/docs/7.4.1/html/users_guide/type-class-extensions.html, see section 7.6.1.4. You'd still have to write `instance Linear Int where; instance Linear Float where` etc., but all the methods would be filled in by the default signature. – John L Mar 26 '12 at 16:58
  • @JohnL : Thanks, that page seems very useful. – Karan Mar 26 '12 at 18:10
3

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 ;)

fuz
  • 88,405
  • 25
  • 200
  • 352
  • can you suggest a workaround in the mean time (which does not involve making everything of type Num (ie Int, Float etc) an instance of Linear manually ) – Karan Mar 26 '12 at 11:53
  • The question is, what you really want to do. Depending on your problem, there may be different solutions to your problem. – fuz Mar 26 '12 at 12:35