Changes between Version 16 and Version 17 of FunctionalDependencies


Ignore:
Timestamp:
Apr 7, 2006 9:45:59 AM (9 years ago)
Author:
ross@…
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • FunctionalDependencies

    v16 v17  
    9999
    100100They thus accept instances like the above `MonadWriter` example.
    101 Unfortunately, this relaxation breaks the guarantees of termination and coherence:
     101Unfortunately, this relaxation breaks the guarantees of termination and coherence.
    102102
    103  '''Loss of termination'''::
    104    The following instances (CHR paper, ex. 6) seem reasonable:
    105    {{{
     103=== Loss of termination ===
     104
     105The following instances (CHR paper, ex. 6) seem reasonable:
     106{{{
    106107class Mul a b c | a b -> c where
    107108        (.*.) :: a -> b -> c
     
    111112instance Mul a b c => Mul a [b] [c] where x .*. v = map (x.*.) v
    112113}}}
    113    and yet instance inference fails to terminate for the following (erroneous) definition:
    114    {{{
     114and yet instance inference fails to terminate for the following (erroneous) definition:
     115{{{
    115116f = \ b x y -> if b then x .*. [y] else y
    116117}}}
    117118
    118  '''Loss of confluence'''::
    119    The following instances (adapted from CHR paper, ex. 18) are sensitive to the order in which rules are applied:
    120    {{{
     119=== Loss of confluence ===
     120
     121The following instances (adapted from CHR paper, ex. 18) are sensitive to the order in which rules are applied:
     122{{{
    121123class B a b | a -> b
    122124class C a b c | a -> b where f :: a -> b -> c -> Bool
     
    124126instance B a b => C [a] [b] Bool
    125127}}}
    126    Given the constraint ``C [a] [b] Bool, C [a] [c] d``,
    127     * if we apply the dependency first, and then reduce using the instances, we obtain ``b = c, B a b, C [a] [b] d``.
    128     * if we first reduce using the instances, we obtain ``B a b, C [a] [c] d``.
    129   (GHC and Hugs yield the former, because they defer context reduction: see FlexibleContexts).
     128Given the constraint ``C [a] [b] Bool, C [a] [c] d``,
     129 * if we apply the dependency first, and then reduce using the instances, we obtain ``b = c, B a b, C [a] [b] d``.
     130 * if we first reduce using the instances, we obtain ``B a b, C [a] [c] d``.
     131(GHC and Hugs yield the former, because they defer context reduction: see FlexibleContexts).
    130132
    131 == Fixes ==
     133== Proposed Fixes ==
    132134
    133135The following are alternatives.