Open sjakobi opened 2 years ago
HashMap.size and HashSet.size have complexity O(n). Nevertheless there is a lot of code like
HashMap.size
HashSet.size
HashMap.size m > CONSTANT
…which could be O(min(n,CONSTANT)) if the HashMap traversal would stop once at most CONSTANT elements have been counted.
HashMap
CONSTANT
For this purpose it would be nice to have a function
compareSize :: HashMap -> Int -> Ordering
and rules that rewrite size comparisons against constants to applications of compareSize.
compareSize
Similar functionality already exists in bytestring: https://github.com/haskell/bytestring/blob/707e50bac1f1ef7c1729a9246e05f95a4909fd27/Data/ByteString/Lazy.hs#L552-L592
bytestring
(Analogous feature request for IntMap: https://github.com/haskell/containers/issues/826)
IntMap
HashMap.sizeandHashSet.sizehave complexity O(n). Nevertheless there is a lot of code like…which could be O(min(n,CONSTANT)) if the
HashMaptraversal would stop once at mostCONSTANTelements have been counted.For this purpose it would be nice to have a function
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(Analogous feature request for
IntMap: https://github.com/haskell/containers/issues/826)