I actually made my own copy of Data.Map and added an extra:
alterLookúp :: Ord k => (Maybe a -> (b,Maybe a)) -> k -> Map k a -> (b,Map k a)
function. I also changed my data type to:
type ParseChart k v = Map k (Map v ())
so I don't have to copy the Data.Set module also. Unfortunately this
doesn't give much better performance - 5734 msec instead of 5828 msec.
Fortunately I found that there is a way to avoid to use Map at all in
one common case. This gave me time about 5024 msec.
Regards,
Krasimir
On 6/3/08, Yitzchak Gale
Krasimir Angelov wrote:
but notice that the set is still traversed twice.
Neil Mitchell wrote:
I don't see any way of reducing that
Yeah, it looks like the Data.Set (and Data.IntSet) library is missing the functions
insertMember :: Ord a => a -> Set a -> (Bool, Set a) deleteMember :: Ord a => a -> Set a -> (Bool, Set a)
analagous to splitMember. It should be easy to write those functions. If you do that for yourself, consider making a patch of them and submitting the patch as a library proposal.
But anyway, a set lookup is very cheap, even for a set that is quite large. You may want to try just doing the extra lookup, it might be good enough for you. At least you eliminated the Map lookup.
Regards, Yitz