Generalize polymorphic functions to arbitrary polymorphic values

[TomasMikula]

Would it be feasible to extend this approach to arbitrary polymorphic values? Essentially, providing syntax for scalaz.Forall:

/** A universally quantified value */
trait Forall[P[_]] {
  def apply[A]: P[A]
}

The polymorphic function is then just a special case:

type NaturalTransformation[F[_], G[_]] = Forall[λ[A => (F[A] => G[A])]]

The syntax could be

val f = ∀[λ[A => (List[A] => Option[A])]](_.headOption)

or in general

val f = ∀[F](<expr>)

where

• F[_] is a unary type constructor;
• <expr> is an expression of type Function0[F[_]].

The resulting type of f is then Forall[F].

One benefit of this is that you don't need special named traits for polymorphic functions anymore (there is scalaz.~> and cats.FunctionK, which are basically the same, but incompatible—one needs conversions between them).

The main benefit, however, is that we would have syntax for other polymorphic values, like

∀[λ[A => Lens[F[A], G[A]]]]

Then given

trait Lens[S, A] {
  def get(s: S): A
  def set(s: S, a: A): S
}
object Lens {
  def apply[S, A](get: S => A, set: (S, A) => S): Lens[S, A] = ???
}

we could define a polymorphic lens

val fstLens = ∀[λ[A => Lens[(A, Int), Id[A]]]](Lens(_._1, (ai, a) => (a, ai._2)))

where fstLens has type Forall[λ[A => Lens[(A, Int), Id[A]]]]. This would then be used like this

val x = ("Hello", 5)
fstLens[String].get(x) // "Hello"
fstLens[String].set(x, "Bye") // ("Bye", 5)

[non]

This looks really compelling.

I'm reluctant to remove the support for polymorphic lambdas (even though it's a special case of this) just because of how often they show up. But I'm definitely open to adding this. Let's think about it.

[TomasMikula]

Strictly speaking, Forall[F] (for some F[_]) can be made a special case of polymorphic lambdas: it is isomorphic to Const[Unit, ?] ~> F; but that is quite cumbersome.

[non]

@julien-truffaut Would something like ∀ (ForAll) be useful to you?

[TomasMikula]

As far as I know, Monocle doesn't have KLens (or would it be LensK?). So my question to @julien-truffaut is rather, have users been asking for one?

[julien-truffaut]

At the moment polymorphic Lens or Optic are encoded using 4 type parameters like PLens[S, T, A, B]. To follow your example, fstLens would have the following signature:
def fstLens[A, B, C]: PLens[(A, B), (C, B), A, C]

As far as I can see, KLens seems to be a special case of PLens but it might offer a better type inference. So I think we will need to experiment in order to see pros and cons.

[TomasMikula]

def fstLens[A, B, C]: PLens[(A, B), (C, B), A, C]

The problem here is how to turn this def into a val, given that B is some concrete type (e.g. Int) and let's assume C =:= A. The goal is to obtain a (P)Lens that works for all A. The problem with def fstLens is that you cannot pass a def around as a value.

[TomasMikula]

Perhaps let's look at a simpler example than KLens. Let's see how ForAll subsumes MonoidK.

The following method is taken from cats.kernel:

def catsKernelStdMonoidForList[A]: Monoid[List[A]]

Then there is a separate type cats.MonoidK. Using ForAll, MonoidK[F] is "just" ∀[λ[A => Monoid[F[A]]]].

val listMonoidK = ∀[λ[A => Monoid[List[A]]]](catsKernelStdMonoidForList[_])

Or, using an ad hoc type alias:

type ListMonoid[A] = Monoid[List[A]]

val listMonoidK = ∀[ListMonoid](catsKernelStdMonoidForList[_])

We used an existing polymorphic method (catsKernelStdMonoidForList) to obtain an equivalent of MonoidK[List], without having to define a trait for MonoidK.

[adelbertc]

This would also be useful for, you guessed it, tagless final. The issue is we encode the algebra with something like:

trait Calc[F[_]] {
  def lit(n: Int): F[Int]
  def add(l: F[Int], r: F[Int]): F[Int]
}

But we can't have a polymorphic value constrained by Calc[F]. Instead we end up having to do something like:

trait CalcAlg[A] {
  def run[F[_]: Calc]: F[A]
}

// smart constructors

def lit(n: Int): CalcAlg[Int] = new CalcAlg[Int] {
  def run[F[_]: Calc]: F[Int] = implicitly[Calc[F]].lit(n)
}

def add(l: CalcAlg[Int], r: CalcAlg[Int]): CalcAlg[Int] = new CalcAlg[Int] {
  def run[F[_]: Calc]: F[Int] = implicitly[Calc[F]].add(l.run[F], r.run[F])
}

which gets tedious.

[TomasMikula]

@adelbertc IIUC, this would require two extensions to my original proposal:

1. Generalize ForAll for higher kinds (in your use case F[_]).
   This seems like a natural next thing to do.

2. Support for context bounds (F[_]: Calc).
   Not sure how this would work. The following would not even be valid syntax.

   def lit(n: Int) = ∀[(F[_]: Calc) => F[Int]] (implicitly[Calc[F]].lit(n))

I imagine there would have to be many variants of ForAll, with the kind of the type parameter and the number of context bounds mangled into the name, like ForAll_(*->*)_1 (ignore the fact that this is not a valid identifier 😉 ). This is getting pretty ugly, but would be nice to have, anyway.

[TomasMikula]

See #44.

[TomasMikula]

This functionality is now provided by P∀scal and can be kept separate from kind-projector.