结合律被破坏的 monad 会在 for-comprehension 中产生不正确的结果吗？

Question

这是 ListT 的 Monad 实例（从复制）

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] = ???
}

它符合 not satisfy associativity 单子法则

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（和 map）的句法糖分，所以损坏的 flatMap 肯定会导致不正确的 for-理解码。例如：

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 操作，但这是一个实现细节和不太相关）。

顺便说一下，我不确定 "is it safe?" 是否是表达这个问题的最佳方式。如果你在 ListT 中的 for 推导产生了正确的结果——而且它们肯定有可能，即使 ListT 的 flatMap 不是关联的——那么在某种意义上它们'重新 "safe".

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

结合律被破坏的 monad 会在 for-comprehension 中产生不正确的结果吗？

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

scala

monads

for-comprehension

associativity