wiki:FlexibleInstances

Version 3 (modified by ross@…, 10 years ago) (diff)

--

Flexible Instances

See ExtensionDescriptionHowto for information on how to write these extension descriptions. Please add any new extensions to the list of HaskellExtensions.

Brief Explanation

In Haskell 98,

  • an instance head must have the form C (T u1 ... uk), where T is a type constructor defined by a data or newtype declaration (see TypeSynonymInstances) and the ui are distinct type variables, and
  • each assertion in the context must have the form C' v, where v is one of the ui.

Without restrictions on the form of instances, constraint checking is undecidable (see UndecidableInstances). A conservative rule (used by GHC with -fglasgow-exts) that ensures termination is:

  • at least one of the type arguments of the instance head must be a non-variable type, and
  • each assertion in the context must have the form C v1 ... vn, where the vi are distinct type variables.

The distinctness requirement prohibits non-terminating instances like

instance C b b => C (Maybe a) b

Note that repeated type variables are permitted in the instance head, e.g.

instance MArray (STArray s) e (ST s)

With this extension, one can write instances like

instance C [Bool] where ...
instance C [Char] where ...

and assertions like C [a] can be neither reduced nor rejected, so FlexibleContexts are also needed.

References

Pros

Cons

  • The above restrictions rule out some useful instances, e.g. derived instances like:
    data Sized s a = N Int (s a)
            deriving (Show)
    
    remain illegal, because the inferred instance has an illegal context:
    instance Show (s a) => Show (Sized s a)
    
    (see Context reduction errors in the Haskell 98 Report). The following examples from the GHC User's Guide are also forbidden:
    instance C a
    instance (C1 a, C2 a, C3 a) => C a
    
    An alternative criterion using a multiset path ordering would allow the Sized example and the first of these, but the second cannot be shown to terminate without considering other instances in the program.