Proposal: Add `restriction` to Data.Map and Data.IntMap

[Henning Thielemann]

On Tue, 26 Jul 2016, Joachim Breitner wrote:

> Hi,
>
> Am Montag, den 25.07.2016, 14:59 -0400 schrieb David Feuer:
>> Both `restrictKeys` and `withoutKeys` are special cases of
>> `filterWithKey` (although they should be considerably more efficient
>> than implementations using that function).
>
> I’m risking to derailing this discussion, but how viable would it be to
> *not* add a new exported name for this, but recommend (e.g. in the
> docs) to use
>
>    filter (`S.elem` set) map
>
> and then rely on rewrite rules to get the desired performance effect
> (by rewriting this expression to an non-exported restrictKeys)?

The 'filter' expression looks a bit low-level to me. I like to transform 
whole big objects (i.e. sets and maps) and avoid inspecting single 
elements like with S.elem. Another way to not add new functions would be 
to generalize Map.intersection and Map.difference like so

Map.intersection :: (Set set, Ord k) => Map k a -> set k -> Map k a

Map.difference :: (Set set, Ord k) => Map k a -> set k -> Map k a

class Set set where toSet :: set k -> Data.Set.Set k

instance Set Data.Set.Set where toSet = id


Hm, Map cannot be an instance of Set. I would have to add:

newtype FlipMap a k = FlipMap (Map k a)

instance Set (FlipMap a) where toSet (FlipMap m) = Map.keysSet m


Since Map cannot be an instance of Set, we would have to add new functions 
anyway. But then we could simply add intersectionSet and differenceSet and 
discourage intersection and difference, because they can be simply written 
as

Map.intersection x y = Map.intersectionSet x (Map.keysSet y)
Map.difference x y = Map.differenceSet x (Map.keysSet y)

As far as I remember, most of the times when I called Map.intersection or 
Map.difference I actually meant Map.intersectionSet or Map.differenceSet, 
respectively, but had to build an auxiliary Map k ().