[Haskell-cafe] Why does Data.Map exist when...

[Dan Doel]

On Monday 16 July 2007, Tony Morris wrote:
> ...it seems to be a special case of Set? Does Data.Map add anything more
> useful than Map' below?

Why does Data.Set exist when it's just a special case of Data.Map?

    import Data.Map

    type Set a = Map a ()

And, in fact, I think going this way doesn't lose any functionality, whereas 
implementing Map in terms of Set loses you stuff like unionWith (at least, 
barring your taking time to re-implement it specifically), which may or may 
not be a big deal to you (I think I've used it before, though).

The answer is, I suppose, that the interface is subtly different (and the 
semantics may be, too; are you sure that your insert using Set behaves the 
same way as insert on Map?), and when you're doing Set stuff, you don't want 
to be bugged by the fact that you're using a Map of ()s, and vice versa 
(although you could probably finesse things to the point where it wouldn't be 
noticeable).

The real question is why there's Data.Map and Data.IntMap, when the compiler 
should really be able to detect that we're using a certain key type, and 
automatically use the optimized Map for that key type without our having to 
do anything. And the answer to that is that maybe, in the future, that will 
be the case, once associated types/data families are widely available. :)

Cheers,
Dan Doel