Default Foldable.elem implementation is `O(n)`

haskell-unordered-containers / unordered-containers

Efficient hashing-based container types

BSD 3-Clause "New" or "Revised" License

221 stars 97 forks source link

Default Foldable.elem implementation is `O(n)` #378

Open yaitskov opened 2 years ago

yaitskov commented 2 years ago

Hi,

I think instance of Foldable.elem for HashSet has default implementation, which has complexity O(n), meanwhile member function is O(log n). IMHO it looks like a bug.

sjakobi commented 2 years ago

Can you clarify how the instance could be improved? member has a Hashable constraint on the element type, and it's not obvious how to use it in the Foldable instance.

sjakobi commented 2 years ago

It would probably be helpful to simply point this out in the haddocks of the Foldable instance.