Может ли монада с нарушенным законом ассоциативности дать неверный результат для понимания?

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

Однако, похоже, он работает правильно для-понимания (в моем личном проекте ). Вообще, безопасно ли использовать «монады», которые нарушают закон ассоциативности для понимания? Не могли бы вы привести контрпример, показывающий неверный результат?

Answer 1

Поскольку for -компостирования являются синтактическими c сахаром для 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 s flatMap не ассоциативны - тогда в некотором смысле они "безопасны".

То, что дает вам законность, - это способность уверенно выполнять определенные виды переписывания и возможность сразу увидеть, что выражения имеют одинаковое значение (например, a(0).flatMap(a).flatMap(a) и a(0).flatMap(a(_).flatMap(a))), без необходимости заглядывать в реализации методов, которые они используют. Это то, что вам не хватает, потому что ListT не имеет ассоциативного flatMap. Независимо от того, считается ли это «безопасным» или нет, вам нужно сделать суждение.