Compilation error when declaring Functor for Either even after using type projections

Question

I am trying to write a Functor for Either for academic purposes in Scala. With help of higher-kinded types and type-projections, I managed to write an implementation for Either.

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

object Functor {
  implicit def eitherFunctor[A] = new Functor[({type λ[α] = Either[A, α]})#λ] {
    override def map[B, C](fa: Either[A, B])(f: B => C) = fa.map(f)
  }
}

def mapAll[F[_], A, B](fa: F[A])(f: A => B)(implicit fe: Functor[F]): F[B] = fe.map(fa)(f)

val right: Either[String, Int] =  Right(2)

mapAll(right)(_ + 2)

Now, the code above does not compile. I am not sure of the reason but the compilation error that I am getting is given below -

Error:(19, 16) type mismatch;
 found   : Either[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 Either[String,Int] to ?F[?A]
  mapAll(right)(_ + 2)

Can someone point what I am not doing right in the code above?

PS: Please do not suggest me to use kind-projector.

Answer 1

You've just been bitten by SI-2712. If you're using Scala >= 2.12.2 just add this line to your build.sbt:

scalacOptions += "-Ypartial-unification"

For other Scala versions you can use this plugin.

Answer 2

As others said, what the compiler is trying to tell you is that the shapes of your types don't match. When you require an F[_], you're requiring a type constructor with a single type parameter, which Either[A, B] doesn't satisfy.

What we need to do is apply a type lambda when applying mapAll, same as we did when we created the instance of the Either functor:

val right: Either[String, Int] = Right(2)

mapAll[({type λ[α]=Either[String, α]})#λ, Int, Int](right)(_ + 2)

We've now squeezed in String and fixed it as the first argument, allowing the type projected type to only need to satisfy our alpha, and now the shapes match.

Of course, we can also use a type alias which would free us from specifying any additional type information when applying mapAll:

type MyEither[A] = Either[String, A]
val right: MyEither[Int] = Right(2)

mapAll(right)(_ + 2)

Answer 3

Either[+A, +B] is expecting two type parameters(as @Ziyang Liu said), so for your example actually need BiFunctor not Functor, BiFunctor accept two functors and bound the two types.

there is a Bifunctor from Scalaz

trait Bifunctor[F[_, _]]  { self =>
  ////

  /** `map` over both type parameters. */
  def bimap[A, B, C, D](fab: F[A, B])(f: A => C, g: B => D): F[C, D]

So you can use this Bifunctor like:

Bifunctor[Either].bimap(Right(1): Either[String, Int])(_.toUpperCase, _ + 1).println

Hope it's helpful for you.