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

[Matthew Brecknell]

Tony Morris:
> ...it seems to be a special case of Set? Does Data.Map add anything more
> useful than Map' below?
> 
> [... Map-like structure based on Data.Set ...]

Note that you could also attempt to go in the other direction (but see
the comments about strictness below):

> type Set' a = Data.Map.Map a ()

Certainly, Data.Map and Data.Set are very similar in their
implementations, but rather than seeing one as a specialisation of the
other, it's more helpful to see them both as specialisations of a basic
underlying binary tree structure. The specialisation occurs both in the
interfaces (for the convenience of the user), and in the implementations
(for efficiency).

For example, at the interface, consider how you would perform the
equivalent of Data.Map.lookup using your Map' type. You'll need a clever
combination of intersection, singleton and toList, with appropriate
lifting into an arbitrary monad.

If you look at the implementations, you'll note that, among other
things, the Data.Map.Map type is strict in the key, but not in the
associated value. Data.Set is not strict in the value, so your Map' type
will not be strict in its key. As well as improving the performance of
Data.Map, strictness in the key also helps avoid problems with memory
leaks.