Malvolio - 1 year ago 78

Scala Question

Scala has the trait

`Iterable[A]`

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

That certainly

- the minor one: the return-type of the function passed in is this . I think this is just a convenience that can be overlooked when judging monad-ness.
`GenTraversableOnce`

- 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?

Answer Source

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 `flatMap`

s 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 `Iterable`

s *in general* form a monad under `flatMap`

.