Eq[Set[A]] instance is not lawful

The Eq[Set[A]] instance given here is not lawful. It doesn't satisfy the substitution property given here that says

• ∀ a, b, f:
  • a=b ⇒ f(a)=f(b)

The problem is that Sets expose some intrinsic order of elements (observable via methods like iterator, foldLeft, ...). For some implementations of sets, e.g. ListSet and HashSet, it is possible to construct two instances that contain the same elements (and are thus considered equal by the provided Eq), but iterate over them in different order (so it is possible to define a function f that falsifies the substitution property above). As a result, the provided Eq instance is not equality, just equivalence.

I'm not sure what should be done about it, if anything. It would be easy to declare Set from stdlib broken, but how would we handle the issue with an idealized implementation of Set?

Some possibilities are:

1. Have a type class Equiv for equivalence (then Eq extends Equiv) and only provide Equiv[Set], not Eq[Set]. (We might then also need another typeclass for order which represents order on the equivalence classes.)

2. Our idealized Set would not have any API that exposes the intrinsic order. This means, for example, that we lose the Foldable[Set] instance, since folds expose order of elements. We could, however, have for example foldMap with an additional constraint that the monoid be commutative:

   def foldMap[A, B](fa: Set[A])(f: A => B)(implicit B: CommutativeMonoid[B]): B
   

   Then the order would remain unobservable. Is there something like CommutativeFoldable?

Another issue is that this problem is not caught by current tests, since ScalaCheck will never (IMO) generate a function f: Set[A] => Set[A] whose return value depends on the intrinsic order of the argument. As currently written, OrderLaws do not let me pass in my own Arbitrary[A => A].

Read kernel/src/main/scala/cats/kernel/instances/set.scala and kernel-laws/src/main/scala/cats/kernel/laws/OrderLaws.scala first. Investigate the substitution-property concern for Set instances and the limitation around Arbitrary function generation. Done requires a decided approach and corresponding instance or law-test changes, but the issue does not specify which option to adopt.