[Hugs-bugs] FD handling unaware of overlap resolution?

Claus Reinke claus.reinke at talk21.com
Mon Feb 20 10:06:59 EST 2006


hmm, the issue seems to be slightly more subtle than I presented it.

the overlap [Select a b (c,d),Select a b ((a,b),c)] should be resolved
in favour of the more specific path; however, there is the issue of 
declaring a return type that does not match the field type of the first 
label occurrence [Select a c ((a,b),((a,c),()))]:

    r = ((A,True),((A,'x'),()))
    r #? A :: Char

this means that the first instance declaration is no longer more 
specific, but simply doesn't match (as we can verify by removing
the FD). now, there seem to be two possible interpretations of 
the functional dependency (like those infamous logic loops..):

1. if we assert that the FD holds, it does.

    the first instance that determines all variable in the domain
    of the FD is chosen, fixing the variables in the range of the FD,
    in line with best-match overlap resolution.

    this means the code works as expected (by me at least;-),
    and we get a type error because Char (the declared type) 
    doesn't match Bool (the type fixed by the FD).

    this seems to be what ghc implements.

2. if we assume that the FD doesn't hold, it doesn't.

    even though we have declared that variables in the range of 
    the FD should be determined by those in the domain, we can
    ignore this declaration, treat the range variables as inputs, and
    look for another matching combination of instances.

    this means we have to reject the code because it could be
    interpreted as not ensuring the FD (returning either Bool or
    Char in the example, depending on context).

    this might be what hugs implements.

personally, I can't see any advantage in 2, so my favourite would
have to be 1, as implemented in ghc..

using the analogy with pattern-matching again (a simpler area
with similar issues), if we write 

    select ((label',val):r) label | label==label' = val
    select (l               :r) label                       = select r label

    select [('A',1),('A',2)] == 2

then option 1 is what Haskell implements, and the expression
evaluates to False (because 1/=2). whereas option 2 would 
reject the definition as not a function (because if we ignore the
"wrong" value 1 given by the first-match rule, we find that the
second clause would permit us to extract a 2 from the list).

so, I can see an interpretation (2) by which Hugs' behaviour 
could be said to be correct, but I still think that the alternative
interpretation (1) is a lot more useful. not to mention that Hugs
and GHC should agree..

so, either it is a bug, or it is a misfeature, or..?

cheers,
claus

>    -- | field selection
>    infixl #?
> 
>    class Select label val rec | label rec -> val where
>      (#?) :: rec -> label -> val
> 
>    instance Select label val ((label,val),r) where
>      ((_,val),_) #? label = val
> 
>    instance Select label val r => Select label val (l,r) where
>      (_,r)       #? label = r #? label
> 
> hugs -98 +o complains [Neil: would it be possible to add a WinHugs option
> for switching to copy&past *without formatting*?]:
> 
>    ERROR file:.\Dilemma.hs:33 - Instances are not consistent with dependencies
>    *** This instance : Select a b (c,d)
>    *** Conflicts with : Select a b ((a,b),c)
>    *** For class : Select a b c
>    *** Under dependency : a c -> b
> 
> but according to the resolution of overlapping instances, the offending 
> instances shouldn't even exist, right? in other words, after resolution, 
> there are no overlaps left, hence no two ways to select an instance.
> whenever the two instance definitions overlap, the first one is chosen,
> so the dependency is maintained.
> 
> or am I missing something? [ghci accepts these definitions]
> 
> Claus
> 
> _______________________________________________
> Hugs-Bugs mailing list
> Hugs-Bugs at haskell.org
> http://www.haskell.org/mailman/listinfo/hugs-bugs


More information about the Hugs-Bugs mailing list