UnorderedTraverse should extend Functor #4802

I had assumed that UnorderedTraverse extended Functor since it can clearly be implemented:

  override def map[A, B](fa: F[A])(f: A => B): F[B] =
    unorderedTraverse[Id, A, B](fa)(f)

But I was surprised to learn (or recall) it didn't. I looked up the original PR to see if I could see why. I found: #1981 (cc @LukaJCB ).

It seems it was briefly considered in that PR, but then discarded because Set[A] could not implement UnorderedTraverse then. I now have a different take: it's code smell that the laws on UnorderedTraverse as so weak that we could implement map in the above, but it is totally unspecified what the result might be. I suppose returning an empty F[B] on every unorderedTraverse and nothing else might actually be lawful.

For instance, we have this code in UnorderedTraverseLaws:

  def unorderedTraverseIdentity[A, B](fa: F[A])(f: A => B)(implicit ev: Functor[F]): IsEq[F[B]] =
    F.unorderedTraverse[Id, A, B](fa)(f) <-> (ev.map(fa)(f))

But that code is never called in the repo. Moreover, there are only two implementations of UnorderedTraverse in the repo: Set and [V] =>> Map[K, V]. Cats collections implements UnorderedTraverse for the parametric HashMap[K, V] there, which was where I was using this.

I think we should have a stern talk with whoever approved these changes (😅 )
#1981 (review)

We are kind of in a jam here. In my opinion, the correct fix is that UnorderedTraverse should extends Functor. We can implement map as described above and not break anyone. However, that would give Set a Functor which would be unlawful, and Functor is a much more commonly used typeclass than UnorderedTraverse (which with this new change really only has one instance that we know about: hashmaps). Moreover, the UnorderedTraverseLaws don't have the correct typeclasses to actually call the FunctorLaws, and due to binary compatibility requirements, we can't add them.

I see two paths forward here:

1. admit we messed up and just consider UnorderedTraverse somewhat lawless: if unorderedTraverse(f)(identity) doesn't even have to be f, which our laws don't require, I don't know how you can really program against this API. We can't add this law currently because the UnorderedTraverseLaws don't accept implicits to check equality on F[A] (we don't have Eq[F[A]] We could do some hack, like check that law inside of a X.pure(...) because we have Eq[X[F[A]] but that seems ugly.

2. we could make UnorderedTraverse extends Functor, which would make our current Set implementation lawless. We could fix this by removing the implicit from the current instance, mark it deprecated and make a new implicit that is lowered to UnorderedFoldable which is IMO the correct thing for Set. Note that Set is already suspect for UnorderedTraverse because to go from Set[A] to Set[B] you are relying on universal hashing on B. If we had a proper parametric HashSet, we would require not only A => F[B] but Hash[B] to create the Set[B], which makes it clear that this could not be a valid UnorderedTraverse. I think the code smell here is pretty strong that we made the wrong choice originally and this would be my preferred path forward.

If we can get some agreement, I will prepare the PR to do step 2.

cc @satorg @armanbilge @LukaJCB