Asymptotics are linear in a few places where they should be logarithmic.

[HuwCampbell]

I was just having a look and noticed this.

It appears that the asymptotics for a few operations are worse that they can and should be.

For example:

insert :: (Ord r, Ord c) => r -> c -> a -> Table r c a -> Table r c a
insert r c a (Table (rm, cm, _)) = fromMaps' r c rm' cm'
  where
    rm' = Map.alter f r rm
    cm' = Map.alter g c cm
    f = Just . maybe (Map.singleton c a) (Map.insert c a)
    g = Just . maybe (Map.singleton r a) (Map.insert r a)

Kind of looks fine, and should be O(ln(c) · ln(r)) or something, but, the size' function called in fromMaps' clearly looks at every key in one of the maps.

So it's actually more like O(r)

I think this could be pretty easily fixed by using insertLookup and alterF.

[HuwCampbell]

Right. This usually just creates a thunk which is probably GC'd.

[zliu41]

@HuwCampbell Thanks for raising this. I think you replied to and closed the wrong issue.

I don't remember why I decided to re-calculate the size, but it seems indeed unnecessary. I'll take a closer look soon.