Why set cannot be a functor

This is well known but keeps tripping me up when I think of an example so here it is.

Set demands that its elements implement Eq (or equals() or whatever is semantically equivalent). List has no such requirement. A bogus equals implementation will lead to Set violating the functor laws. 

Imagine an implementation that looked something like:

class OddEquals(val id: Int, val label: String) {

  override def equals(a: Any): Boolean =

    if (a.isInstanceOf[OddEquals]) {

      val other = a.asInstanceOf[OddEquals]

      id == other.id

    } else false

  override def hashCode(): Int = id

}

which would be a fairly typical piece of code for objects whose identity depends solely on their primary key.

Now, image two services. One finds an entity given any related string, we'll call it f. I'll fake it like this:

  type F = String => OddEquals

  val f: F = x => new OddEquals(x.length, x)

The other service simply extracts the entity's name:

  type G = OddEquals => String

  val g: G = _.label

The functor law says:

xs.map(x => g(f(x))) == xs.map(f).map(g))

But if xs is Set("hello", "world"), the left-hand side is the same as the input but the right-hand side is Set("hello").

Compare this to List("hello", "world") and you'll see that both left- and right-hand side are equal (that is, same as xs)