Dear haskellers,
Dne 06/19/2013 02:27 PM, Milan Straka napsal(a):
Hi all,-----Original message----- From: Nikita Volkov <nikita.y.volkov@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 alterFI 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)
f Nothing = (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')
f Nothing = (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