Re: Left-bias and non-structural equality.

On Thursday 05 Jan 2006 8:11 pm, Ketil Malde wrote:

Adrian Hey 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