Left-bias and non-structural equality.

Adrian Hey ahey at iee.org
Mon Jan 2 18:43:20 EST 2006

On Monday 02 Jan 2006 7:29 pm, Jean-Philippe Bernardy wrote:
> Non structural equality seemed not to have many proponents the last
> time I discussed it. (See
> http://www.haskell.org//pipermail/libraries/2004-March/001833.html and
> following messages)
> Yet, since haskell doesn't rule it out, I guess we have to provide a
> consitent behaviour, if only to minimize the user's suprise.

Well I think on the whole I agree with the views expressed by Cale (and
Robert Will on the above mentioned thread). Insisting on structural
equality seems too restrictive. If we insist on this then presumably
Sets can't (sensibly) be instances of Eq or Ord, so we couldn't have
Sets of Sets. (Hmm.. Sets of Sets.. seems like tries would be the way
to go here. I guess we do probably do need ListSet and ListMap..)

Anyway, the problem is we have one hole and two "equal" things, only
one of which can fit in the hole. Is there any reason why we can't
simply adopt the position that which one is chosen is unspecified and
the choice is entirely at the implementors discretion?

If this results in ambiguous programs then this is because the
corresponding instance of Ord (and presumably Eq too) is just broken,
and this is what needs to be fixed (or removed). If users can't define
sane instances of Eq and Ord for their types then they'll just have to
use the lower level APIs (eg. Data.Tree.AVL) and pass whatever is the
appropriate combining comparison as an explicit argument.

Adrian Hey

More information about the Libraries mailing list