[Haskell-cafe] Re: (flawed?) benchmark : sort

Denis Bueno dbueno at gmail.com
Mon Mar 10 12:54:30 EDT 2008


On Mon, Mar 10, 2008 at 12:19 PM, Adrian Hey <ahey at iee.org> wrote:
> Denis Bueno wrote:
>  > On Mon, Mar 10, 2008 at 10:10 AM, Adrian Hey <ahey at iee.org> wrote:
>  >>  >>  The Eq instance you've given violates the law that (x == y) = True
>  >>  >>  implies x = y. Of course the Haskell standard doesn't specify this law,
>  >>  >>  but it should.
>  >
>  > Unless I'm missing something obvious, the example Neil gave earlier
>  > should make it clear how impossible this requirement is:
>  >
>  >   What if I had made the definition of Foo:
>  >
>  >   data Foo = Foo Int (Int -> Int)
>  >
>  > There is no way in general to decide the observational equivalence of
>  > two values of this data type (by reduction to the halting problem).
>  > Therefore it is impossible to write any function implementing such an
>  > equality test.
>
>  Did you read my original response to this example?
>
>  http://www.haskell.org/pipermail/haskell-cafe/2008-March/040356.html

Yes.  You would argue that one should not export the data constructor
Foo.  That is a decision that requires more details about the code
providing Foo, although it certainly seems a reasonable approach in
many cases.  Supposing I wanted to export Foo, though, the condition
you'd like to put on == breaks down.  Even if I don't export Foo, how
do I ensure that any standard library functions called from the Foo
library don't depend on the condition you'd like to put on ==?  Do I
have to examine them individually?  Wouldn't it be easier to reason
about code if we constrain the semantics of == as *little* as possible
(as an equivalence relation)?

-- 
 Denis


More information about the Haskell-Cafe mailing list