Implementing `sequence` on a Monad

Question

Working on another exercise to implement Monad.sequence() from Functional Programming in Scala, my answer differs from the official/known-to-be correct answer:

def sequence[A](lma: List[F[A]]): F[List[A]]

Official:

def sequence[A](lma: List[F[A]]): F[List[A]] =
  lma.foldRight(unit(List[A]()))((ma, mla) => map2(ma, mla)(_ :: _))

Mine:

def sequence[A](lma: List[F[A]]): F[List[A]] = F(lma.flatten)

Example where F is Option:

scala> val x: List[Option[Int]] = List( Some(1), None)
x: List[Option[Int]] = List(Some(1), None)

scala> Some(x.flatten)
res1: Some[List[Int]] = Some(List(1))

Is my answer (or the spirit of it) legitimate here?

I get the following compile-time exception, but I'm sure if it's related to my lack of understanding of type constructors.

Monad.scala:15: error: not found: value F
F(lma.flatten)

Answer 1

When you write Option(1), what's actually happening is that you're calling the apply method on the Option companion object. This is only very indirectly related to the Option type—specifically, there's no way in general to get the Something companion object (which is a value) if you only have a type variable referring to the Something type. In fact there's no guarantee that the companion object even exists, and even if it does exist, its apply method might return something that's entirely not an instance of the Something type. The fact that X.apply(...) does return an X in the case of List and Option and case classes is entirely a matter of convention.

The other part of the issue here is the call to List.flatten. If you look at the "Full Signature" for flatten in the docs, you'll see that it has an implicit argument:

def flatten[B](implicit asTraversable: (A) => GenTraversableOnce[B]): List[B]

This means that you can only use it on a List[A] if A can be implicitly converted into a GenTraversableOnce of some kind. This isn't the case in general for any old monad.

I'd encourage you to prove these things to yourself, though—try your implementation with some of the other monads from the exercises and see where things break down.