Changes between Version 14 and Version 15 of FunctionalDependencies


Ignore:
Timestamp:
Mar 30, 2006 4:59:05 PM (9 years ago)
Author:
ross@…
Comment:

details

Legend:

Unmodified
Added
Removed
Modified
  • FunctionalDependencies

    v14 v15  
    44== Brief Explanation == 
    55 
    6 Functional dependencies (borrowed from relational databases) are a partial solution to the ambiguities that plague [wiki:MultiParamTypeClasses multi-parameter type classes], e.g. 
     6Functional dependencies (borrowed from relational databases) restrict the instances of a [wiki:MultiParamTypeClasses multi-parameter type class], e.g. 
    77{{{ 
    88class ... => C a b c | a -> b 
    99}}} 
    1010says that any two instances of `C` that agree in the first parameter must also agree in the second. 
     11They are a partial solution to the following problems with MPTCs: 
     12 * ambiguity 
     13 * imprecise types and late error reporting, arising from deferred context reduction (see FlexibleContexts). 
    1114 
    1215== References == 
     
    1518 * [http://cvs.haskell.org/Hugs/pages/hugsman/exts.html#sect7.1.1 Multiple parameter classes] in the Hugs 98 User Manual 
    1619 * [http://www.haskell.org//pipermail/haskell-prime/2006-February/000289.html Problems] with functional dependencies (email) by SPJ + paper. [http://www.haskell.org/pipermail/haskell/2000-December/006324.html See also]. 
    17  
     20 * AssociatedTypes are an alternative solution. 
    1821== Tickets == 
    1922[[TicketQuery(description~=FunctionalDependencies)]] 
     
    3235 * AssociatedTypes seem to be more promising. 
    3336 
    34 == Variations == 
     37== Restrictions on instances == 
     38 
     39There are several versions. 
    3540 
    3641=== Original version === 
    3742 
     43These are the restrictions from the original paper, named according to the FD-CHR paper. 
    3844Suppose a class ''C'' has a functional dependency ''X'' `->` ''Y''. 
    3945The original paper imposed two restrictions on instances of the class ''C'' (sect. 6.1): 
    4046 
    41  1. For any instance 
     47 1. '''Coverage.''' 
     48    For any instance 
    4249    {{{ 
    4350instance ... => C t 
    4451}}} 
    4552    any variable occurring free in t,,Y,, must also occur free in t,,X,,. 
    46  2. If there is a second instance 
     53 2. '''Consistency.''' 
     54    If there is a second instance 
    4755    {{{ 
    4856instance ... => C s 
     
    5765=== GHC and Hugs === 
    5866 
    59 GHC and Hugs implement a relaxed version of the first restriction above: they require only that any variable occurring free in t,,Y,, be dependent (using dependencies of classes in the context) on variables that occur free in t,,X,,. 
     67GHC and Hugs implement a relaxed version of the above "coverage" condition: they require only that any variable occurring free in t,,Y,, be dependent (using dependencies of classes in the context) on variables that occur free in t,,X,,. 
    6068They thus accept instances like the following from the monad transformer library, which is invalid according to the original rules: 
    6169{{{ 
     
    95103=== New version === 
    96104 
    97 The following complex relaxation of the first rule is safe (CHR paper, sect. 6), and allows the instances in the monad transformer library: 
     105The following complex relaxation of the "coverage" condition is safe (CHR paper, sect. 6), and allows the instances in the monad transformer library: 
    98106 
    99107 1. For any instance 
     
    106114 
    107115Note that functional dependencies corresponding to [wiki:AssociatedTypes associated type synonyms] are always full. 
     116 
     117== Improvement of inferred types == 
     118 
     119"Improvement", as used by Mark Jones, means using information about what instances could match a predicate to instantiate its type variables, or to fail. 
     120Note that since context reduction is deferred (see FlexibleContexts), this refers not to what instances are available, but what instances are possible. 
     121 
     122A functional dependency X -> Y allows two improvement rules: 
     123 1. '''FD improvement.''' 
     124    If a context contains predicates C t and C s such that t,,X,, = s,,X,,, infer t,,Y,, = s,,Y,,. 
     125 2. '''Instance improvement.''' 
     126    Given a predicate C s and an instance declaration 
     127    {{{ 
     128instance ... => C t 
     129}}} 
     130    such that s,,X,, = S t,,X,, for some substitution S, infer s,,Y,, = S t,,Y,,. 
     131    (This rule is justified by the above "consistency" condition.) 
     132 
     133An alternative view of the confluence problem discussed under ''GHC and Hugs'' is that the improvement rules should be modified.