[Haskell-cafe] Implementing ParseChart with Data.Map

[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