Typeclass instances for `ZipLazyList` and `ZipStream` seem to be unlawful

[satorg]

There are Alternative and CommutativeApplicative instances for both ZipLazyList and ZipStream:

Details

cats/core/src/main/scala-2.13+/cats/data/ZipLazyList.scala

Line 31 in a69b592

implicit val catsDataAlternativeForZipLazyList: Alternative[ZipLazyList] & CommutativeApplicative[ZipLazyList] =

cats/core/src/main/scala-2.12/cats/data/ZipStream.scala

Line 31 in a69b592

implicit val catsDataAlternativeForZipStream: Alternative[ZipStream] with CommutativeApplicative[ZipStream] =

cats/core/src/main/scala-2.13+/cats/data/ZipStream.scala

Line 33 in a69b592

implicit val catsDataAlternativeForZipStream: Alternative[ZipStream] & CommutativeApplicative[ZipStream] =

However, the corresponding laws have never been verified. The existing tests for both ZipLazyList and ZipStream check laws only up to CommutativeApply, with the following comment:

Can't test applicative laws as they don't terminate

Details

cats/tests/shared/src/test/scala-2.13+/cats/tests/LazyListSuite.scala

Lines 71 to 72 in a69b592

	// Can't test applicative laws as they don't terminate
	checkAll("ZipLazyList[Int]", CommutativeApplyTests[ZipLazyList].apply[Int, Int, Int])

cats/tests/shared/src/test/scala/cats/tests/StreamSuite.scala

Lines 57 to 58 in a69b592

	// Can't test applicative laws as they don't terminate
	checkAll("ZipStream[Int]", CommutativeApplyTests[ZipStream].apply[Int, Int, Int])

Moreover, ZipList, ZipVector, ZipSeq, as well as their *NonEmpty* counterparts, define instances only up to CommutativeApply.

Taken together, this strongly suggests that ZipLazyList and ZipStream cannot lawfully provide anything stronger than CommutativeApply.

Perhaps the Alternative and CommutativeApplicative instances for ZipLazyList and ZipStream should be moved to alleycats-core, while cats-core should retain only CommutativeApply.

[satorg]

@johnynek , wdyt?

[johnynek]

I don't know why they don't terminate, but I think it could be that some methods in alternative would generate infinite streams for some of these values.

Since they are infinite, we can't use a naive way to check equality of the streams, but they may be equivalent, so not exactly unlawful.

An alternative way to check this may be this:

Instead of using Eq[LazyList[A]] we could have Gen[Eq[LazyList[A]] which does:

Gen.biasedSmallInt.flatMap { takeSize =>
  new Eq[LazyList[A]] {
    def eqv(a: LazyList[A], b: LazyList[A]) =
      a.iterator.take(takeSize).zip(b.iterator.take(takeSize)).forall { case (a, b) => Eq[A].eqv(a, b) }
  }
}

If the law passes:

forall(genEq) { eq =>

 }

Then it is true. The catch is, we would have to tune biasedSmallInt such that it could return a very large value (close to MaxInt), but it usually returns a smaller one (something like an geometric distribution or something tuned with the appropriate mean).

This could work.

[joroKr21]

You are correct. The reason is that pure for lazy list and stream are infinite:

def pure[A](x: A): ZipLazyList[A] = new ZipLazyList(LazyList.continually(x))

The other collections cannot define Applicative because they can't be infinite.

[satorg]

Ok, now I got it, thank you.
I tried an Eq[ZipLazyList[A]] version with a length limit:

implicit def customZipLazyListEq[A: Eq]: Eq[ZipLazyList[A]] = Eq.by(_.value.take(100_000))

For the sake of smoke testing, the length was hardcoded to some big yet finite number.

It works out for CommutativeApplicativeTests – all the checks pass indeed:

checkAll("ZipLazyList", CommutativeApplicativeTests[ZipLazyList].commutativeApplicative[Int, Int, Int])

However, AlternativeTests[ZipLazyList] still fail on "right distributivity":

checkAll("ZipLazyList", AlternativeTests[ZipLazyList].alternative[Int, Int, Int])

which is defined here:

cats/laws/src/main/scala/cats/laws/discipline/NonEmptyAlternativeTests.scala

Line 54 in a69b592

"right distributivity" -> forAll(laws.nonEmptyAlternativeRightDistributivity[A, B] _),

and then here:

cats/laws/src/main/scala/cats/laws/NonEmptyAlternativeLaws.scala

Lines 34 to 35 in a69b592

	def nonEmptyAlternativeRightDistributivity[A, B](fa: F[A], ff: F[A => B], fg: F[A => B]): IsEq[F[B]] =
	((ff |+| fg).ap(fa)) <-> ((ff.ap(fa)) |+| (fg.ap(fa)))

And it is not related to infinite values – the law fails even when fa, ff and fg all have size 1.

Looking at the implementation of ap and combineK for ZipLazyList, I'm not sure if it really can be achieved.
If we assume that ap is defined correctly, then I guess there's something wrong with combineK for ZipLazyList.

Thoughts?

[joroKr21]

Nice catch - yeah it doesn't make sense because it's forwarding to the non-zip instance:

      def combineK[A](x: ZipLazyList[A], y: ZipLazyList[A]): ZipLazyList[A] =
        ZipLazyList(cats.instances.lazyList.catsStdInstancesForLazyList.combineK(x.value, y.value))

But of course that's wrong - it's doing concatenation here, not zipping so that changes the length of the list (when finite) and breaks ap which is zipping.

[joroKr21]

So I think you could define a zipping semigroup (when the element forms a semigroup) but not a generic SemigroupK

[satorg]

We obtain a Semigroup instance with this method:

cats/core/src/main/scala/cats/SemigroupK.scala

Line 97 in a69b592

def algebra[A]: Semigroup[F[A]] = combineK(_, _)

which in its current form doesn't allow to provide Semigroup for elements.

[satorg]

So I guess what it implies is that ZipLazyList cannot be Alternative. But it can be CommutativeApplicative and Semigroup (which can be provided as a separate instance).

I wonder if it is possible to strip Alternative from ZipLazyList without breaking source compatibility.

[joroKr21]

No, of course source compatibility will be broken. We can keep binary compatibility by making it non-implicit and deprecating it.

[satorg]

Found this very old issue that seems to be related to this one: #3082

[johnynek]

Parallel has always been rather adhoc. Why are any of the laws what they are? Why is the Applicative map2 allowed to be different but not the pure? Not very clear.

[satorg]

Also, there's another curious dicsussion in #3777. It looks like Parallel can imply either fail-fast or fail-last (error-accumulating) strategy, and currently it is up to the implementation which one is actually implied.

I feel that if Typelevel ever considers a new major Cats version, then the whole Parallel paradigm should be significantly revisited.