IntMap.size and IntSet.size have complexity O(n). Nevertheless there is a lot of code like

IntMap.size m > CONSTANT

…which could be O(min(n,CONSTANT)) if the IntMap traversal would stop once at most CONSTANT elements have been counted.

For this purpose it would be nice to have a function

compareSize :: IntMap -> Int -> Ordering

and rules that rewrite size comparisons against constants to applications of compareSize.

Similar functionality already exists in bytestring: https://github.com/haskell/bytestring/blob/707e50bac1f1ef7c1729a9246e05f95a4909fd27/Data/ByteString/Lazy.hs#L552-L592