Left-bias and non-structural equality.

[Ketil Malde]

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

with

  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?)

-k
-- 
If I haven't seen further, it is by standing in the footprints of giants