Changes between Version 2 and Version 3 of FlexibleInstances


Ignore:
Timestamp:
Dec 12, 2005 11:55:47 AM (10 years ago)
Author:
ross@…
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • FlexibleInstances

    v2 v3  
    66== Brief Explanation ==
    77
    8 In Haskell 98, instance declarations must have the form `instance` (C1 v1, ..., Cn vn) `=>` 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.
     8In Haskell 98,
     9 * an instance head must have the form C (T u,,1,, ... u,,k,,), where T is a type constructor defined by a `data` or `newtype` declaration (see TypeSynonymInstances) and the u,,i,, are distinct type variables, and
     10 * each assertion in the context must have the form C' v, where v is one of the u,,i,,.
     11
    912
    1013Without restrictions on the form of instances, constraint checking is undecidable (see UndecidableInstances).
    11 A conservative rule that ensures termination (used by GHC with `-fglasgow-exts`) is to require instance heads of the form  `instance` (C1 vs1, ..., Cn vsn) `=>` C t1 ... tk, where at least one of the ti is not a type variable (assuming MultiParamTypeClasses). The non-variable restriction can be onerous if OverlappingInstances are permitted.
     14A conservative rule (used by GHC with `-fglasgow-exts`) that ensures termination is:
     15 * at least one of the type arguments of the instance head must be a non-variable type, and
     16 * each assertion in the context must have the form C v,,1,, ... v,,n,,, where the v,,i,, are distinct type variables.
     17The distinctness requirement prohibits non-terminating instances like
     18{{{
     19instance C b b => C (Maybe a) b
     20}}}
     21Note that repeated type variables are permitted in the instance head, e.g.
     22{{{
     23instance MArray (STArray s) e (ST s)
     24}}}
    1225
    13 Note that repeated type variables are permitted.
    14 
    15 If the language has FlexibleInstances like
     26With this extension, one can write instances like
    1627{{{
    1728instance C [Bool] where ...
    1829instance C [Char] where ...
    1930}}}
    20 assertions like `C [a]` can be neither reduced nor rejected, so FlexibleContexts are also needed.
     31and assertions like `C [a]` can be neither reduced nor rejected, so FlexibleContexts are also needed.
    2132
    2233== References ==
     
    2637
    2738== Pros ==
    28  * Pro
    29  * Pro
     39 * Such instances often arise with MultiParamTypeClasses.
    3040
    3141== Cons ==
    32  * Con
    33  * Con
     42 * The above restrictions rule out some useful instances, e.g. derived instances like:
     43   {{{
     44data Sized s a = N Int (s a)
     45        deriving (Show)
     46}}}
     47   remain illegal, because the inferred instance has an illegal context:
     48   {{{
     49instance Show (s a) => Show (Sized s a)
     50}}}
     51   (see [http://www.haskell.org/onlinereport/decls.html#sect4.5.3 Context reduction errors] in the Haskell 98 Report). The following examples from the GHC User's Guide are also forbidden:
     52   {{{
     53instance C a
     54instance (C1 a, C2 a, C3 a) => C a
     55}}}
     56   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.