How can we map a Set?

Scalaz used to have a scalaz.Functor for scala.collection.Set but it was eventually removed because it relied on Any’s == method. You can read more about why Functor[Set] is a bad idea at Fake Theorems for Free.

If Set had been truly parametric, we wouldn’t have been able to define a Functor in the first place. Luckily, a truly parametric Set has recently been added to Scalaz as scalaz.ISet, with preliminary benchmarks also showing some nice performance improvements. I highly recommend using ISet whenever you can!

Now we can see the problem more clearly; the type of map on ISet is too restrictive to be used inside of a Functor because of the scalaz.Order constraint:

def map[B: Order](f: A => B): ISet[B]

And it might seem like we’ve lost something useful by not having a Functor available. For example, we can’t write the following:

val nes = OneAnd("2014-05-01", ISet.fromList("2014-06-01" :: "2014-06-22" :: Nil)) // a non-empty Set
val OneAnd(h, t) = nes.map(parseDate)

Which is because the map function on scalaz.OneAnd requires a scalaz.Functor for the F[_] type parameter, which is ISet in the above example.

But we have a solution! It’s called Coyoneda (also known as the Free Functor) and it’ll hopefully be able to demonstrate why not having Functor[ISet] available has no fundamental, practical consequences.

Coyoneda can be defined in Scala like so:

trait Coyoneda[F[_], A] {
  type I
  def k: I => A
  def fi: F[I]
}

There are just three parts to it:

1. I - an existential type
2. k - a mapping from I to A
3. fi - a value of F[I]

We can create a couple of functions to help with constructing a Coyoneda value:

def apply[F[_], A, B](fa: F[A])(_k: A => B): Coyoneda[F, B] { type I = A } =
  new Coyoneda[F, B] {
    type I = A
    val k = _k
    val fi = fa
  }

def lift[F[_], A](fa: F[A]): Coyoneda[F, A] = Coyoneda(fa)(identity[A])

The constructors allow any type constructor to become a Coyoneda value:

val s: Coyoneda[ISet, Int] = Coyoneda.lift(ISet.fromList(1 :: 2 :: 3 :: Nil))

Now here’s the special part; we can define a Functor for all Coyoneda values:

implicit def coyonedaFunctor[F[_]]: Functor[({type λ[α] = Coyoneda[F, α]})#λ] =
  new Functor[({type λ[α] = Coyoneda[F,α]})#λ] {
    def map[A, B](ya: Coyoneda[F, A])(f: A => B) = Coyoneda(ya.fi)(f compose ya.k)
  }

What’s interesting is that the F[_] type does not have to have a Functor defined for the Coyoneda to be mapped!

Let’s use this to try out our original example. We’ll define a type alias to make things a bit cleaner:

type ISetF[A] = Coyoneda[ISet, A]

And we can use this new type instead of a plain ISet:

// Scala has a really hard time with inference here, so we have to help it out.
val functor = OneAnd.oneAndFunctor[ISetF](Coyoneda.coyonedaFunctor[ISet])
import functor.functorSyntax._

val nes = OneAnd[ISetF, String]("2014-05-01", Coyoneda.lift(ISet.fromList("2014-06-01" :: "2014-06-22" :: Nil)))
val OneAnd(h, t) = nes.map(parseDate)

So we’ve been able to map the Coyoneda! But how do we do something useful with it?

We couldn’t define a Functor because it needs scalaz.Order on the output type, but we can use the map method directly on ISet. We can use that function by running the Coyoneda like so:

// Converts ISetF back to an ISet, using ISet#map with the Order constraint
val s = t.fi.map(t.k).insert(h)

And we’re done!

We’ve been able to use Coyoneda to treat an ISet as a Functor, even though its map function is too constrained to have one defined directly. This same technique applies to scala.collection.Set and any other type-constructor which would otherwise require a restricted Functor. I hope this has demonstrated that Functor[Set] not existing has no practical consequences, other than scalac not being as good at type-inference.