A single general modification function for Map and IntMap proposal

[Petr Pudlák]

Dear haskellers,

Dne 06/19/2013 02:27 PM, Milan Straka napsal(a):

> Hi all,
>
>> -----Original message-----
>> From: Nikita Volkov <nikita.y.volkov at gmail.com>
>> Sent: 19 Jun 2013, 13:47
>>
>> Hello guys!
>>
>> A deadline of a discusssion on this has been reached. To review the discussion you can visit the archives. Following is a summarization.
>>
>> 1. Following is an implementation proposed by Schachaf Ben-Kiki, which in a combination with an `INLINABLE` pragma produces very impressive results by making even the primitive operations reimplemented in terms of it perform better:
>>
>> insert: ~ +5% increase using alterF
>> delete: ~ +10% increase using alterF
> I probably did not make myself clear enough -- the insert reimplemented
> with alterF runs 5% slower (the running time is increased by 5%) and
> similarly for delete.
>
I was playing with |alterF| to implement

|-- If an element equal to `x` is present, return it. If not, add `x` to the cache.
cacheLookup  :: (Ord  a) => a ->State  (M.Map  a a) a
cacheLookup  x = state (alterF x f)
   where
     f (Just  y) = (y,Just  y)
     fNothing    = (x,Just  x)|

and I realized that in the first case |alterF| needlessly reinserts |y| 
into the map, which introduces unnecessary traversal. So my suggestion 
for discussion is to define |alterF| as

|data  Alter  a =Keep  |Remove  |Replace  a
   deriving  (Read,Show,Eq,Ord)

alterF  :: (Functor  f,Ord  k) => k -> (Maybe  a -> f (Alter  a)) -> (Map  k a -> f (Map  k a))
--                                                  ^^^^^|

where |Alter| gives the action to be performed on the map. It's just as 
|Maybe|, but it adds |Keep| to keep the map intact, if one neither wants 
to replace an element nor to remove it. Another little benefit is that 
it's more descriptive and makes |alterF| slightly more accessible to 
users. Like in my case |cacheLookup| becomes more readable:

|cacheLookup  x = state (alterF x f)
   where
     f (Just  x') = (x',Replace  x')
     fNothing    = (x,Keep)|

It probably won't affect performance for the standard functions defined 
using |alterF|, but in cases like this it could help.

Best regards,
Petr

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20130715/bce9dc05/attachment.htm>