Proper implementation for a 2 type parameters Functor in Scala

Question

I saw this question several times on SO, but no matter how hard I try, I can't make the following code compile. The goal is to implement an Functor implementation for a simpler Reader (the code is here):

  trait Functor[F[_]] {
    def fmap[A, B](fa: F[A])(f: A => B): F[B]
  }

  implicit class FunctorOps[F[_]: Functor, A](self: F[A]) {
    def fmap[B](f: A => B): F[B] = implicitly[Functor[F]].fmap(self)(f)
  }

  case class Reader[A, B](run: A => B)
  type ReaderF[X] = ({ type L[A] = Reader[X, A] })

  implicit def readerFunctors[E]: Functor[ReaderF[E]#L] = 
    new Functor[ReaderF[E]#L] {
       override def fmap[A, B](fa: Reader[E, A])(f: A => B): Reader[E, B] = 
          Reader(e => f(fa.run(e)))
    }

  val foo = Reader[String, Int](_ => 42)

  foo.fmap(_ + 1) // does not compile

I tried to bypass the implicit mechanism with the following:

FunctorOps(foo).fmap(_ + 1)

but this outputs the following compilation error:

Error:(82, 23) type mismatch;
 found   : com.fp.Scratchpad.Reader[String,Int]
 required: ?F[?A]
Note that implicit conversions are not applicable because they are ambiguous:
 both method ArrowAssoc in object Predef of type [A](self: A)ArrowAssoc[A]
 and method Ensuring in object Predef of type [A](self: A)Ensuring[A]
 are possible conversion functions from com.fp.Scratchpad.Reader[String,Int] to ?F[?A]
  FunctorOps(foo).fmap(_ + 1)

Thank you in advance for your help.

UPDATE

Just to make sure my FunctorOps is right, I created a functor instance for Id:

case class Id[A](value: A)
implicit val idF: Functor[Id] = new Functor[Id] {
  override def fmap[A, B](fa: Id[A])(f: A => B): Id[B] = Id(f(fa.value))
}

val id = Id(42)
id.fmap(_ + 1) // compiles

So the problem does not come from the FunctorOps implicit class. I suspect Scala to have a real hard time with type lambdas...

UPDATE 2

I tried to simplify the problem but without success:

  trait Functor[F[_]] {
    def map[A, B](x: F[A])(f: A => B): F[B]
  }

  implicit class Ops[F[_], A](fa: F[A])(implicit F: Functor[F]) {
    def map[B](f: A => B): F[B] = F.map(fa)(f)
  }

  type FF[A] = ({ type F[B] = A => B })

  implicit def ff[E]: Functor[FF[E]#F] = new Functor[FF[E]#F] {
    override def map[A, B](x: E => A)(f: A => B): E => B = e => f(x(e))
  }

  val f: String => Int = _ => 42

  val value: Functor[FF[String]#F] = ff[String]
  val ops = new Ops[FF[String]#F, Int](f)(value)

  // These compile
  ops.map(_ + 1)("")
  value.map(f)(_ + 1)("")

  // This not
  f.map(_ + 1)

What is your Scala version? The first one compiles in scastie.scala-lang.org/gpRKdKjNS4KLTAq7Zwptsw. I was actually surprised it seems to work in older versions too, I assumed you need 2.12 or 2.11.11+. — Alexey Romanov
I've just checked and Scala version is 2.12.8. Tried to compile with IDEA and sbt :( — Francis Toth

mdm mdm · Accepted Answer · 2019-03-28T10:40:11

UPDATE:
I think that, to have this working, you need to enable some extra options for the compiler in build.sbt:

scalacOptions ++= Seq(
      "-Ypartial-unification",
      "-language:postfixOps",
      "-language:higherKinds",
      "-deprecation",
      "-encoding", "UTF-8",
      "-feature",      
      "-unchecked"
    )

More info on the partial unification flag and what it solves can be found here.

ORIGINAL ANSWER: Are you running your code through Worksheet or a Scratch in IDEA? I have noticed that sometimes, especially in these kind of functional programming tasks where there is type inference, implicit resolution and higher kinded type "magic", IDEA's REPLs are not up to the task (but I am not sure why).

This said, I tried to run the following on IDEA:

object TestApp extends App{
  trait Functor[F[_]] {
    def fmap[A, B](fa: F[A])(f: A => B): F[B]
  }

  implicit class FunctorOps[F[_]: Functor, A](self: F[A]) {
    def fmap[B](f: A => B): F[B] = implicitly[Functor[F]].fmap(self)(f)
  }

  case class Reader[A, B](run: A => B)
  type ReaderF[X] = ({ type L[A] = Reader[X, A] })

  implicit def readerFunctors[E]: Functor[ReaderF[E]#L] =
    new Functor[ReaderF[E]#L] {
      override def fmap[A, B](fa: Reader[E, A])(f: A => B): Reader[E, B] =
        Reader(e => f(fa.run(e)))
    }

  val foo: Reader[String, Int] = Reader[String, Int](s => s.length)

  val i = foo.fmap(_ + 1)

  println(i.run("Test"))
  println(i.run("Hello World"))
}

And it works fine, printing 5 and 12. Also, as someone else mentioned, your code works on Scastie, which is another syntom of IDEA's acting up.

One final note: you probably already know this, but you can avoid all that type-lambda ugliness using the kind-projector compiler plugin.

Long story short, drop the ReaderF[X] type alias, and make your functor instance look like this:

implicit def readerFunctors[X]: Functor[Reader[X,?]] =
    new Functor[Reader[X,?]] {
      override def fmap[B, C](fa: Reader[X,B])(f: B => C): Reader[X,C] =
        Reader(e => f(fa.run(e)))
    }

Which is more readable IMHO.

Proper implementation for a 2 type parameters Functor in Scala

1 Answers