Comparing Haskell and Scala Bind/Flatmap Examples

Question

The following bind(>>=) code, in Haskell, does not compile:

ghci> [[1]] >>= Just
<interactive>:38:11:
    Couldn't match type ‘Maybe’ with ‘[]’
    Expected type: [t] -> [[t]]
      Actual type: [t] -> Maybe [t]
    In the second argument of ‘(>>=)’, namely ‘Just’
    In the expression: [[1]] >>= Just

But, in Scala, it does actually compile and run:

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

Haskell's >>= signature is:

>>= :: Monad m => m a -> (a -> m b) -> m b

So, in [[1]] >>= f, f's type should be: a -> [b].

Why does the Scala code compile?

Answer 1

As @chi explained Scala's flatMap is more general than the Haskell's >>=. The full signature from the Scala docs is:

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

This implicit isn't relevant for this specific problem, so we could as well use the simpler definition:

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

There is only one Problem, Option is no subclass of GenTraversableOnce, here an implicit conversion comes in. Scala defines an implicit conversion from Option to Iterable which is a subclass of Traversable which is a subclass of GenTraversableOnce.

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

The implicit is defined in the companion object of Option.

A simpler way to see the implicit at work is to assign a Option to an Iterable val:

scala> val i:Iterable[Int] = Some(1)
i: Iterable[Int] = List(1)

Scala uses some defaulting rules, to select List as the implementation of Iterable.

The fact that you can combine different subtypes of TraversableOnce with monad operations comes from the implicit class MonadOps:

  implicit class MonadOps[+A](trav: TraversableOnce[A]) {
    def map[B](f: A => B): TraversableOnce[B] = trav.toIterator map f
    def flatMap[B](f: A => GenTraversableOnce[B]): TraversableOnce[B] = trav.toIterator flatMap f
    def withFilter(p: A => Boolean) = trav.toIterator filter p
    def filter(p: A => Boolean): TraversableOnce[A] = withFilter(p)
  }

This enhances every TraversableOnce with the methods above. The subtypes are free to define more efficient versions on there own, these will shadow the implicit definitions. This is the case for List.

Answer 2

Quoting from the Scala reference for List

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

So, flatMap is more general than Haskell's (>>=), since it only requires the mapped function f to generate a traversable type, not necessarily a List.