Repository navigation
Typeclass instances for ZipLazyList and ZipStream seem to be unlawful #4830
Description
Activity
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 haveGen[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.
You are correct. The reason is that
purefor lazy list and stream are infinite:def pure[A](x: A): ZipLazyList[A] = new ZipLazyList(LazyList.continually(x))
The other collections cannot define
Applicativebecause they can't be infinite.Ok, now I got it, thank you.
I tried anEq[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:
and then here:
cats/laws/src/main/scala/cats/laws/NonEmptyAlternativeLaws.scala
Lines 34 to 35 in a69b592
And it is not related to infinite values – the law fails even when
fa,ffandfgall have size 1.Looking at the implementation of
apandcombineKforZipLazyList, I'm not sure if it really can be achieved.
If we assume thatapis defined correctly, then I guess there's something wrong withcombineKforZipLazyList.Thoughts?
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
apwhich is zipping.Reacted by Sergey TorgashovSo I think you could define a zipping semigroup (when the element forms a semigroup) but not a generic
SemigroupKWe obtain a
Semigroupinstance with this method:
which in its current form doesn't allow to provide
Semigroupfor elements.So I guess what it implies is that
ZipLazyListcannot beAlternative. But it can beCommutativeApplicativeandSemigroup(which can be provided as a separate instance).I wonder if it is possible to strip
AlternativefromZipLazyListwithout breaking source compatibility.Reacted by Georgi KrastevNo, of course source compatibility will be broken. We can keep binary compatibility by making it non-implicit and deprecating it.
Reacted by Luka JacobowitzParallel 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.
Reacted by Sergey TorgashovAlso, there's another curious dicsussion in #3777. It looks like
Parallelcan 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
Parallelparadigm should be significantly revisited.
There are
AlternativeandCommutativeApplicativeinstances for bothZipLazyListandZipStream:Details
cats/core/src/main/scala-2.13+/cats/data/ZipLazyList.scala
Line 31 in a69b592
cats/core/src/main/scala-2.12/cats/data/ZipStream.scala
Line 31 in a69b592
cats/core/src/main/scala-2.13+/cats/data/ZipStream.scala
Line 33 in a69b592
However, the corresponding laws have never been verified. The existing tests for both
ZipLazyListandZipStreamcheck laws only up toCommutativeApply, with the following comment:Details
cats/tests/shared/src/test/scala-2.13+/cats/tests/LazyListSuite.scala
Lines 71 to 72 in a69b592
cats/tests/shared/src/test/scala/cats/tests/StreamSuite.scala
Lines 57 to 58 in a69b592
Moreover,
ZipList,ZipVector,ZipSeq, as well as their*NonEmpty*counterparts, define instances only up toCommutativeApply.Taken together, this strongly suggests that
ZipLazyListandZipStreamcannot lawfully provide anything stronger thanCommutativeApply.Perhaps the
AlternativeandCommutativeApplicativeinstances forZipLazyListandZipStreamshould be moved to alleycats-core, while cats-core should retain onlyCommutativeApply.