Changes between Version 22 and Version 23 of FunctionalDependencies


Ignore:
Timestamp:
Apr 19, 2006 10:54:19 PM (8 years ago)
Author:
ross@…
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • FunctionalDependencies

    v22 v23  
    8383    (This rule is justified by the above "consistency" condition.) 
    8484 
     85=== Interaction with superclasses === 
     86 
     87The original version makes no changes to the treatment of superclasses, so given the classes (sect. 7) 
     88{{{ 
     89class U a b | a -> b 
     90class U a b => V a b 
     91}}} 
     92the constraint set {{{U a b, V a c}}} is irreducible. 
     93(Adding a dependency to V does not change this.) 
     94In GHC and Hugs, and the system studied in DF-CHR, the improvement rules are applied to the closure of the constraint set under superclasses. 
     95In this example, that is {{{U a b, U a c, V a c}}}, so the functional dependency implies {{{b = c}}}. 
     96(This example can also be rearranged to show nonconfluence for the original system.) 
     97 
    8598=== Properties === 
    8699 
    87 With FlexibleInstances and no OverlappingInstances, this system is coherent and decidable (CHR paper, corr. 1). 
     100 * With FlexibleInstances and no OverlappingInstances, this system is coherent and decidable (CHR paper, corr. 1). 
    88101 
    89 Unfortunately the "coverage" condition rules out instances like the following, from the monad transformer library: 
    90 {{{ 
     102 * Unfortunately the "coverage" condition rules out instances like the following, from the monad transformer library: 
     103   {{{ 
    91104class (Monoid w, Monad m) => MonadWriter w m | m -> w 
    92 instance MonadWriter w m => MonadWriter w (ReaderT r m) 
     105instance (Error e, MonadWriter w m) => MonadWriter w (ErrorT e m) 
    93106}}} 
    94107 
     
    153166    * the functional dependency is ''full'' (involves all the arguments of the class), and the arguments t,,Y,, are distinct type variables determined by the free variables of t,,X,,. 
    154167 
    155 The fullness condition restores confluence, while the variable argument condition restores termination. 
     168The fullness condition restores confluence, while the variable argument condition restores termination (by making instance improvement trivial). 
    156169 
    157170Note that functional dependencies corresponding to [wiki:AssociatedTypes associated type synonyms] are always full.