association set conversions for Data.Map types

[matthewleon]

Two things here:

toSet: It seems to me that an association set better embodies the static guarantees that we get when converting a map to an ascending association list with toAscList.

fromSet: It would also seem (naively) to me that this allows us to rely on the type system to produce the guarantee we want in fromAscList.

My apologies if this has been addressed elsewhere. I looked and couldn't find anything.

[treeowl]

Please explain exactly what these functions do, give type signatures, and explain how they do what they do better than what we have already.

…

On Feb 6, 2017 8:15 AM, "Matthew Leon" ***@***.***> wrote: Two things here: toSet: It seems to me that an association *set* better embodies the static guarantees that we get when converting a map to an ascending association list with toAscList. fromSet: It would also seem (naively) to me that this allows us to rely on the type system to produce the guarantee we want in fromAscList. My apologies if this has been addressed elsewhere. I looked and couldn't find anything. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#391>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABzi_QNyuFg7_I5-pPsUl8pdoK3J-5k6ks5rZxzigaJpZM4L4K5N> .

[matthewleon]

toSet :: Map k a -> Set (k, a).
Convert the map to a set of key/value pairs.
The existing toAscList essentially does this, but without the static guarantee provided by the Set type that a key will not be repeated in the list. Admittedly, one could simply take the output of toAscList and build a Set with it, but my intuition (very possibly incorrect) is that there might be some optimization to exploit by writing this function intelligently.

fromSet :: Set (k, a) -> Map k a.
Build a map from a set of key/value pairs.
Similarly, we could do this by using fromAscList, but as its documentation states in italics, the precondition (input list is ascending) is not checked.

[treeowl]

Your toSet certainly could be written well, yes. toSet M.Tip = S.Tip toSet (M.Bin s k v l r) = S.Bin s (k, v) (toSet l) (toSet r) There's also an unsafe variant allowing the user to map a strictly increasing function at the same time. Do you have an application in mind? I think you should propose this on the libraries list--it does seem reasonable. Your fromSet is a bit of a different story. Since you'll need to merge elements with the same key, I don't think you're likely to do much better than converting to a list and back again. You're right that adding the function makes it clear that it's an invariant-safe operation, but I don't know if it's worth it. On Feb 6, 2017 11:08 AM, "Matthew Leon" <[email protected]> wrote: toSet :: Map k a -> Set (k, a). Convert the map to a set of key/value pairs. The existing toAscList essentially does this, but without the static guarantee provided by the Set type that key k will not be repeated in the list. Admittedly, one could simply take the output of toAscList and build a Set with it, but my intuition (very possibly incorrect) is that there might be some optimization to exploit by writing this function intelligently. fromSet :: Set (k, a) -> Map k a. Build a map from a set of key/value pairs. Similarly, we could do this by using fromAscList, but as its documentation states in italics, *the precondition (input list is ascending) is not checked.* — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#391 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABzi_VuIRJPDfJp7gdsOtTANDphcRYwEks5rZ0VdgaJpZM4L4K5N> .

[meooow25]

This was addressed by #817