Left-bias and non-structural equality.
ketil.malde at bccs.uib.no
Thu Jan 5 15:11:30 EST 2006
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 - whether a Set use
structural equality or just some possibly ill-defined equivalence,
that should be a property of the Set *type*, not the insertion
operator. And what if you change the equivalence while inserting?
I guess it is impractical to use a phantom type to provide the
ordering function? :-)
How about something like:
data SetEql a b = -- abstract, set of as, requires Ord b
empty :: Ord b => (a->b) -> SetEql a b
(and similar for other set construction functions)?
I'm still not convinced this solves any problem not solved better by a
Map, though. And it still doesn't embed the comparison function in
the type, so I guess you will have to define left or right bias for
union, etc. (Or perhaps run both (a->b) functions on all keys to check
for equality, with the alternative being a run time error?)
If I haven't seen further, it is by standing in the footprints of giants
More information about the Libraries