[Haskell-cafe] strange stack overflow with Data.Map

Cale Gibbard cgibbard at gmail.com
Fri Dec 30 20:04:54 EST 2005


On 30/12/05, Adrian Hey <ahey at iee.org> wrote:
> As for the structural equality issue, I have always assumed that if
> (==) returned True or `compare` returned EQ this implied structural
> equality. But I'm not sure that's documented anywhere, and as it
> happens it's not true for the Eq and Ord instances defined AVL trees.
> This is something that had been worrying me (maybe I should remove
> these instances).

This isn't even quite true for all the prelude types. In particular
-0.0 and 0.0 are distinct Float values structurally, but will compare
equal, though one might make exceptions here due to floating point
values being thought of as some approximation of real numbers where
the laws are satisfied.

However, I think it's safe to only require that (==) be a suitable
equivalence relation on the values of a type. This is especially true
when the representation is hidden, so that no stronger tests for
comparison could be constructed by the library user. It seems like it
would usually be handy to have instances of Eq  not differentiate
between values which "represent the same thing" in different ways.

Earlyish versions of Miranda had 'laws' which would be applied
automatically to normalise values of a particular type, so as to get a
type which wasn't freely generated by its constructors. They were
quite strong, and one could easily enforce a variety of invariants,
like keeping lists sorted and trees balanced. At some point they were
removed, but I haven't seen a really good explanation as to why this
happened. I suppose that there are other ways to achieve those
effects, but it's neat to be able to use pattern matching on what
would otherwise have to be an abstract data type.

 - Cale


More information about the Libraries mailing list