Traversal encoding

[julien-truffaut]

In Monocle 1.x and 2.x, we implemented Traversal using the Van Laarhoven encoding, meaning all functions within Traversal are defined in terms of modifyF:

trait Traversal[A, B] {
  def modifyF[F[_]: Applicative](f: B => F[B])(from: A): F[A]
}

In 3.x, we are trying to keep the core module without external dependency, so the question is:

How can we implement Traversal without Applicative?

[julien-truffaut]

We could define our own Applicative in an internal module (i.e. public but marked as implementation details). Then, in the cats-interop module, we could define an automatic translation between cats Applicative and Monocle Applicative.

This is the worst possible case. I hope we find a better idea.

[nafg]

Why precisely does F need Applicative? If it intrinsically only makes sense if it is then you have to have some applicative to talk about. Why can't that be cats applicative?

If the problem is it annoys or has poor interop with Scalaz then maybe they need figure out how to factor out some basic things into a shared library.

[julien-truffaut]

@nafg Van Laarhoven encoding uses both pure and map2 from Applicative. However, it is not the only encoding. For example, profunctor optics use something called Wander (see purescript implementation).

We will offer a modifyF with exactly this signature in the cats-interop module. The question is can we encode Traversal without any typeclass from cats? We did something similar with Fold. Traditionally, it depends on Monoid but there are other encodings only using vanilla Scala.

[jdegoes]

The smallest / simplest possible type class that has the same expressive power as Applicative:

trait Zippable[F[_]] {
  def succeedUnit: F[Unit]
  def zipWith[A, B, C](l: F[A], r: F[B])(f: (A, B) => C): F[C]
}

One could derive Zippable in third-party modules for both Cats & Scalaz Applicative, as well as include instances of Zippable for collection data types inside Monocle.

One could also go two other directions:

First, recognize the features allowed by modifyF:

def modifyF[F[_]: Applicative](f: B => F[B])(from: A): F[A]

These include, principally, stateful modification, together with short-circuiting failures. For all intent and purpose, this means you can implement almost everything with a much simpler modify:

def modify[S, E](s: S)(f: (S, B) => (S, Either[E, B]))(from: A): (S, Either[E, A])

All combinators in Monocle and many other ones can be defined in terms of this one. Of course, one cannot use IO effects with this definition while traversing, but that's a bad idea anyway: mainly because it introduces race conditions in updating the state of the traverse (at the time you get the A back, arbitrary amount of time and other concurrent updates could have happened to the traverse structure).

Second, one could instead recognize a Traverse as being a type of lens on a collection (with rich out of the box integration with Scala collection types), but this lens would be augmented with additional methods for performing operations on the elements of the collection, as well as further composing optics with the element type. This is the most "Scala idiomatic" solution and results in the simplest / most friendly API (it also does not prelude users from doing the same for their own non-collection types, like trees).

[joroKr21]

You could also use a collection as F[_] to return variants of modifications. Or perhaps a generator for testing. Zippable looks better to me.

[neko-kai]

@julien-truffaut You could define your own Applicative typeclass and then define Optional Instances in the companion object to convert cats and scalaz classes into yours.

See encoding of DIEffect: https://github.com/7mind/izumi/blob/ea72bbb3239b1727a9d0f8993325061fd17873a5/distage/distage-core-api/src/main/scala/izumi/distage/model/effect/DIEffect.scala#L131 , distage and logstage libraries do not depend on ZIO or cats-core, but they automatically support these effect types if the dependency is present on the classpath