[Haskell-cafe] Implementing ParseChart with Data.Map

[Krasimir Angelov]

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 <gale at sefer.org> wrote:
> 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
>