Add Functor.widen

[ceedubs]

I think that we should have something like def widen[A, AA >: A](fa: F[A]): F[AA] on (covariant) Functor. People who are working in code that is a hybrid of OO and FP (which is pretty much everyone who uses FP in scala, since subtyping is used for sum types) often find themselves wanting something like this.

A straightforward implementation is map identity, but this solution is often not very performant. Since the functor laws specify that fa map identity is equivalent to fa, there generally shouldn't be any problem with just using an asInstanceOf cast instead of mapping over identity. I think that The singleton instance trick is unsafe points out that there are ways that you can get unsound results with this approach in certain situations. I'm not sure how much of a real problem that is in practice.

[julienrf]

Out of curiosity, what are the arguments to not make Functor's type parameter covariant?

[edmundnoble]

I believe the "singleton instance trick is unsafe" article does not apply in this case. The reason for its unsafety is singleton type patterns, however I don't believe they are unsound in this case:

class F[+A] // (with implicit functor in scope)
class A
class B extends A
val f: F[B] = ???
val g: F[A] = f.widen
val g2: F[A] = f match {
  case _: g.type => f
}

As you can see, having widen is a function from F[B] to F[A]. Implementing widen as an unsafe cast of F[B] to F[A], we can then use a singleton type pattern to... unsafely cast an F[B] to an F[A]. Assuming F follows the functor laws, this is no less unsafe than using widen directly.

Edit: This hinges on the absence of functorial GADTs in cats which violate Liskov lifting.

[edmundnoble]

Also (sorry for the spam) I plan to tackle this with a PR later today.

[durban]

Well, technically it is possible to use this to perform an unsafe cast (tested with b149835):

package com.example

import cats.Functor
import cats.data.Const
import cats.std.int._

object Example extends App {

  type IntConst[A] = Const[Int, A]

  def unsafeCoerce[A, B]: (A => B) = {
    val n: IntConst[Nothing] = Const[Int, Nothing](0)
    val b: IntConst[B] = Functor[IntConst].widen[Nothing, B](n)
    Functor[IntConst].widen[Nothing, A](n) match {
      case _: b.type =>
        implicitly[A =:= B]
    }
  }

  val d: Double = unsafeCoerce[String, Double]("a")
  println(d)
}

This produces:

[error] (run-main-0) java.lang.ClassCastException: java.lang.String cannot be cast to java.lang.Double
java.lang.ClassCastException: java.lang.String cannot be cast to java.lang.Double
        at scala.runtime.BoxesRunTime.unboxToDouble(BoxesRunTime.java:114)
        at com.example.Example$.delayedEndpoint$com$example$Example$1(Example.scala:20)
        at com.example.Example$delayedInit$body.apply(Example.scala:7)
        at scala.Function0$class.apply$mcV$sp(Function0.scala:34)
        at scala.runtime.AbstractFunction0.apply$mcV$sp(AbstractFunction0.scala:12)
        at scala.App$$anonfun$main$1.apply(App.scala:76)
        at scala.App$$anonfun$main$1.apply(App.scala:76)
        at scala.collection.immutable.List.foreach(List.scala:381)
        at scala.collection.generic.TraversableForwarder$class.foreach(TraversableForwarder.scala:35)
        at scala.App$class.main(App.scala:76)
        at com.example.Example$.main(Example.scala:7)
        at com.example.Example.main(Example.scala)
        at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
        at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
        at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
        at java.lang.reflect.Method.invoke(Method.java:498)

[ceedubs]

@durban yeah, that does bother me a bit. I think it can only be a problem when reference equality is used (this is how case _: b.type works), which means breaking parametricity. It seems unlikely to me that this would be a problem in practice, as it seems like you kind of have to make a concerted effort to make this produce unsound results. For those reasons, and since it's likely to be much more efficient than map identity for many structures, I'm inclined to just put a warning in the scaladoc for the method. WDYT?

[durban]

@ceedubs Yeah, I guess a warning in scaladoc is the least bad thing to do. I agree, that in practice, this probably rarely causes a problem, and can appreciate the efficiency argument.

What really bothers me though is that the root cause (if I undestood correctly) is that we're lying to scalac: Const is in effect covariant (or, I guess in this case it's phantom-variant), but scalac doesn't know that, thus it makes inferences based on that it's invariant (since that is what we're telling when we say class Const[A, B] ...).

[ceedubs]

@durban I agree that it's unfortunate that Const is phantom-variant but that we have no way of representing this with Scala's support for variance. I think it would be arbitrary to mark it as either covariant or contravariant, so I'm not sure either of those make much sense.

I'm going to go ahead and close this out since #1208 was merged. But please feel free to continue this conversation.