'elem' is O(n) for sets :(

[neongreen]

Sets usually have O(log n) elem, but IntSet and HashSet have O(n) elem because the elem from Foldable is slower than it could be (since it can't use the Hashable or Ord constraints). Facepalm.

We can fix it by doing something like this, as David Feuer proposed at [email protected]:

class Foldable f where
  type ElemConstr t :: * -> Constraint
  type ElemConstr t = Eq

  elem :: ElemConstr t a => a -> t a -> Bool
  default elem :: (ElemConstr t ~ Eq, Eq a) => a -> t a -> Bool

(But for NontrivialContainer instead of Foldable.)

[dfeuer]

@neongreen this is probably meant for the less handsome (but better at Haskell!) David Feuer @treeowl

[neongreen]

@dfeuer yep, I noticed my mistake and edited the message soon after posting it.

[chshersh]

@neongreen Unfortunately, this is not possible for universum because we have OVERLAPPABLE instance. See issue #58. So we either need to implement ToList and Container using functional dependencies or remove OVERLAPPABLE instance and add default signatures. At this moment I don't know which solution is better.