DData revision /equivalence vs equality

[Robert Will]

On Wed, 17 Mar 2004, Ketil Malde wrote:

> I've already said that I think Eq's (==) should be "structural
> equality", which I thought meant that there shouldn't be any
> "deeper" equality.

Taking this serious we would also have to use "deriving Eq" and never any
weaker definition of Equality.

As I explain in
  http://www.stud.tu-ilmenau.de/~robertw/dessy/fun/principles.html
the problem can really only be understood by considering abstract data
types: Equality must be so strong that all exported functions can't
distinguish equal elements.  What you do internally doesn't matter.

As the above document explains (in the last section, by the way), this
view of Abstract Data Types will also make any "biasing" in (e.g.) Set
operations superfluous.  In DData you say "as a concrete implementation
Data.Set may specify biasing", but in the Abstract Collection Standard, we
don't have that excuse any more.

When looking at the standard you will see that Abstraction actually looses
you much stuff, since Abstraction is always about _leaving things out_.
The benefit is that the things (properties) that are left in are much more
general.  Of course an implementation of the Abstract Collections can
strengthen the specifications (e.g. to include biasing), but giving that
anyone relying on this, can't use other implementations any more, it
suddenly becomes much less attractive.

Surely the Gentle Introduction into Haskell with Collections must explain
more of Abstract Data Types and the Laws of Programming.

Robert