Changes between Version 14 and Version 15 of FunctionalDependencies
- Timestamp:
- 03/30/06 08:59:05 (7 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
FunctionalDependencies
v14 v15 4 4 == Brief Explanation == 5 5 6 Functional dependencies (borrowed from relational databases) are a partial solution to the ambiguities that plague [wiki:MultiParamTypeClasses multi-parameter type classes], e.g.6 Functional dependencies (borrowed from relational databases) restrict the instances of a [wiki:MultiParamTypeClasses multi-parameter type class], e.g. 7 7 {{{ 8 8 class ... => C a b c | a -> b 9 9 }}} 10 10 says that any two instances of `C` that agree in the first parameter must also agree in the second. 11 They 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). 11 14 12 15 == References == … … 15 18 * [http://cvs.haskell.org/Hugs/pages/hugsman/exts.html#sect7.1.1 Multiple parameter classes] in the Hugs 98 User Manual 16 19 * [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. 18 21 == Tickets == 19 22 [[TicketQuery(description~=FunctionalDependencies)]] … … 32 35 * AssociatedTypes seem to be more promising. 33 36 34 == Variations == 37 == Restrictions on instances == 38 39 There are several versions. 35 40 36 41 === Original version === 37 42 43 These are the restrictions from the original paper, named according to the FD-CHR paper. 38 44 Suppose a class ''C'' has a functional dependency ''X'' `->` ''Y''. 39 45 The original paper imposed two restrictions on instances of the class ''C'' (sect. 6.1): 40 46 41 1. For any instance 47 1. '''Coverage.''' 48 For any instance 42 49 {{{ 43 50 instance ... => C t 44 51 }}} 45 52 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 47 55 {{{ 48 56 instance ... => C s … … 57 65 === GHC and Hugs === 58 66 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,,.67 GHC 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,,. 60 68 They thus accept instances like the following from the monad transformer library, which is invalid according to the original rules: 61 69 {{{ … … 95 103 === New version === 96 104 97 The following complex relaxation of the first ruleis safe (CHR paper, sect. 6), and allows the instances in the monad transformer library:105 The following complex relaxation of the "coverage" condition is safe (CHR paper, sect. 6), and allows the instances in the monad transformer library: 98 106 99 107 1. For any instance … … 106 114 107 115 Note 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. 120 Note that since context reduction is deferred (see FlexibleContexts), this refers not to what instances are available, but what instances are possible. 121 122 A 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 {{{ 128 instance ... => 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 133 An alternative view of the confluence problem discussed under ''GHC and Hugs'' is that the improvement rules should be modified.
