UnorderedTraverse should extend Functor

[johnynek]

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:

cats/laws/src/main/scala/cats/laws/UnorderedTraverseLaws.scala

Line 30 in e94ddf0

def unorderedTraverseIdentity[A, B](fa: F[A])(f: A => B)(implicit ev: Functor[F]): IsEq[F[B]] =

  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

[satorg]

I suppose path 2 also implies admitting that we messed up :)

I'm personally for path 2, because it entails fixing up the mess. But if we remove the implicit, then we'll formally break source compatibility. Perhaps, it makes sense to just deprecate it for now with a clear message that it is lawless and is subject for complete removal in the future. And probably make the implicit's priority as low as possible. Also, for those downstream projects that happen to use it, provide a non-deprecated alternative in alley-cats.

[satorg]

Speaking of the stuff that was messed up (or wasn't thought through thoroughly) in Cats:

• Traverse has its non-empty counterpart – NonEmptyTraverse. However, no non-empty counterpart exists for UnorderedTraverse (i.e. NonEmptyUnorderedTraverse or UnorderedNonEmptyTraverse – ?).
• Likewise, a non-empty counterpart for Foldable is Reducible. However, there is UnorderedFoldable but no UnorderedReducible in Cats.
• The cherry on top: Cats has Bifoldable that comes in handy sometimes, but doesn't have Bireducible which could be used in some cases too, I guess.

In fact, the latter was the first one I noticed and even started working on adding it in #4469. But then switched to other tasks and to be honest forgot about it. I wonder if it makes sense to resurrect it.

[LukaJCB]

You make some really good arguments for deprecation. I think this might be used rarely enough where this would be okay. It's a shame to lose it but I agree it's a bit of a smell! 👍