Help understanding map2

Question
#1

What should map2 return in the case of List[Int]?

I’m trying for the 5th time to read the Monad chapter of the Red Book (Functional Programming in Scala by Chiusano and Bjarnason). Section 11.2 attempts to motivate monads by looking at previous implementations of map2 for three classes introduced in previous chapters, Gen, Parser, and Option.
However, the generalization seems weird to me.

  def map2[A,B,C](fa:Gen[A], fb:Gen[B], f:(A,B)=>C):Gen[C] = {
    fa flatMap (a => fb map (b => f(a,b)))
  }
  def map2[A,B,C](fa:Parser[A], fb:Parser[B], f:(A,B)=>C):Parser[C] = {
    fa flatMap (a => fb map (b => f(a,b)))
  }
  def map2[A,B,C](fa:Option[A], fb:Option[B], f:(A,B)=>C):Option[C] = {
    fa flatMap (a => fb map (b => f(a,b)))
  }

Thus in they define map2 more generally as follows:

trait Mon[F[_]] {
  def map2[A,B,C](fa: F[A], fb: F[B], f: (A,B)=>C): F[C] = 
    fa flatMap (a => fb map (b => f(a,b)))

However, when I try to use this definition for List[Int] I get an inconsistent result.
Should map2(List(1,2,3),List(10,20,30), _+_) return List(11,22,33), or should it return List(11, 21, 31, 12, 22, 32, 13, 23, 33) ? I was under the impression map2 was supposed to apply the binary function to corresponding elements of the two lists, not every possible pairing.

Do I misunderstand map2?

#2

map2 as you defined it will indeed give you the cartesian product: fb.map(f) will apply f to all elements of fb, this is then applied to all elements of fa by your fa.flatMap(g). For Lists this is equivalent to the following imperative code:

val out = mutable.MutableList[C]()
for (i <- 0 until fa.length) {
  for (j <- 0 until fb.length) {
    out += f(fa(i), fb(j))
  }
}

If you want to apply it to the corresponding elements instead then you want to use zip, for example:

fa.zip(fb).map { case ((a, b)) => f(a, b) }

This can also be shortened since we’re just applying it to f (tupled converts a function from taking N arguments to taking a single N-tuple argument):

fa.zip(fb).map(f.tupled)

This is roughly equivalent to the following imperative code:

val out = mutable.MutableList[C]()
for (i <- 0 until math.min(fa.length, fb.length)) {
  out += f(fa(i), fb(i))
}
1 Like
#3

The red book curiously avoids the discussion of the List monad in this section. The mysterious omission confuses the reader in my opinion. The implication is that map2 can be defined as shown, when actually it cannot.

#4

In monad world List represents computations that can have many answers, and composing lists with flatMap (and map2 as defined here) gives you every possible answer.

When you get to applicative functors you’ll see that map2 characterizes something more general than monad, and indeed you can define a zipping Applicative instance for List as long as you forget that it’s a monad.

1 Like