16

Scala has the trait Iterable[A] that defines

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

That certainly looks like the bind function on a monad, and the documentation hints that it is a monad, but there are two objections, one minor and one major:

  • the minor one: the return-type of the function passed in is this GenTraversableOnce. I think this is just a convenience that can be overlooked when judging monad-ness.
  • the major one: the "value" of the monad is the list of all the values it contains, but the function is given the values one at a time.

Do these problems break the monad-ness of the collection?

3
  • 2
    A relevant question is does Scala per se (excluding scalaz) have native monads and what are some examples? Answers would depend on how respondents choose to define a monad. Odersky's point is that they have additonal requirements for compatibility with object orientation in Scala. In that sense the Scala concept of monad is unique to Scala and mabye saying "monad like" would be more appropriate. However, since the discussion is about Scala, you introduced the term monad in that context and it has been reasonably defined for Scala by Odersky, there is no need to qualify it in responses.
    – user4322779
    Jan 3, 2015 at 1:21
  • 1
    note that this isn't even the type signature of flatMap which is defined in TraversableLike, it is: def flatMap[B, That](f: (A) ⇒ GenTraversableOnce[B])(implicit bf: CanBuildFrom[Iterable[A], B, That]): That see: github.com/scala/scala/blob/2.11.x/src/library/scala/collection/…
    – stew
    Jan 3, 2015 at 4:02
  • 1

5 Answers 5

24

The "major" concern is easier to answer: no, it doesn't, because that's not what it means. A monad is not required to have any particular "value" or none, only to compose with functions in particular ways.

For the "minor" one, you're right to be concerned about the types. Properly, a monad is a monoid (with some additional constraints), meaning it's a set with certain operations. The elements of this set are, as far as I can tell, things of type A => M[B] (in scalaz this type is called Kleisli); flatMap is the |+| operation of the monoid.

Does the set of all possible A => Iterable[B] in Scala form a monoid with respect to this operation (and a suitable choice of identity)? No, very much not, because there are plenty of possible A => Iterable[B] that violate the monad laws. For a trivial example, {a: A => throw new RuntimeException()}. A more serious example is that e.g. if a Set is present in a flatMap chain, this can break associativity: suppose we have:

f: String => Iterable[String] = {s => List(s)}
g: String => Iterable[String] = {s => Set(s)}
h: String => Iterable[String] = {s => List("hi", "hi")}

Then

((f |+| g) |+| h).apply("hi") = List("hi") flatMap h = List("hi", "hi")

but

(f |+| (g |+| h)).apply("hi") = List("hi") flatMap {s => Set("hi")} = List("hi")

which is upsetting, because the whole point of a monoid is that we can write f |+| g |+| h and not worry about which way we evaluate it. Going back to monads, the point is that we should be able to write

for {
  a <- f("hi")
  b <- g(a)
  c <- h(b)
} yield c

and not worry about which order the flatMaps are composed in. But for the f, g and h from above, which answer do you expect the above code to give? (I know the answer, but it's quite surprising). With a true monad, the question wouldn't come up except as a scala compiler implementation detail, because the answer would be the same either way.

On the other hand, does a particular subset of possible A => M[B], e.g. "the set of all A => List[B] implemented under the scalazzi safe subset of scala", form a monad with respect to that definition of flatMap? Yes (at least for the commonly accepted definition of when two scala functions are equal). And there are several subsets for which this applies. But I think it's not entirely true to say that scala Iterables in general form a monad under flatMap.

3
  • 2
    (1) {a: A => throw new RuntimeException()} With this example in hand, you can argue that monads do not exist in Scala at all. (2) "if a Set is present in a flatMap" A monadic operation is only monadic if the monad at both sides of it is the same. A.flatMap(somethingorothertharterurnsB) is not subject to monad laws. Monad laws for A are only concerned with functions that return A. Jan 4, 2015 at 8:19
  • 1
    1) I prefer to think of it as "only certain subsets of possible Scala functions (e.g. the scalazzi safe subset) form monads". It's an important thing to bear in mind, particularly for people coming from e.g. Haskell. 2) The question asks about Iterable; List and Set are both subtypes of that.
    – lmm
    Jan 4, 2015 at 9:12
  • Ah OK. Iterable is not a monad of course. It's not even a collection. Its subtypes may be (different) monads. Jan 4, 2015 at 9:37
18

The answer to your headline question is maybe. A collection with flatMap is not sufficient to be a monad, but it might be a monad if it satisfies some further conditions.

Your "minor" issue certainly breaks the monadicity (the proper word for "monad-ness") of Iterable. This is because many subtypes of Iterable and GenTraversableOnce are not monads. Therefore, Iterable is not a monad.

Your "major" issue is not a problem at all. For example, the function argument to the List monad's flatMap receives the elements of the List one at a time. Each element of the list generates a whole list of results, and those lists are all concatenated together at the end.

Fortunately, judging whether something is a monad is really easy! We just have to know the precise definition of monad.

The requirements for being a monad

  1. A monad has to be a type constructor F[_] that takes one type argument. For example, F could be List, Function0, Option, etc.
  2. A monadic unit. This is a function that takes a value of any type A and produces a value of type F[A].
  3. A monadic composition operation. It's an operation that takes a function of type A => F[B], and a function of type B => F[C] and produces a composite function of type A => F[C].

(There are other ways of stating this, but I find this formulation straightforward to explain)

Consider these for Iterable. It definitely takes one type argument. It has a unit of sorts in the function Iterable(_). And while its flatMap operation doesn't strictly conform, we could certainly write:

def unit[A](a: A): Iterable[A] = Iterable(a)

def compose[A,B,C](f: A => Iterable[B],
                   g: B => Iterable[C]): A => Iterable[C] =
  a => f(a).flatMap(g)

But this does not make it a monad, since a monad additionally has to satisfy certain laws:

  1. Associativity: compose(compose(f, g), h) = compose(f, compose(g, h))
  2. Identity: compose(unit, f) = f = compose(f, unit)

An easy way to break these laws, as lmm has already pointed out, is to mix Set and List as the Iterable in these expressions.

"Semimonads"

While a type construction with just flatMap (and not unit), is not a monad, it may form what's called a Kleisli semigroupoid. The requirements are the same as for monad, except without the unit operation and without the identity law.

(A note on terminology: A monad forms a Kleisli category, and a semigroupoid is a category without identities.)

For-comprehensions

Scala's for-comprehensions technically have even fewer requirements than semigroupoids (just map and flatMap operations obeying no laws). But using them with things that are not at least semigroupoids has very strange and surprising effects. For example, it means that you can't inline definitions in a for-comprehension. If you had

val p = for {
  x <- foo
  y <- bar
} yield x + y

And the definition of foo were

val foo = for {
  a <- baz
  b <- qux
} yield a * b

Unless the associativity law holds, we cannot rely on being able to rewrite this as:

val p = for {
  a <- baz
  b <- qux
  y <- bar
} yield a * b + y

Not being able to do this kind of substitution is extremely counterintuitive. So most of the time when we work with for-comprehensions we assume that we're working in a monad (likely even if we're not aware of this), or at least a Kleisli semigroupoid.

But note that this kind of substitution does not work in general for Iterable:

scala> val bar: Iterable[Int] = List(1,2,3)
bar: Iterable[Int] = List(1, 2, 3)

scala> val baz: Iterable[Int] = Set(1,2,3)
baz: Iterable[Int] = Set(1, 2, 3)

scala> val qux: Iterable[Int] = List(1,1)
qux: Iterable[Int] = List(1, 1)

scala> val foo = for {
     |   x <- bar
     |   y <- baz
     | } yield x * y
foo: Iterable[Int] = List(1, 2, 3, 2, 4, 6, 3, 6, 9)

scala> for {
     |   x <- foo
     |   y <- qux
     | } yield x + y
res0: Iterable[Int] = List(2, 2, 3, 3, 4, 4, 3, 3, 5, 5, 7, 7, 4, 4, 7, 7, 10, 10)

scala> for {
     |   x <- bar
     |   y <- baz
     |   z <- qux
     | } yield x * y + z
res1: Iterable[Int] = List(2, 3, 4, 3, 5, 7, 4, 7, 10)

For more information about monads

For more on monads in Scala, including what it all means and why we should care, I encourage you to have a look at chapter 11 of my book.

4
  • Am I correct in thinking that if you repaired the flaw in the type-signature, so it was def flatMap[B](f: (A) ⇒ Iterable[B]): Iterable[B], that would fix associativity (ignoring covariance issues for now) and then Iterable would be a (true) Monad? Also, I don't understand the basis for your statement, "The trick is that because List is a monad, the resulting lists are all concatenated." Jan 10, 2015 at 14:36
  • And it also seems that Futures (which do not have a true unit) are not Monads, despite having an associative bind in when. Jan 10, 2015 at 14:38
  • 1
    No, fixing up the type signature of flatMap on Iterable would not fix the associativity issue. The core issue is that two Iterable instances may have different semantics for flatMap.
    – Apocalisp
    Jan 11, 2015 at 3:54
  • 3
    Futures definitely do have a unit. If you have a value of some type A, you can always turn that into a Future[A] that just returns that value.
    – Apocalisp
    Jan 11, 2015 at 3:56
2

I think a collection with a flatMap is not necessarily a monad. It does not necessarily fit the monad laws. These laws are probably better explained in Functional Programming in Scala than I could do.

Recently I heard from a coworker a simplified and pragmatic explanation (with self-consciousness) of what is a monad in Scala: something you can put in a for comprehension.

I'm not a monad expert, but it seems to me that this is not true, and so it is for collections with flatMap. The most obvious exemple of this is in Scala lib Either as it is not right biaised and it does not have any flatMap method until you project it to a side (and this projection is not monadic as it returns Either). As far as I understand it, a type is not a monad (or a monoid or whatever), but a type may have a monad (or even many ones? not sure but would be interested by any exemple (but maybe Either is the good one?)).

I think Scala is a pragmatic language, in which it can sometimes be useful to forget about strict rules and help programmers to do their job more easily. Not all programmers care about what is a monad, but many probably want to flatten a List[Set[Int]] at some point and flatMap may help them.

This reminds me of this blog post in which the Future type is considered as copointed for tests.

1
  • I almost fully rephrased my answer. Ch29 of Programming in Scala 2ed is "For Expressions Revisited". It is about determining the functions necessary to support the full range of for expressions and loops in order to enable their translation using those functions. This is why withFilter is necessary. See stackoverflow.com/questions/15149738/… for monad implementations in core scala without scalaz.
    – user4322779
    Jan 4, 2015 at 2:35
2

To answer your question in the context of core Scala excluding Scalaz and category theory, while core Scala does not have a trait, class or object named "Monad", it does implement an object-oriented concept of monad that I will reference as Orderskian monad, since it was invented and implemented primarily by Martin Ordersky (and Adrian Moors according to http://igstan.ro/posts/2012-08-23-scala-s-flatmap-is-not-haskell-s.html).

An Orderskian monad requires at least map, flatmap and withFilter functions as explained in "Programming In Scala" (2Ed:PDF edition:chapter 23:page 531) by Martin Odersky where he states "Therefore, map, flatMap and withFilter can be seen as an object-oriented version of the functional concept of monad." Based on this, Scala Collections are Orderskian monads.

To answer your question including Scalaz, it requires a scalaz.Monad implementatation to extend the Monad trait and implement two abstract functions, pure and bind, in order to satisfy three laws requiring them (http://scalaz.github.io/scalaz/scalaz-2.9.1-6.0.2/doc/index.html#scalaz.Monad). Core Scala collections do not meet those requirements so nothing could ever break their scalaz.Monad-ness because it never existed. To the extent that scalaz.Monad models category theory monad, this argument applies to the latter.

4
  • 2
    People are downvoting this. Why? Is it the discrepancy between the formal definition of Monad in category theory and Odersky's definition of the Monad class? Jan 3, 2015 at 0:28
  • 1
    I could not say and am going with Odersky. If someone has a better answer let them put it up. Scala per se does not have an actual Monad trait or class - that is in scalaz.
    – user4322779
    Jan 3, 2015 at 0:51
  • I'm upvoting but would just correct this: a monad does not need flatmap and map as map can be expressed in term of flatmap and unit anyway (as far as I remember from Functional Programming in Scala) Jan 3, 2015 at 2:17
  • Odersky is a co-author of the paper Parametric type classes scholar.google.com.hk/… , in which they created a definition for Haskell monad. So oderskian monad is actually Haskell monad.
    – Yang Bo
    Mar 12, 2018 at 17:53
1

Scala collection methods flatMap and flatten are more powerful than monadic flatMap/flatten. See here: https://www.slideshare.net/pjschwarz/scala-collection-methods-flatmap-and-flatten-are-more-powerful-than-monadic-flatmap-and-flatten

enter image description here

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.