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

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

Hi all,

...

-----Original message----- From: Nikita Volkov 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