Is the flat matrix collection a monad?

Question

Scala has an Iterable[A] attribute that defines

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

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

• minor: the return type of the function passed is GenTraversableOnce . I think this is just a convenience that can be missed when evaluating the monad.
• the main thing: the "value" of the monad is a list of all the values ​​it contains, but the function receives the values ​​one at a time.

Do these problems violate the monadiness of the collection?

Answer 1

The "main" problem is easier to answer: no, it is not, because it is not what it means. The monad is not required to have any particular “value” or not, only to constitute functions in certain ways.

For the "minor" you are right to worry about the types. That's right, a monad is a monoid (with some additional restrictions), which means its set with certain operations. The elements of this set, as far as I can tell, are of type A => M[B] (in a scalar this type is called Kleisli ); flatMap is an operation |+| monoid.

Is the set of all possible A => Iterable[B] in Scala a monoid with respect to this operation (and an appropriate choice of identity)? No, not really, because there are many possible A => Iterable[B] that violate the laws of the monad. For a trivial example, {a: A => throw new RuntimeException()} . A more serious example is that, for example, if a Set present in the flatMap chain, this may violate 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 frustrating because the whole point of the monoid is that we can write f |+| g |+| h f |+| g |+| h f |+| g |+| h and not worry about how we evaluate it. Returning to monads, the fact is that we must write

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

and don’t worry about which order consists of flatMap . But for f , g and h above, what answer do you expect from the code above? (I know the answer, but this is pretty surprising). With a true monad, the question will not arise, except for the Scala compiler detailing, because the answer will be the same anyway.

On the other hand, does any particular subset of the possible A => M[B] , for example. "the set of all A => List[B] , implemented under a safe subset of scala stories, " forms a monad in relation to this definition of flatMap ? Yes (at least for the generally accepted definition 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 Iterable in general is a monad under flatMap .

Answer 2

The answer to your main question is no . Collection with flatMap not enough for the monad. It can be a monad if it satisfies some additional conditions.

Your "minor" problem certainly violates monadicity (the correct word for "monad") Iterable . This is because many subtypes of Iterable and GenTraversableOnce are not monads. Therefore, Iterable not a monad.

Your "main" problem is not a problem at all. For example, the argument to the List monad flatMap flatMap takes List elements one at a time. Each list item generates a list of results, and these lists are combined together at the end.

Fortunately, it’s really easy to judge whether something is a monad! We just need to know the exact definition of the monad.

Monad Requirements

• The monad must be a constructor of type F[_] , which takes one type argument. For example, F could be List , Function0 , Option , etc.
• Monadic unit. This is a function that takes a value of any type A and returns a value of type F[A] .
• Operation monadic composition. This is an operation that performs a function of type A => F[B] and a function of type B => F[C] and creates a composite function of type A => F[C] .

(There are other ways to state this, but I find this wording understandable)

Consider them for Iterable . It definitely takes one type argument. It has a sort function in the Iterable(_) function. And although its flatMap operation flatMap not strictly matched, we could 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 the monad must additionally satisfy certain laws:

• Associativity: compose(compose(f, g), h) = compose(f, compose(g, h))
• Identity: compose(unit, f) = F = compose(f, unit)

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

"Semimonads"

While a type construct with just flatMap (not unit ) is not a monad, it can form what is called a Clisley semigroup. The requirements are the same as for the monad, except without the unit operation and without the law of identity.

(Note on terminology: the monad forms the Claysley category, and the semigroup forms the category without identities.)

For-insights

Scala for concepts technically have even fewer requirements than flatMap (just map and flatMap operations that do not obey any laws). But using them with things that are not at least semi-groupoids has very strange and amazing effects. For example, this means that you cannot embed definitions for understanding. If you

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

And the definition of foo was

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

If the law of associativity is not satisfied, we cannot rely on the ability to rewrite this as:

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

The inability to make such a replacement is extremely incompatible. Therefore, most of the time when we work with understanding, we assume that we work in a monad (probably even if we don’t know this) or at least a semi-group Kleisley.

But note that this kind of lookup doesn’t work at all 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 information on monads in Scala, including everything that it means and why we should care, I recommend that you take a look at Chapter 11 of my book.

Answer 3

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

The warrant monad requires at least a map, a flat map, and Filter functions, as described in Scala Programming (2Ed: PDF edition: chapter 23: p. 531) by Martin Odersky, where he states: "Therefore, a map, a flat map and withFilter can be seen as an object-oriented version of the functional concept of the monad. " Based on this, Scala Collections are warrant monads.

To answer your question, including Scalaz, it requires an implementation of scalaz.Monad to extend the Monad trait and implement two abstract functions, pure and connected, to satisfy the three laws that require them ( http://scalaz.imtqy.com/scalaz/scalaz -2.9.1-6.0.2 / doc / index.html # scalaz.Monad ). Core Scala collections do not meet these requirements, so nothing can break their scalaz.Monad-ness, because it never existed. To the extent that scalaz.Monad models the theory of monad theory, this argument applies to the latter.

Answer 4

I think a flat-card collection is not necessarily a monad. This does not necessarily comply with the laws of the monad . These laws are probably better explained in functional programming in Scala than I could have done.

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

I am not a monad expert, but it seems to me that this is not so, and therefore for collections with flatMap. The most obvious example of this is Scala lib Either , since it is incorrect and has no flatMap method until you project it to the side (and this projection is not monadic, since it returns either). As far as I understand, a type is not a monad (or a monoid or something else), but a type can have a monad (or even many of them) is not sure, but would be interested in any example (but maybe one?)).

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

This reminds me of this blog post in which Future Type is considered rooted for tests .

Answer 5

Scala flatMap and flatten collection methods 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