scala - 结合律被破坏的单子(monad)会在理解中产生不正确的结果吗？

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

确实如此 not满足 associativity单子(monad)法则

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

然而，它似乎在理解中正常工作(在我的个人项目中)。一般来说，在理解中使用阻止关联律的“单子(monad)”是否安全？你能提供一个反例来证明不正确的结果吗？

Answer 1

由于for - 理解是 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 的示例-理解而不是 flatMap直接(这里最后还有一些额外的 map 操作，但这是一个实现细节，并不真正相关)。

作为旁注，我不确定“它安全吗？”正是表达这个问题的最佳方式。如果您的 for -在 ListT 中的理解产生正确的结果——他们肯定会，即使 ListT的 flatMap不是关联的——那么从某种意义上说，它们是“安全的”。

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