[Haskell-cafe] looking for examples of non-fullFunctional Dependencies

[Claus Reinke]

> class C a b c | a -> b, a -> c
> instance C a b b => C [a] [b] [b]
> 
> Suppose we encounter the constraint C [x] y z

interesting example. splitting improvement into two rules 
seems to lose the (b1=b2) constraint that spans both:

[O]
    C [x] y z => y=[b1].
    C [x] y z => z=[b2].

my first thought was that the improvement rules look too general
as the instance only applies if (y=z), so i was tempted to add that
constraint via guards or patterns:

[A]
    C [x] y [b] => y=[b].
    C [x] [b] z => z=[b].

but the FD states that knowing a is sufficient to know both b and c, 
so one could argue that (y=z), just like (y=[b]) and (z=[b]) should 
be a consequence rather than a condition for these improvements:

[B]
    C [x] y z => y=z, y=[b].
    C [x] y z => y=z, z=[b].

it is interesting to observe Hugs (20051031) vs GHCi (6.9.20080217)
on this example and some slight variations (see below). it appears [1] 
that Hugs follows [B] while GHCi follows [A], and that [2,3] GHCi 
generally treats structural and unification constraints differently. i have 
no idea how GHCi comes up with the type (x, [Bool], [Char]) in [2].

btw, Ross started a survey of FD examples/requirements a while ago 
on the Haskell prime list - it would be nice to have any results of his 
and your's online (on the wiki perhaps?), especially as documentation 
regarding different interpretations of the same language extensions 
between Hugs and GHC (overlap resolution & FDs comes to mind
as being fairly similar to this example):

http://www.haskell.org/pipermail/haskell-prime/2006-April/001334.html
http://www.haskell.org/pipermail/haskell-prime/2006-April/001440.html

claus

[1]
    class C a b c | a -> b, a -> c
    instance C a b b => C [a] [b] [b]

    Hugs: 
    :t undefined::C [x] y z => (x,y,z)
    undefined :: C [a] [b] [b] => (a,[b],[b])

    GHCi:
    :t undefined :: C [x] y z => (x,y,z)
    undefined :: C [x] y z => (x,y,z) :: (C [x] [b] [b1]) => (x, [b], [b1])

[2]
    class C a b c | a -> b, a -> c
    instance C a b b => C [a] [b] [b]
    instance C [a] [Bool] [Char]

    Hugs:
    ERROR file:.\C.hs:8 - Instances are not consistent with dependencies
    *** This instance : C [a] [Bool] [Char]
    *** Conflicts with : C [a] [b] [b]
    *** For class : C a b c
    *** Under dependency : a -> b

    GHCi:
    Ok, modules loaded: Main.
    :t undefined :: C [x] y z => (x,y,z)
    undefined :: C [x] y z => (x,y,z) :: (x, [Bool], [Char])

[3]
    class C a b c | a -> b, a -> c
    instance C a b b => C [a] [b] [b]
    instance C [a] Bool Char

    Hugs:
    ERROR file:.\C.hs:8 - Instances are not consistent with dependencies
    *** This instance : C [a] Bool Char
    *** Conflicts with : C [a] [b] [b]
    *** For class : C a b c
    *** Under dependency : a -> b

    GHCi:
    C:\Documents and Settings\cr3\Desktop\C.hs:7:0:
        Functional dependencies conflict between instance declarations:
          instance (C a b b) => C [a] [b] [b]
            -- Defined at C:\Documents and Settings\cr3\Desktop\C.hs:7:0-32
          instance C [a] Bool Char
            -- Defined at C:\Documents and Settings\cr3\Desktop\C.hs:8:0-23
    Failed, modules loaded: none.