[Haskell-cafe] looking for examples of
non-fullFunctional Dependencies
Claus Reinke
claus.reinke at talk21.com
Thu Apr 17 09:57:57 EDT 2008
> 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.
More information about the Haskell-Cafe
mailing list