CODEWITHSUNDEEP
scala
Rpant
Rpant

Reputation: 1054

How does flatmap really work in Scala

I took the scala odersky course and thought that the function that Flatmap takes as arguments , takes an element of Monad and returns a monad of different type.

trait M[T] {
    def flatMap[U](f: T => M[U]): M[U]
}

On Monad M[T] , the return type of function is also the same Monad , the type parameter U might be different.

However I have seen examples on internet , where the function returns a completely different Monad. I was under impression that return type of function should the same Monad. Can someone simplify the below to explain how flapmap results in the actual value instead of Option in the list.

Is the List not a Monad in Scala.

val l= List(1,2,3,4,5)
def f(x:int) = if (x>2) Some(x) else None
l.map(x=>f(x))
//Result List[Option[Int]] = List( None , None , Some(3) , Some(4) , Some(5))
l.flatMap(x=>f(x))
//Result: List(3,4,5)

Upvotes: 1

Views: 389

Answers (3)

Victor Moroz
Victor Moroz

Reputation: 9225

Let's start from the fact that M[T]is not a monad by itself. It's a type constructor. It becomes a monad when it's associated with two operators: bind and return (or unit). There are also monad laws these operators must satisfy, but let's omit them for brevity. In Haskell the type of bind is:

class Monad m where
  ...
  (>>=) :: m a -> (a -> m b) -> m b

where m is a type constructor. Since Scala is OO language bind will look like (first argument is self): 

trait M[T] {
    def bind[U](f: T => M[U]): M[U]
}

Here M === m, T === a, U === b. bind is often called flatMap. In a pure spherical world in a vacuum that would be a signature of flatMap in OO language. Scala is a very practical language, so the real signature of flatMap for List is:

final def flatMap[B, That](f: (A) ⇒ GenTraversableOnce[B])(implicit bf: CanBuildFrom[List[A], B, That]): That

It's not bind, but will work as a monadic bind if you provide f in the form of (A) => List[B] and also make sure that That is List[B]. On the other hand Scala is not going to watch your back if you provide something different, but will try to find some meaningful conversion (e.g. CanBuildFrom or something else) if it exists.

UPDATE

You can play with scalac flags (-Xlog-implicits, -Xlog-implicit-conversions) to see what's happening:

scala> List(1).flatMap { x => Some(x) }
<console>:1: inferred view from Some[Int] to scala.collection.GenTraversableOnce[?] via scala.this.Option.option2Iterable[Int]: (xo: Option[Int])Iterable[Int]
       List(1).flatMap { x => Some(x) }
                                  ^
res1: List[Int] = List(1)

Upvotes: 2

puhlen
puhlen

Reputation: 8519

The flatmap found in the standard library is a much more general and flexible method than the monadic bind method like the flatMap from Odersky's example.

For example, the full signature of flatmap on List is

def flatMap[B, That](f: (A) ⇒ GenTraversableOnce[B])(implicit bf: CanBuildFrom[List[A], B, That]): That

Instead of requiring the function passed into flatmap to return a List, it is able to return any GenTraversableOnce object, a very generic type.

flatmap then uses the implicit CanBuildFrom mechanism to determine the appropriate type to return.

So when you use flatmap with a function that returns a List, it is a monadic bind operation, but it lets you use other types as well.

Upvotes: 1

dhg
dhg

Reputation: 52681

Hmm, perhaps confusingly, the signature you gave is not actually correct, since it's really (in simplified form):

def flatMap[B](f: (A) ⇒ GenTraversableOnce[B]): Traversable[B]

Since the compiler is open-source, you can actually see what it's doing (with its full signature):

def flatMap[B, That](f: A => GenTraversableOnce[B])(implicit bf: CanBuildFrom[Repr, B, That]): That = {
  def builder = bf(repr) // extracted to keep method size under 35 bytes, so that it can be JIT-inlined
  val b = builder
  for (x <- this) b ++= f(x).seq
  b.result
}

So you can see that there is actually no requirement that the return type of f be the same as the return type of flatMap.

Upvotes: 1

Related Questions