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.