Use variance in optic type parameters

[julien-truffaut]

A Getter[A, B] is equivalent to A => B. So the variance of Getter should be the same as Function1, covariant in A, the input and contravariant in B, the output. If you are like me and have trouble putting your head around variance, you will find a great resource in Thinking with types.

trait Getter[-A, +B] {
  def get(from: A): B
}

On the other hand, a Lens[A, B] is equivalent to a pair of function (get: A => B, set: (A, B) => A). Both A and B appear in covariant and contravariant positions, which means Lens must be invariant in A and B.

trait Lens[A, B] extends Getter[A, B] { 
  // A is both an input and ouput of set
  def set(from: A, newValue: B): A 
}

All write optics are invariant, but it turns out that their polymorphic version is not. For example, a PolyLens[A1, A2, B1, B2] is a pair of function (get: A1 => B1, set: (A1, B2) => A2). Now, both A1 and B2 are in contravariant position and A2 and B1 are in covariant position.

trait PolyLens[-A1, +A2, +B1, -B2] extends Getter[A1, B1] { 
  def set(from: A1, newValue: B2): A2
}

Thank you, Adam Fraser and John De Goes for the idea. Also, thanks to Georgi Krastev for pointing out monomorphic Lens can inherit Getter with variance.

This issue is directly conflicting with removing polymorphic optics in #770.

So the question is, does variance in polymorphic optics brings enough benefits to compensate for their inconvenience?

EDIT: I removed the section where I said monomorphic Lens cannot inherit Fold with variance

[jdegoes]

@julien-truffaut Happy to help!

On miscellaneous other things I got too busy to respond to:

1. Sealed vs unsealed. If inheritance is going to be used at all — and I think it must be — then the sealed vs unsealed distinction doesn't really matter that much. After all, if you have a Fold you can always type case it to the most powerful variant, e.g. prism: Prism. Sealing them is a choice to make that explicit: e.g. saying even if you are passed something weaker, if you match against it, you might find something stronger. The only way to prevent that possibility is to avoid inheritance at all, because only then will you remove the possibility of type casing on the inheritance hierarchy.
2. Traversal. The solution that @adamgfraser and I sketched was not as powerful as a full traversal, although it can do many of the same things. If you want the full power, I suggest the simplest possible type class:

   trait Zippable[F[_]] {
     def succeed: F[Unit]
     def zipWith[A, B, C](fa: F[A], fb: F[B])(f: (A, B) => C): F[C]
   }

   Instances of this type class can be derived automatically in separate modules for any Cats or Scalaz Applicative.
   Alternately, you can imagine a traversal as a function from one optic to another optic.
3. The polymorphic optics in general infer quite well, and full polymorphism is necessary to have a sensible hierarchy. The one tricky detail is having a uniform and single compose operator for all optics, but we did prototype a solution (actually several) that can handle this requirement. The remaining type inference problems in things like field can probably also be solved, albeit at some cost to the library authors.

Overall this direction looks quite promising as an "incremental" adjustment to Monocle, one which removes unnecessary dependencies and starts to embrace the OOP side of Scala, not just the functional side of Scala.

Please drop us a line if you need an assistance pushing this forward!

[julien-truffaut]

I started some experiment in the variance branch, e.g. https://github.com/julien-truffaut/Monocle/tree/variance/core/shared/src/main/scala/monocle/poly

[joroKr21]

Minor correction - Getter[-A, +B] does not preclude invariant Lens[A, B] extends Getter[A, B] but I think it's better to keep polymorphic lenses anyway.

To me both Zippable and Applicative look simpler and more powerful than the PoC of Traversal in #752 so 👍 for that.

[julien-truffaut]

@joroKr21 good point, thanks for calling me bluff! I was so sure it wouldn't work that I didn't check.

By curiosity, why do you think it is better to keep polymorphic optics? Have you used them in their current form? Do you think variance will make them more usable?

Regarding Traversal encoding, there is a dedicated issue here #766

[joroKr21]

To be fair no, I only had practical use for monomorphic optics. But the polymorphic optics are more general whereas it feels that variance would indeed make them more useful and that there is a higher chance to solve the compose explosion. Perhaps comparing side by side a monomorphic vs polymorphic hierarchy would be most illuminating but that sounds like a lot of work.

[adamgfraser]

I spent some more time on this and I believe the below encoding inspired by @Odomontois's tofu-optics library would allow us to have one way to compose all optics, assuming we use sub-typing as discussed above. Basically, this takes advantage of the insight that when we compose two optics the composed optic always has the type of the "weaker" of the two optics. I think having one way to compose all optics, along with zero dependencies, is very important for getting broader adoption of optics.

If we do this, use declaration site variance, and use Zippable instead of Applicative as @jdegoes discussed above I think that gives a relatively clear path forward for 3.x that satisfies existing use cases while providing a host of new benefits.

object experiment {

  trait OpticCompose[Optic[S, T, A, B]] {
    def compose[S, T, A, B, C, D](left: Optic[S, T, A, B], right: Optic[A, B, C, D]): Optic[S, T, C, D]
  }

  object OpticCompose {

    implicit val lensCompose: OpticCompose[Lens] = ???

    implicit val optionalCompose: OpticCompose[Optional] = ???

    implicit val prismCompose: OpticCompose[Prism] = ???
  }

  final implicit class ComposeSyntax[Optic[S, T, A, B], S, T, A, B](private val self: Optic[S, T, A, B]) {
    def >>>[Optic1[S, T, A, B] >: Optic[S, T, A, B], C, D](
      that: Optic1[A, B, C, D]
    )(implicit ev: OpticCompose[Optic1]): Optic1[S, T, C, D] =
      ev.compose(self, that)
  }

  sealed trait Optional[-S, +T, +A, -B] {

    def headOption[A]: Optional[List[A], List[A], A, A] =
      Prism.cons >>> Lens.first
  }

  trait Lens[-S, +T, +A, -B] extends Optional[S, T, A, B]

  object Lens {

    def first[A, B, C]: Lens[(A, B), (C, B), A, C] = ???
  }

  trait Prism[-S, +T, +A, -B] extends Optional[S, T, A, B]

  object Prism {

    def cons[A, B]: Prism[List[A], List[B], (A, List[A]), (B, List[B])] = ???
  }
}

[julien-truffaut]

Thanks @adamgfraser, it is definitely worth investigating. Is the variance in optics type parameters help in your snippet? Or is it enough to have inheritance between optics?

It is still not clear to me where variance helps for optics type inference. It completely makes sense in ZIO (or fs2) but I believe it is because type parameters are independent of one another (they encode different things like DI and error). However, there is a strong connection between S, T, A, B in polymorphic optics.

[julien-truffaut]

I started playing with your proposal Adam and I got the following error:

[error]  found   : monocle.OpticAndThen[monocle.Lens]
[error]  required: monocle.OpticAndThen[[_, _]monocle.Lens[_, _]]
[error] Note: monocle.Lens <: [_, _]monocle.Lens[_, _], but trait OpticAndThen is invariant in type Optic.

It seems that's where variance in optics will help. I will give it a try in the variance branch.

[jdegoes]

@julien-truffaut Variance should not decrease type inference and could in some cases help; probably to achieve significant improvement (i.e. full inference in things like fields), it would be necessary to add even more type parameters (beyond STAB).

[julien-truffaut]

Variance does not decrease type inference, that's for sure. However, I am not convinced adding type parameters improve it. I would be happy to be proven wrong but so far, I haven't seen a single example of polymorphic optics having better type inference.

I tried to implement @adamgfraser proposal here but I am getting type inference issues when I try to compose a Lens with Prism.some, see example.

[jdegoes]

I haven't seen a single example of polymorphic optics having better type inference.

Variance will not improve type inference for monomorphic optics, because they become invariant, but it should for polymorphic optics; although it does give you the ability to relate optics (e.g. optic 1 is a subtype of optic 2), which could be useful.

What Adam and I found was "polymorphic optics" were insufficiently polymorphic to permit full inference. But if you don't like 4 type parameters, you will definitely NOT like the alternative. 😆

[julien-truffaut]

but it should for polymorphic optics

@jdegoes that's exactly what I am talking about. So far I haven't seen an example of better type inference when adding type parameters.

More type parameters make the code more difficult to read, so I believe it should bring some benefits in order to compensate for the additional complexity. I know you have similar opinions.

[joroKr21]

This issue is quite annoying here: scala/bug#11789

[Odomontois]

I should add that optics variance is irrelevant to composition unification.
But the subtyping hierarchy is essential.