Changes between Version 2 and Version 3 of FlexibleInstances


Ignore:
Timestamp:
Dec 12, 2005 11:55:47 AM (8 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.