Re: A single general modification function for Map and IntMap proposal

Hi all,

-----Original message----- From: Shachaf Ben-Kiki Sent: 30 Apr 2013, 23:49

...

However: I just wrote a quick direct version:

alterF :: (Ord k, Functor f) => k -> (Maybe a -> f (Maybe a)) -> Map k a -> f (Map k a) STRICT_1_OF_2(alterF) alterF k f = go where go Tip = maybe Tip (singleton k) <$> f Nothing go (Bin sx kx x l r) = case compare k kx of LT -> (\l' -> balance kx x l' r) <$> go l GT -> (\r' -> balance kx x l r') <$> go r EQ -> maybe (glue l r) (\x' -> Bin sx kx x' l r) <$> f (Just x)

And benchmarked lookup-via-alterF, insert-via-alterF, etc. -- they come out much slower. However, if I add an INLINE pragma or SPECIALIZE pragmas for common/relevant functors (e.g. Const r, Identity, (r,)), then they come out almost the same speed as the primitive function.

I don't think INLINE is necessarily bad for this function. (I don't like the idea of using SPECIALIZE here because I don't think e.g. Identity should have special privileges over some other newtype with the same Functor instance.) So maybe the direct implementation should be reconsidered. I can do a more thorough benchmark later if people are interested.

The right pragma is probably INLINABLE, which is used a lot throughout the containers. It exposes the unfolding of alterF and if a Ord k or Functor f is known when calling alterF, specialization is created for that Ord or Functor and this specialization is reused in this and dependant modules. Results of my benchmarks are insert: ~ +5% increase using alterF delete: ~ +10% increase using alterF

...

I am also a bit worried whether withItem is the "right" general function. For example Shachaf Ben-Kiki mentions the at :: (Ord k, Functor f) => k -> (Maybe i -> f (Maybe i)) -> Map k i -> f (Map k i) from the lens package in other mail, but maybe there are others.

I think that alterF almost certainly *a* right function -- it's just a monadic/functorial version of `alter`, which is the most general "simple" updating function. Possibly there should be others too, but this one is useful and general. Although it needs a better name. :-)

I feel convinced, alterF seems to offer additional functionality by being quite general, and it is reasonably efficient because a specialization is created for calls with known functor instance. I like it :) Cheers, Milan