[Haskell-cafe] looking for examples ofnon-fullFunctional Dependencies

[Claus Reinke]

a little more experimentation leaves me confused. consider

[4]
    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] c => (a,[b],c)

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

both systems improve 'y' to '[b]', but not to '[b] where z=[b]'.

ok, the third parameter is not in range of an FD, so cannot be
instantiated by improvement, and without that, 'y' cannot be
instantiated as far as the FD would suggest. it is slightly
surprising that 'y' get partially instantiated at this stage.

however, if we try to help the process along by instantiating
'z' to '[b]' ourselves, we get:

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

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

i would have expected 'C a c c => (a,[c],[c])' here, as
only instantiation of 'y' is required; so my intuition is still off,
and neither [A] nor [B] seems to capture Hugs' interpretation.
in particular, i don't see how to account for [5], even with
a refined ruleset that accounts for [4].

suggestions?-)
claus

----- Original Message ----- 
From: "Claus Reinke" <claus.reinke at talk21.com>
To: "Martin Sulzmann" <martin.sulzmann at gmail.com>; "Mark P Jones" <mpj at cs.pdx.edu>
Cc: "Tom Schrijvers" <Tom.Schrijvers at cs.kuleuven.be>; "Haskell-cafe Café" <haskell-cafe at haskell.org>
Sent: Thursday, April 17, 2008 2:57 PM
Subject: Re: [Haskell-cafe] looking for examples ofnon-fullFunctional Dependencies


>> 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.
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe