Wrapped sets and maps

[treeowl]

A map from elements of type k to () can be viewed as a set. Indeed, this is how Data.HashSet works. Less usefully, I imagine, a set of elements of type k can also be viewed as a map from elements of type k to (). Should we offer newtype wrappers implementing this correspondence?

[snoyberg]

What would these look like? What would be the advantage for the user?

[treeowl]

I'm not sure what you mean about what they'd look like. For the wrapped map case, the purpose would be to let libraries depending on this one magically turn their map implementations into set implementations. Applications the other way are definitely not as obvious.

[snoyberg]

I mean what are you proposing as the newtype wrapper here? I'm not sure what practically benefit you're going for here. Is the idea to get to elide definitions of data types like HashSet completely, and just rely on a newtype wrapper?

[treeowl]

Sounds about right.

newtype WrappedMap m = WrappedMap {unwrappedMap :: m}
newtype HashSet a = HashSet (WrappedMap (HashMap a ()))
  deriving ({- all the instances -})

[snoyberg]

What's the purpose of the newtype WrappedMap here?

[treeowl]

It's just a target for GND. The relationship between a set of a and a map from a to () has to be implemented somewhere... There's no (inherent) need to implement it separately and by hand for each map type.

[treeowl]

Obviously unordered-containers will not be incurring a mono-traversable dependency, but I feel like this wrapper should exist as a matter of principle.

[snoyberg]

Arguments on principle aren't really too interesting to me, I'm sorry. I'm much more interested in code being useful in some kind of real-world case.