Left-bias and non-structural equality.

[Adrian Hey]

On Thursday 05 Jan 2006 8:11 pm, Ketil Malde wrote:
> Adrian Hey <ahey at iee.org> writes:
> > insertUsing :: (a -> a -> COrdering a) -> a -> Set a -> Set a
> >
> > But as others have pointed out, this is probably the wrong thing
> > to do as Sets should provide some kind of semantic guarantees
>
> My gut reaction to this is that it's ugly

Well I thought it was clear from the post you're replying to (and
even from the text you've quoted) that this was just a straw man
proposal, not a real proposal.

As for doing this with AVL trees rather than "Sets", I have no
intention of changing this because having "combining comparisons"
as explicit arguments is really convenient in real programs. It
wraps up user control of both strictness and biasing into a
single function argument, eliminates the need for separate
"With" versions of functions and allows easy mixed type
operations (such as intersection).

It's true that this lacks safety, because all these functions
assume that tree elements are sorted according to the same
criterion (informally speaking), and this is not enforced by
the type system.

Where there's a real problem is that assuming the underlying
data structure is an AVL tree and providing O(1) conversions
between Sets and AVL trees is not going to be an option for a
general Set type constructor class. What's needed is some kind of
abstracted type safe wrapper to deal with non-instances of Ord.
Preferably one that provides the same control as Data.Tree.AVL
does.

So maybe something like what you suggested would work. I dunno,
but if anybody wants to provide a suitably abstracted wrapper
around all or part of the current Data.Tree.AVL API, that would
be very useful.

Regards
--
Adrian Hey