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?

Matthias Braun · Accepted Answer · 2017-02-27 09:24:29Z

21

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.

edited Feb 27, 2017 at 9:24

Matthias Braun

34.8k27 gold badges158 silver badges177 bronze badges

answered Mar 21, 2015 at 21:27

bmaderbacher

1,2611 gold badge10 silver badges19 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Bergi Over a year ago

Is that just Lists flatMap or does this work for every type in Scala?

bmaderbacher Over a year ago

The GenTraversableOnce is used for all "list like" collections in Scala. It's possible to use e.g. a Vector in combination with a List. Vector(1).flatMap(x=>List(x)) == Vector(1) or List(1).flatMap(x=>Vector(x)) == List(1)

Bergi Over a year ago

Nah, I wondered whether the use of GenTraversableOnce in the flatMap signature is a generalisation that is specific to lists, or is working in all monads (types with a flatMap method?)?

bmaderbacher Over a year ago

It's only defined this way for List, Vector and probably some other similar types. Option on the other hand has a simple flatMap as you would expect: final def flatMap[B](f: (A) ⇒ Option[B]): Option[B]

bmaderbacher Over a year ago

@Bergi I've looked into it and it seems that every subclass of TraversableOnce shows this behavior, I've added the details to my answer.

chi · Accepted Answer · 2015-03-21 21:11:58Z

12

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.

answered Mar 21, 2015 at 21:11

chi

117k4 gold badges143 silver badges230 bronze badges

2 Comments

Jas Over a year ago

where do i see in the signature (a -> m b) that the function should generate a traversable type, i only see that the function should produce m b but m is general isn't it where does it say a list? isn't a list denoted in haskell by [] i don't see any [] in the haskell bind definition...

chi Over a year ago

@Jas Above I'm only saying that Scala's bind for lists (shown above) is more general than Haskell's bind for lists. I am not comparing the general bind (Scala has no "general" bind, only classes which happen to have a flatMap, IIRC). In Haskell, we have a list-bind [a] -> (a -> [b]) -> [b] when in Scala it is more similar to [a] -> (a -> t b) -> [b] for a suitable t.

David Reynolds · Accepted Answer · 2023-07-19 04:48:35Z

A Perspective:

Given that Haskell's >>= signature is:

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

You need to make sure that you properly recognize the types of a and b.

Given the initial part of the expression ...

[ [1] ] >>= ...

This suggests that m corresponds to [], which then implies that the type a refers to [Int].

Given this recognition, Just doesn't have the appropriate structure. In order to be consistent with what you have, you'd need something like:

f :: [Int] -> [Maybe [Int]] = \x -> [Just x]

If you use that, then you should get:

ghci> [[1]] >>= f
[Just [1]]

In Scala, if you do something like:

    trait Monad[M[_] : Applicative]:
      extension [A](a: A)
        def rtrn() : M[A] // Scala version of Haskell's return
      extension [A](x: M[A])
        def >>=[B](h: A => M[B]): M[B]
        def >:>[B](y: M[B]): M[B] = x >>= ( (_ : A) => y )

In order to have the code be simple and be consistent with Haskell's general picture, it is assumed that Functor and Applicative have also been defined. The notation used above is not idiomatic Scala, but rather used to draw a greater parallel with Haskell's syntax. Notice that rtrn is used instead of return and >:> instead of >>.

An instance of Monad for List could look like:

    given Monad[List] with
      extension [A](x: A)
        def rtrn():List[A] = List( x )
      extension [A](xs: List[A])
        def >>=[B](h: A => List[B]): List[B] = 
          xs.fmap(h)
            .foldLeft(List() : List[B])( (_ ++ _) : (List[B], List[B]) => List[B])

Since it's assumed that Functor and Applicative have been written, fmap would be defined in the Functor trait.

Using this, you can replicate the Haskell result in Scala.

scala> List(List(1)) >>= ( (u : List[Int]) => List ( Some ( u ) ) ) 
val res0: List[Some[List[Int]]] = List(Some(List(1)))

As others have indicated, Scala's flatMap is essentially just a more general form of >>=. Thus, when applied like the above, you get the same result!

scala> List(List(1)).flatMap( (u : List[Int]) => List ( Some ( u ) ) )
val res4: List[Some[List[Int]]] = List(Some(List(1)))

Abstracting things just a little bit, the effective type-signature for flatMap is effectively (using Haskell syntax):

flatMap :: (Monad m, ??? t) => m a -> (a -> t b) -> m b

The ??? above is something that includes the Monad kind, but is even weaker (thereby making it to be more general).

Collectives™ on Stack Overflow

Comparing Haskell and Scala Bind/Flatmap Examples

3 Answers 3

5 Comments

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related