结合律失效的 monad 能否在 for-comprehension 中产生不正确的结果？

Question

这是一个Monad实例ListT（从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] = ???
}

它并不能满足关联单子法

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")

因为，虽然我们得到相同的值，但它们的顺序不同

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

然而，它似乎在 for-comprehensions 中正常工作（在我的个人项目中）。一般来说，在 for-comprehensions 中使用制动结合律的“monads”是否安全？你能提供一个反例来证明错误的结果吗？

Answer 1

由于for-comprehensions 是flatMap(and map) 的语法糖，因此肯定flatMap会导致错误的for-comprehension 代码出现错误。例如：

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

进而：

scala> first == second
res0: Boolean = false

这是您重写的示例，以使用for-comprehensions 而不是flatMap直接使用（这里最后还有一些额外的map操作，但这是一个实现细节，并不真正相关）。

作为旁注，我不确定“它安全吗？” 正是表达这个问题的最佳方式。如果你的for-comprehensions inListT产生正确的结果——而且它们肯定会产生正确的结果，即使ListT'sflatMap不是关联的——那么在某种意义上它们是“安全的”。

合法性赋予您的是能够自信地执行某些类型的重写，并且能够一眼就知道表达式具有相同的值（例如a(0).flatMap(a).flatMap(a)和a(0).flatMap(a(_).flatMap(a))），而无需查看它们使用的方法的实现。这就是您所缺少的，因为ListT没有关联flatMap. 这是否算作“安全”是您必须做出的判断。