Behavior of flatMap when applied to List[Option[T]]

Question

Let's take a look at this code:

scala> val a = List(Some(4), None)
a: List[Option[Int]] = List(Some(4), None)
scala> a.flatMap( e=> e)
List[Int] = List(4)

Why would applying flatMap with the function { e => e } on a List[Option[T]] returns a List[T] with the None elements removed?

Specifically, what is the conceptual reasoning behind it -- is it based on some existing theory in functional programming? Is this behavior common in other functional languages?

This, while indeed useful, does feel a bit magical and arbitrary at the same time.

EDIT:

Thank you for your feedbacks and answer. I have rewritten my question to put more emphasis on the conceptual nature of the question. Rather than the Scala specific implementation details, I'm more interested in knowing the formal concepts behind it.

Answer 1

I assume you mean the support for mapping and filtering at the same time with flatMap:

scala> List(1, 2).flatMap {
     |   case i if i % 2 == 0 => Some(i)
     |   case i => None
     | }
res0: List[Int] = List(2)

This works because Option's companion object includes an implicit conversion from Option[A] to Iterable[A], which is a GenTraversableOnce[A], which is what flatMap expects as the return type for its argument function.

It's a convenient idiom, but it doesn't really exist in other functional languages (at least the ones I'm familiar with), since it relies on Scala's weird mix of subtyping, implicit conversions, etc. Haskell for example provides similar functionality through mapMaybe for lists, though.

Answer 2

Let's first look at the Scaladoc for Option's companion object. There we see an implicit conversion:

implicit def option2Iterable[A](xo: Option[A]): Iterable[A]

This means that any option can be implicitly converted to an Iterable, resulting in a collection with zero or one elements. If you have an Option[A] where you need an Iterable[A], the compiler will add the conversion for you.

In your example:

val a = List(Some(4), None)
a.flatMap(e => e)

We are calling List.flatMap, which takes a function A => GenTraversableOnce[B]. In this case, A is Option[Int] and B will be inferred as Int, because through the magic of implicit conversion, e when returned in that function will be converted from an Option[Int] to an Iterable[Int] (which is a subtype of GenTraversableOnce).

At this point, we've essentially done the following:

List(List(1), Nil).flatMap(e => e)

Or, to make our implicit explicit:

List(Option(1), None).flatMap(e => e.toList)

flatMap then works on Option as it does for any linear collection in Scala: take a function of A => List[B] (again, simplifying) and produce a flattened collection of List[B], un-nesting the nested collections in the process.