Changes between Version 10 and Version 11 of DefaultSuperclassInstances


Ignore:
Timestamp:
Mar 12, 2011 5:48:14 PM (3 years ago)
Author:
simonpj
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • DefaultSuperclassInstances

    v10 v11  
    77 * A class can ''deepen'' its superclass (e.g., an implementation of Traversable f delivers at least enough technology to deliver Foldable f and Functor f).  
    88 
    9 ('''SLPJ''' I don't understand this distinction clearly.) This proposal concerns the latter phenomenon, which is currently such a nuisance that Functor and Applicative are not superclasses of Monad. Nobody wants to be forced to write Functor and Applicative instances, just to access the Monad interface. Moreover, any proposal to refine the library by splitting a type class into depth-layers is (rightly!) greeted with howls of protest as an absence of superclass instances gives rise to breakage of the existing codebase. 
     9('''SLPJ''' I don't understand this distinction clearly.)  
     10 
     11This 
     12proposal concerns the latter phenomenon, which is currently such a 
     13nuisance that Functor and Applicative are not superclasses of 
     14Monad. Nobody wants to be forced to write Functor and Applicative 
     15instances, just to access the Monad interface. Moreover, any proposal 
     16to refine the library by splitting a type class into depth-layers is 
     17(rightly!) greeted with howls of protest as an absence of superclass 
     18instances gives rise to breakage of the existing codebase. 
     19 
     20Default superclass instances are implemented in the 
     21[http://personal.cis.strath.ac.uk/~conor/pub/she/superclass.html Strathclyde Haskell Enhancement].  
     22They should enable some tidying of 
     23the library, with relatively few tears. Moreover, they should allow us 
     24to deepen type class hierarchies as we learn. Retaining backward 
     25compatibility in relative silence is the motivation for an opt-in 
     26default. 
    1027 
    1128== The proposal == 
    1229 
    1330Concretely, the proposal is as follows. 
     31 
     32=== Default superclass instances === 
    1433 
    1534First, we allow a class declaration to include a '''default superclass instance delcaration''' for some, none, or all of its superclass constraints. We say that superclasses with default implementations are '''intrinsic''' superclasses. Example: 
     
    3453        ff <*> fs = ff >>= \ f -> fs >>= \ s -> return (f s) 
    3554}}} 
    36 Here,  and `Applicative` is an intrinsic superclass of `Monad`. 
     55Here, `Applicative` is an intrinsic superclass of `Monad`. 
     56 
     57=== Instance declarations === 
     58 
     59A default superclass instance in a class declaration for class C 
     60has an effect on the instance declarations for C. 
     61 
     62Specifically: 
     63 * An instance declaration  
     64{{{ 
     65instance Q => C ty where ...defs... 
     66}}}  
     67   for class C generates an extra instance  
     68   declaration 
     69{{{ 
     70instance Q => Si ty where .... 
     71}}}  
     72   for each intrinsic superclass Si of C 
     73 
     74 * The method definitions in `...defs...` are distributed to the  
     75   appropriate instance declaration, according to which class 
     76   the method belongs to. 
     77 
     78 * Any methods that are not specified explicitly are "filled in" 
     79   from the default definition given in the default superclass instance. 
     80   (If there is no default definition, then a warning is produced, 
     81   and a definition that calls `error` is used instead.) 
     82 
     83For example, assume the class declaration for `Monad` above. Then 
     84this instance declaration: 
     85{{{ 
     86  instance Monad m where 
     87    (>>=) = ...blah... 
     88    (<*)  = ...bleh... 
     89}}} 
     90would generate an extra instance declaration for the instrinsic superclass `Applicative`, 
     91with the methods distributed appropriately: 
     92{{{ 
     93  instance Monad m where 
     94    (>>=) = ...blah... 
     95 
     96  instance Applicative m where 
     97    (<*) = ...bleh...  -- Programmer specified 
     98 
     99    ff <*> fs = ff >>= \ f -> fs >>= \ s -> return (f s) 
     100                       -- From the default superclass instance 
     101}}} 
     102We call these extra instance declarations an '''intrinsic instance declaration'''. 
     103(The term "derived instance" is already taken!) 
     104 
     105This process is recursive.  Since `Functor` is an intrinsic superclass of `Applicative`, 
     106the intrinsic instance for `Applicative` recursively  
     107generates an intrinsic instance for `Functor`: 
     108{{{ 
     109  instance Functor m where 
     110    fmap = (<*>) . return       -- From default superclass instance 
     111}}} 
     112 
     113== The opt-out mechanism ==  
     114 
     115Just because you can make default instances, they are not always the instances you want. A key example is 
     116{{{ 
     117    instance Monad m => Monad (ReaderT r m) where ... 
     118}}} 
     119which would give us by default the intrinsic instance 
     120{{{ 
     121    instance Monad m => Applicative (ReaderT r m) where ... 
     122}}} 
     123thus preventing us adding the more general 
     124{{{ 
     125    instance Applicative m => Applicative (ReaderT r m) where ... 
     126}}} 
     127To inhibit the generation of an intrinsic instance declaration, one can use a 
     128`hiding` clause in the instance declaration: 
     129{{{ 
     130    instance Sub x where 
     131      ... 
     132      hiding instance Super 
     133}}} 
     134which acts to prevent the generation of instances for Super and all of 
     135Super's intrinsic superclasses in turn. For example: 
     136write 
     137{{{ 
     138    instance Monad m => Monad (ReaderT r m) where ... 
     139      return x = ... 
     140      ba >>= bf = ... 
     141      hiding instance Applicative 
     142}}} 
     143The `hiding` clause applies to all the intrinsic instances generated 
     144from an instance declaration.  For example, we might write 
     145{{{ 
     146    instance Monad T where 
     147      return x = ... 
     148      ba >>= bf = ... 
     149      hiding instance Functor 
     150}}} 
     151Note that `Functor` is only an indirect intrinsic superclass of `Monad`, via `Applicative`. 
     152So the above instance would generate an intrinsic instance for `Applicative` but not for `Functor`. 
     153 
     154Jón's proposal had a more subtle opt-out policy, namely that an 
     155intrinsic superclass can be quietly pre-empted by an instance for the 
     156superclass from a prior or the present module. Note that to declare an 
     157instance of the subclass, one must produce an instance of the 
     158superclass by the same module at the latest.  
     159 
     160This quiet exclusion 
     161policy is not enough to handle the case of multiple candidate 
     162intrinsic instances arising from multiple intrinsic superclasses (e.g., 
     163`Traversable` and `Monad` giving competing `Functor` instances), so some 
     164explicit form is required. The question for us, then, is what should 
     165happen if an intrinsic superclass not explicitly hidden were to clash 
     166with an explicit instance from the same or a prior module. We could 
     167 
     168  1. Reject this as a duplicate instance declaration, which indeed it is. 
     169  2. Allow the explicit to supersede the intrinsic default, but issue a warning suggesting to either remove the explicit instance or add an explicit opt-out, or 
     170  3. Allow the explicit to supersede the intrinsic default silently. 
     171 
     172As it stands, we propose option 1 as somehow the principled thing to 
     173do. We acknowledge that it creates an issue with legacy code, 
     174precisely because there are plenty of places where we have written the 
     175full stack of instances, often just doing the obvious default thing: 
     176these should be cleaned up, sooner or later.  
     177 
     178Option 3 avoids that 
     179problem but risks perplexity: if I make use of some cool package which 
     180introduces some {{{Foo :: * -> *}}}, I might notice that {{{Foo}}} is 
     181a monad and add a {{{Monad Foo}}} instance in my own code, expecting 
     182the {{{Applicative Foo}}} instance to be generated in concert; to my 
     183horror, I find my code has subtle bugs because the package introduced 
     184a different, non-monadic, {{{Applicative Foo}}} instance which I'm 
     185accidentally using instead. Option 2 is certainly worth considering as 
     186a pragmatic transitional compromise, although the 'transitional' has a 
     187dangerous tendency to be permanent. 
     188 
     189== Multi-headed instance declarations == 
     190 
     191While we're about it, to allow multi-headed instance declarations for class-disjoint conjunctions, with the same semantics for constraint duplication and method distribution as for the defaults, so 
     192{{{ 
     193    instance S => (C x, C' x) where 
     194      methodOfC  = ... 
     195      methodOfC' = ... 
     196}}} 
     197is short for 
     198{{{ 
     199    instance S => C x where 
     200      methodOfC  = ... 
     201    instance S => C' x where 
     202      methodOfC' = ... 
     203}}} 
     204This proposal fits handily with the [wiki:KindFact kind Fact proposal],  
     205which allows multiple constraints to be abbreviated by 
     206ordinary type synonyms.  So we might write 
     207{{{ 
     208  type Stringy x = (Read x, Show s) 
     209  instance Stringy Int where 
     210    read = ... 
     211    show = ... 
     212}}} 
     213The common factor is that one instance declaration is expanded into 
     214several with the method definitions distributed appropriately among 
     215them. 
     216 
     217== Details == 
    37218 
    38219Each default superclass instance declaration in a `class` declaration must be for 
     
    48229      instance Tweedle dee where ... 
    49230}}} 
    50  
    51   * Let subclass instance declarations spawn intrinsic superclass instances by default -- if we have 
    52 {{{ 
    53     class Bar t[x] => Foo x where 
    54       instance Bar t[x] where ... 
    55  
    56     instance C => Foo s where ... 
    57 }}} 
    58   we automatically acquire a default superclass instance 
    59 {{{ 
    60     instance C => Bar t[s] where ... 
    61 }}} 
    62  
    63   * Let subclass instance declarations provide and override the methods of their intrinsic superclasses with no extra delimitation; so we may write 
    64 {{{ 
    65     instance Monad Blah where 
    66       return x = ... 
    67       ba >>= bf = ... 
    68 }}} 
    69   and acquire the Monad instance, along with fully formed Applicative and Functor instances. By requiring that intrinsic superclasses be class-distinct, we ensure that the distribution of methods to spawned instances is unambiguous. Moreover, local overrides beat the default. If we write 
    70 {{{ 
    71     instance Monad Blah where 
    72       return x = ... 
    73       ba >>= bf = ... 
    74       bs >> bt = ... 
    75 }}} 
    76   we override the default (>>) but keep the (<*>) in the spawned Applicative instance. 
    77  
    78   * To inhibit default-spawning with the syntax 
    79 {{{ 
    80     instance Sub x where 
    81       ... 
    82       hiding instance Super 
    83 }}} 
    84   which acts to prevent the generation of instances for Super and all of Super's intrinsic superclasses in turn. We need this, so that we can write 
    85 {{{ 
    86     instance Monad Blah where 
    87       return x = ... 
    88       ba >>= bf = ... 
    89       hiding instance Functor 
    90  
    91     instance Traversable Blah where 
    92       traverse f bx = ...  -- inducing a default implementation of Functor 
    93 }}} 
    94   or indeed to turn off all the defaults and provide a standalone Functor instance. 
    95  
    96   * While we're about it, to allow multi-headed instance declarations for class-disjoint conjunctions, with the same semantics for constraint duplication and method distribution as for the defaults, so 
    97 {{{ 
    98     instance S => (C x, C' x) where 
    99       methodOfC  = ... 
    100       methodOfC' = ... 
    101 }}} 
    102   is short for 
    103 {{{ 
    104     instance S => C x where 
    105       methodOfC  = ... 
    106     instance S => C' x where 
    107       methodOfC' = ... 
    108 }}} 
    109  
    110 This proposal fits handily with the [wiki:KindFact kind Fact proposal], which allows multiple constraints to be abbreviated by ordinary type synonyms. 
    111  
    112 Default superclass instances are implemented in the [http://personal.cis.strath.ac.uk/~conor/pub/she/superclass.html Strathclyde Haskell Enhancement]. They should enable some tidying of the library, with relatively few tears. Moreover, they should allow us to deepen type class hierarchies as we learn. Retaining backward compatibility in relative silence is the motivation for an opt-in default. 
    113  
    114 == Discussion == 
    115  
    116 Oleg and others note: just because you can make default instances, they are not always the instances you want. A key example is 
    117 {{{ 
    118     instance Monad m => Monad (ReaderT r m) where ... 
    119 }}} 
    120 which would give us by default 
    121 {{{ 
    122     instance Monad m => Applicative (ReaderT r m) where ... 
    123 }}} 
    124 thus preventing us adding the more general 
    125 {{{ 
    126     instance Applicative m => Applicative (ReaderT r m) where ... 
    127 }}} 
    128 The opt-out is crucial, but relatively cheap. 
    129  
    130 Jón's proposal had a more subtle opt-out policy, namely that an intrinsic superclass can be quietly pre-empted by an instance for the superclass from a prior or the present module. Note that to declare an instance of the subclass, one must produce an instance of the superclass by the same module at the latest. This quiet exclusion policy is not enough to handle the case of multiple candidate instances arising from multiple intrinsic superclasses (e.g., Traversable and Monad giving competing Functor instances), so some explicit form is required. The question for us, then, is what should happen if an intrinsic superclass not explicitly hidden were to clash with an explicit instance from the same or a prior module. We could 
    131  
    132   1. reject this as a duplicate instance declaration, which indeed it is, or 
    133   2. allow the explicit to supersede the intrinsic default, but issue a warning suggesting to either remove the explicit instance or add an explicit opt-out, or 
    134   3. allow the explicit to supersede the intrinsic default silently. 
    135  
    136 As it stands, we propose option 1 as somehow the principled thing to do. We acknowledge that it creates an issue with legacy code, precisely because there are plenty of places where we have written the full stack of instances, often just doing the obvious default thing: these should be cleaned up, sooner or later. Option 3 avoids that problem but risks perplexity: if I make use of some cool package which introduces some {{{Foo :: * -> *}}}, I might notice that {{{Foo}}} is a monad and add a {{{Monad Foo}}} instance in my own code, expecting the {{{Applicative Foo}}} instance to be generated in concert; to my horror, I find my code has subtle bugs because the package introduced a different, non-monadic, {{{Applicative Foo}}} instance which I'm accidentally using instead. Option 2 is certainly worth considering as a pragmatic transitional compromise, although the 'transitional' has a dangerous tendency to be permanent. 
     231By requiring that intrinsic superclasses be class-distinct, we ensure that the distribution of methods to spawned instances is unambiguous.  
     232