Define laws for Traversable

[sideeffffect]

Difficulty: Advanced, requires familiarity with the concept of algebraic laws and testing them

Traversable currently doesn't have any laws (only inherits those from Covariant). Figure out which laws should ZIO Prelude's Traversable abide. Then write those tests down in Traversable.laws. Add tests for the missing instances in TraversableSpec (tests for some basic instances, like Option or List are already present).

As an inspiration, have a look Cats or ScalaZ or Haskell Travers/able and their laws:

https://github.com/typelevel/cats/blob/master/laws/src/main/scala/cats/laws/TraverseLaws.scala#L9 https://github.com/scalaz/scalaz/blob/master/core/src/main/scala/scalaz/Traverse.scala#L162 https://hackage.haskell.org/package/base-4.14.0.0/docs/Data-Traversable.html#t:Traversable

[zalbia]

I'd like to take this.

[zalbia]

I'm hitting a roadblock writing the naturality law for Traversable. Looking at the implementation of the laws in Cats & ScalaZ, it looks like we need to have an implementation of natural transformation. Do we need to implement it in zio-prelude to write this law or am I missing something?

[sideeffffect]

I'm no category theorist, so please excuse me if I say something nonsensical.

Natural transformations are morphisms between functors, right? In that case we don't have them in ZIO Prelude (yet :wink:).

But let me ask "from the other side". Are we able to write some interesting laws/properties for Traversable with the current state of things? If yes, could you please open a PR with that? We'll figure something out about naturality in the meantime :+1:

[Badmoonz]

@zach-albia I think we don't need so Generic approach for generating Applicatives used by foreach as you do testing for several hardcoded instances is sufficient, even using only Id Applicative is enough imho

[zalbia]

@zach-albia I think we don't need so Generic approach for generating Applicatives used by foreach as you do testing for several hardcoded instances is sufficient, even using only Id Applicative is enough imho

@Badmoonz your commit was super helpful in making the PR run in Dotty. Thanks!

[Badmoonz]

@zach-albia

I think it will be nice to add some tests to check that laws are really working:

        {
          implicit val badTraversable = new Traversable[Option] {
            // breaks Traversable Identity law
            override def foreach[G[+_]: IdentityBoth: Covariant, A, B](fa: Option[A])(f: A => G[B]): G[Option[B]] =
              (None: Option[B]).succeed
            override def map[A, B](f: A => B): Option[A] => Option[B] = _.map(f)
          }

          testM("Traversable.Identity law violation captured")(checkAllLaws(Traversable)(GenF.option, Gen.anyInt).map(x => assert(x.isFailure)(Assertion.isTrue)))
        },
        {
          implicit val badTraversable = new Traversable[Option] {
            override def foreach[G[+_]: IdentityBoth: Covariant, A, B](fa: Option[A])(f: A => G[B]): G[Option[B]] = fa match {
              case Some(x) => f(x).map(Some(_): Option[B])
              case None    => (None: Option[B]).succeed
            }

            // breaks Covariant Identity law
            override def map[A, B](f: A => B): Option[A] => Option[B] = _ => None

          }
          testM("Covariant.Identity law violation captured")(checkAllLaws(Traversable)(GenF.option, Gen.anyInt).map(x => assert(x.isFailure)(Assertion.isTrue)))
        }

still cannot imagine such traversable instance that has valid Identity laws and broken Composition laws 🤔

[sideeffffect]

So we now have 2 PRs implementing this https://github.com/zio/zio-prelude/pull/442 has

• identity
• sequentialFusion
• purity
• naturality
• parallelFusion

https://github.com/zio/zio-prelude/pull/449 has

• identity
• composition (for some predefined functors)

So how do we do this guys? Do you @zach-albia and @Badmoonz coordinate with each other to create one PR? Or should we merge first one and then the other? In what order? /cc @adamgfraser

[zalbia]

@sideeffffect I integrated a lot of the code from #449 into #442. I think you can merge his first once #449 runs in 2.11, and then you can take a look at mine? I think mine needs some more review TBH.

[Badmoonz]

@sideeffffect

I don't want to reject all the job @zach-albia has done introducing new laws

But if we want to keep things simple and valuable, really enough set of traversable laws would be

1. check that map and foreach commute (traversable instance may override map for perfomance issues)

   forall ta, f : ta.map(f) = Id.unwrap(ta.foreach[Id, A, B]((a: A) => Id(f(a)))

2. Check already defined Covariant.laws

That's all we need!!! It's ever lesser law set than #449

sequentialFusion,purity,naturality,parallelFusion laws within Identity Applicative can be proved by Covariant laws , so they probably don't validate any bad case

I think we should introduce new laws in terms of existing such instances that work incorrectly but pass current laws

[sideeffffect]

If what @Badmoonz says is correct, than let's just have the one commutativity law. If all the other laws follow from that (+ the Covariant laws), then we don't need them and we should strive for minimalism in this regard IMHO. What do you guys think? /cc @adamgfraser @jdegoes

[adamgfraser]

Yes I think we don't need five laws. The formulation I have seen normally has two, an identity law that calling foreach with the identity function returns the value unchanged, which is basically consistency with map, and then a second that two traversals can be fused, though I am sure there are other minimal formulations of laws.

[sideeffffect]

For the record, here are papers discussing laws for Traversable:

• M. Jaskelioff and O. Rypacek. An investigation of the laws of traversals. 2012.
• Richard Bird, Jeremy Gibbons, Stefan Mehner, Janis Voigtländer and Tom Schrijvers. Understanding Idiomatic Traversals Backwards and Forwards. 2013.

Would somebody like to go forward and implement the identity law

forall ta, f : ta.map(f) = Id.unwrap(ta.foreach[Id, A, B]((a: A) => Id(f(a)))

?

[sideeffffect]

There have been some changes in the codebase, like renaming Traversable to ForEach and others, so the PR(s) might be outdated. But our need for laws for ForEach (aka Traversable) hasn't disappeared :wink: Would some of you guys @Badmoonz or @zalbia or anybody else like to pick up the work on adding laws for this type class? (And there's also NonEmptyForEach, what laws should that get?)

[zalbia]

@sideeffffect I would love to have a go at it again as soon as I get the chance (which should be in a week or two). Will maintain @Badmoonz' insight on the minimum number of laws that need to be implemented.

[zalbia]

That said, if anyone reading this wants to take this instead before I get to chance to work on it, please go ahead.