How does flatmap really work in Scala

Question

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)

Disgustingly enough, you can put pretty much whatever signature you want onto flatmap, map, and filter and still use for comprehensions. — Alec
– Alec, Commented Sep 15, 2017 at 20:40

Victor Moroz · Accepted Answer · 2017-09-16 01:51:21Z

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)

dhg · Accepted Answer · 2017-09-15 19:32:13Z

1

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.

answered Sep 15, 2017 at 19:32

dhg

52.8k8 gold badges125 silver badges144 bronze badges

1 Comment

cchantep Over a year ago

There is no need to have a look at the compiler source, that's documented in the publish Scaladoc about the Scala library

puhlen · Accepted Answer · 2017-09-15 22:22:52Z

1

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.

edited Sep 15, 2017 at 22:22

answered Sep 15, 2017 at 19:32

puhlen

8,5591 gold badge19 silver badges32 bronze badges

1 Comment

HTNW Over a year ago

List forms a perfectly good monad. Just because you can do more than a normal monad doesn't prevent it from being a monad. Restricting flatMap to return List is perfectly fine and generates the basic monadic bind. Otherwise put, the fact that monadic bind usually has the name flatMap should not be enough to disqualify List from being a monad just because it's bind operation is named differently. If there's some trait Monadic[M[A] <: Monadic[M]] { def flatMap(f: A => M[B]): B }, you can say that List is not Monadic, but its wrong to say that this means it isn't a monad.

Collectives™ on Stack Overflow

How does flatmap really work in Scala

3 Answers 3

Comments

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related