违反关联性法则的monad会产生不正确的理解力吗? [英] Can monad with broken associativity law yield incorrect result in for-comprehension?

问题描述

这是ListT的Monad实例(从 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] = ???
}

它确实不满足

因为，尽管我们获得了相同的值，但它们的顺序却不同

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-理解是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额外的操作，但这只是实现细节，并不真正相关).

作为旁注，我不确定是否安全?"正是表达这个问题的最佳方法.如果您在ListT中的for理解产生了正确的结果—即使ListT的flatMap不具有关联性，它们也肯定会产生正确的结果–那么从某种意义上说它们是安全的". >

合法性为您带来自信地执行某些类型的重写的能力，并且一眼就能知道表达式具有相同的值(例如a(0).flatMap(a).flatMap(a)和a(0).flatMap(a(_).flatMap(a)))，而不必考虑他们使用的方法的实现.这是您所缺少的，因为ListT没有关联的flatMap.判断是否安全"是您必须做出的判断.

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?

解决方案

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.

这篇关于违反关联性法则的monad会产生不正确的理解力吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！