Set sequencing type puzzle

Question

Last night in responding to this question, I noticed the following:

scala> val foo: Option[Set[Int]] = Some(Set(1, 2, 3))
foo: Option[Set[Int]] = Some(Set(1, 2, 3))

scala> import scalaz._, Scalaz._
import scalaz._
import Scalaz._

scala> foo.sequenceU
res0: scala.collection.immutable.Set[Int] = Set(1, 2, 3)

That is, if foo is an optional set of integers, sequencing it returns a set of integers.

This isn't what I expected at first, since sequencing a F[G[A]] should return a G[F[A]] (assuming that F is traversable and G is an applicative functor). In this case, though, the Option layer just disappears.

I know this probably has something to do with some interaction between one of the supertypes of Set and the Unapply machinery that makes sequenceU work, and when I can find a few minutes I'm planning to work through the types and write up a description of what's going on.

It seems like a potentially interesting little puzzle, though, and I thought I'd post it here in case someone can beat me to an answer.

Answer 1

wow, yeah. Here's what I can surmise is happening. since Set doesn't have an Applicative of its own, we are getting the Monoid#applicative instance instead:

scala> implicitly[Unapply[Applicative, Set[Int]]].TC
res0: scalaz.Applicative[_1.M] forSome { val _1: scalaz.Unapply[scalaz.Applicative,Set[Int]] } = scalaz.Monoid$$anon$1@7f5d0856

Since Monoid is defined for types of kind * and applicative is defined for types of kind * -> *, the definition of Applicative in Monoid sorta wedges in an ignored type parameter using a type lambda:

final def applicative: Applicative[({type λ[α]=F})#λ] = new Applicative[({type λ[α]=F})#λ] with SemigroupApply...

Notice there that the type parameter α of λ is thrown away, so when Applicative#point is called, which becomes Monoid#zero, instead of it being a Monoid[Set[Option[Int]]] it is a Monoid[Set[Int]].

larsh points out that this has the interesting side-effect of alllowing sequenceU to be (ab)used as sum:

scala> List(1,2,3).sequenceU
res3: Int = 6