English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
Re: polymorphic equality and overloading
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2000-07-07 (14:29)
From: John R Harrison <johnh@i...>
Subject: Re: polymorphic equality and overloading

Eijiro Sumii writes:

| But as you know (and as I wrote in my previous messages), the
| polymorphic equality in Caml is not at all the "equality in
| mathematics" for many (or most?) datatypes.

Probably "most" is an exaggeration. But there are quite a few examples.
One I haven't seen mentioned in this thread is the type of floating point
numbers. The equality relation defined in the main standard for binary
floating point arithmetic (IEEE 754) is not reflexive. Specifically x = x
is false if x is a NaN ("not a number"). So again, this is really an
instance of overloading in CAML:

  #let x = 0.0 /. 0.0;;
  x : float = nan.0
  #x = x;;
  - : bool = false
  #x == x;;
  - : bool = true

Nevertheless, I find the CAML polymorphic equality and orderings pretty
useful and superficially simple, even if they sometimes have a touch of
arbitrariness about them.

Is it possible using just equality, not orderings, to write a set-compare
operation on polymorphic lists using fewer than 0(n^2) operations?
Trivially, using orderings, one can just sort both lists in O(n log n)
operations then run along them in order. Is there something comparably
efficient just using equality?