Can monad with broken associativity law yield incorrect result in for-comprehension?

Question

Here is a Monad instance for ListT (copied from montrivo)

case class ListT[M[_], A](value: M[List[A]])
implicit def listTMonad[M[_]: Monad] = new Monad[ListT[M, *]] {
  override def flatMap[A, B](fa: ListT[M, A])(f: A => ListT[M, B]): ListT[M, B] =
    ListT(
      Monad[M].flatMap[List[A], List[B]](fa.value)(
        list => Traverse[List].flatTraverse[M, A, B](list)(a => f(a).value)
      )
    )
  override def pure[A](a: A): ListT[M, A] = ListT(Monad[M].pure(List(a)))
  override def tailRecM[A, B](a: A)(f: A => ListT[M, Either[A, B]]): ListT[M, B] = ???
}

It does not satisfy associativity monad law

val a: Int => ListT[List, Int] = {
  case 0 => ListT(List(List(0, 1)))
  case 1 => ListT(List(List(0), List(1)))
}
assert(a(0).flatMap(a).flatMap(a) != a(0).flatMap(x ⇒ a(x).flatMap(a)), "Associativity law is not satisfied")

because, although we get the same values, they are in different order

ListT(List(List(0, 1, 0, 0, 1), List(0, 1, 1, 0, 1), List(0, 1, 0, 0), List(0, 1, 0, 1), List(0, 1, 1, 0), List(0, 1, 1, 1)))
ListT(List(List(0, 1, 0, 0, 1), List(0, 1, 0, 0), List(0, 1, 0, 1), List(0, 1, 1, 0, 1), List(0, 1, 1, 0), List(0, 1, 1, 1)))

However it seem to work correctly in for-comprehensions (in my personal project). Generally, is it safe to use "monads" that brake associativity law in for-comprehensions? Could you provide a counter-example demonstrating incorrect result?

a good read https://math.stackexchange.com/questions/1348692/why-associativity-h-circ-g-circ-f-h-circ-g-circ-f-is-required-in-com/1348702 — 1565986223, Feb 29 '20 at 15:56

score 5 · Accepted Answer · answered Feb 29 '20 at 16:13

Since for-comprehensions are syntactic sugar for flatMap (and map), it definitely is the case that a broken flatMap could result in incorrect for-comprehension code. For example:

import cats.{Monad, Traverse}, cats.implicits._

// Your code here...

val first = for {
  y <- for {
    x <- a(0)
    y <- a(x)
  } yield y
  z <- a(y)
} yield z

val second = for {
  x <- a(0)
  y <- a(x)
  z <- a(y)
} yield z

And then:

scala> first == second
res0: Boolean = false

This is your example rewritten to use for-comprehensions instead of flatMap directly (there are also some extra map operations at the end here, but that's an implementation detail and not really relevant).

As a side note, I'm not sure "is it safe?" is exactly the best way to phrase this question. If your for-comprehensions in ListT produce the correct result—and they definitely might, even though ListT's flatMap isn't associative—then in a sense they're "safe".

What lawfulness gives you is the ability to perform certain kinds of rewriting with confidence, and to be able to know at a glance that expressions have the same value (e.g. a(0).flatMap(a).flatMap(a) and a(0).flatMap(a(_).flatMap(a))), without having to look into the implementations of the methods they use. This is what you're missing because ListT doesn't have an associative flatMap. Whether that counts as "safe" or not is a judgment call you have to make.

Can monad with broken associativity law yield incorrect result in for-comprehension?

1 Answers1

Linked