[Haskell-cafe] (names for) invariants for Eq and Ord?

Levent Erkok erkokl at gmail.com
Tue May 29 20:00:42 UTC 2018


Johannes:

Heartily agreed. In fact, oft-used modules like Data.Map also need to be
very clear regarding their requirements for Eq/Ord. It's well known in the
folklore that the law:

          M.lookup k (M.insert k v M.empty) == Just v

fails for maps when the key can be floating point:

    Prelude> import qualified Data.Map as M
    Prelude M> let k = 0/0 in let v = 0 in M.lookup k (M.insert k v
M.empty) == Just v
    False

Perhaps not a big deal as no-one should use floating-point values as a key
to a map, but there's nothing stopping from anyone from doing so. Perhaps
more worryingly, the Haskell report is largely silent about  Eq/Ord
instances that come out-of-the-box for such gotchas as you yourself
observed.

-Levent.


On Tue, May 29, 2018 at 12:26 PM, Simon Jakobi via Haskell-Cafe <
haskell-cafe at haskell.org> wrote:

> Hi Johannes,
>
> https://ghc.haskell.org/trac/ghc/ticket/15078 might be interesting to you.
>
> Cheers,
> Simon
>
> 2018-05-28 16:47 GMT+02:00 Johannes Waldmann <johannes.waldmann at htwk-
> leipzig.de>:
>
>> Dear Cafe,
>>
>> I am somewhat surprised that the Haskell Standard (*)
>> https://www.haskell.org/onlinereport/haskell2010/haskellch6.
>> html#x13-1270006.3
>> does not contain any
>> notation for (intended) properties of Eq and Ord instances,
>> and their relation. For Java (standard library),
>> the API spec uses wording like "consistent with equals"
>> https://docs.oracle.com/javase/10/docs/api/java/lang/Comparable.html
>>
>> I am well aware that semantics (transitivity, etc.)
>> cannot be enforced statically, in either language.
>> But both standards still speak of "total order".
>> Do we (Haskell) need something similar to "consistent with equals"?
>>
>> It depends. E.g., looking at a (random) source in containers
>> (Data.Map.Internal), it seems that it will always use the result of
>> compare, never of (==), on keys. That's not obvious from the docs.
>> I just checked -- I can make a type where (==) = undefined,
>> but write a proper Ord instance, and use it as key type.
>>
>> I am asking this because I will be teaching type classes,
>> with Eq and Ord as examples. I detected the funny situation
>> that the Java specification looks "more mathematical"
>> than the corresponding Haskell one. What will the students think ...
>>
>> - J.W.
>>
>> (*) The Haskell standard is what you find when you scroll
>> down, down, down to the very bottom of
>> https://www.haskell.org/documentation . So, probably not that
>> important...
>> _______________________________________________
>> Haskell-Cafe mailing list
>> To (un)subscribe, modify options or view archives go to:
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>> Only members subscribed via the mailman list are allowed to post.
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20180529/7a5e44f1/attachment.html>


More information about the Haskell-Cafe mailing list