On 30/12/05, Adrian Hey
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