Why can find `Functor` instance for Tree but not for Branch or Leaf?

Question

I have the following Functor definition:

import cats.Functor
import cats.syntax.functor._

object Theory {

  implicit val treeFunctor: Functor[Tree] =
    new Functor[Tree] {
      def map[A, B](fa: Tree[A])(f: A => B): Tree[B] =
        fa match {
          case Branch(left, right) =>
            Branch(map(left)(f), map(right)(f))
          case Leaf(value) =>
            Leaf(f(value))
        }
    }

  def main(args: Array[String]): Unit = {
    Branch(Leaf(10), Leaf(20)).map(_ * 2)
  }


}

for:

sealed trait Tree[+A]

final case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]

final case class Leaf[A](value: A) extends Tree[A]

Why the compiler complains:

// <console>:42: error: value map is not a member of wrapper.Branch[
Int]
//
Branch(Leaf(10), Leaf(20)).map(_ * 2)
//

So I have to create a smart constructor:

object Tree {
  def branch[A](left: Tree[A], right: Tree[A]): Tree[A] =
    Branch(left, right)
  def leaf[A](value: A): Tree[A] =
    Leaf(value)
}

What is a smart constructor in this case?

Use defined functor for `Tree` not for `Branch` – Sergii Lagutin Jan 31 '18 at 15:07 — Sergii Lagutin, Jan 31 '18 at 15:07

score 3 · Accepted Answer · answered Jan 31 '18 at 15:13

The declaration of Functor[F[_]] in cats is invariant in F. Therefore, a Functor[Tree] is neither a generalization, nor a specialization of Functor[Branch]. These types are unrelated.

The problem with your code is the following. The expression

Branch(Leaf(10), Leaf(20))

is of type Branch[Int]. When you try to apply .map[X] to it directly, you signal that you would like to get a Branch[X] as the result. But there is no Functor[Branch] in scope (it's not like you couldn't write one, but as it stands, there is none).

In order to make use of the Functor[Tree], you have to make it clear to the compiler that you want to treat this instance as Tree[Int]. Casting would work. Or using a custom factory method that hides Branch and exposes Tree would work too: that's what the "smart" constructor is doing.

I'll just add that `Functor[F[_]]` is invariant in `F` not just in `cats`, it's simply invariant in `F`. https://stackoverflow.com/questions/47181109/calling-generic-function-with-functor-using-subclass-cats-scalaz — Dmytro Mitin, Feb 03 '18 at 15:25
@DmytroMitin Hmm... *thinking*: It takes `F[A], A => B`, returns `F[B]`... takes `F`, returns `F`... */thinking* Oh yes, indeed! You're absolutely right! I think there was some discussion about whether `F[+_]` could be made covariant, but this is also not the case. So, yes, remark accepted. Thank you! — Andrey Tyukin, Feb 03 '18 at 15:33

Dmytro Mitin · Answer 2 · 2018-02-03T15:46:41.397

You can use kittens and implement instances for Branch and Leaf, then the instance for Tree can be derived.

libraryDependencies += "org.typelevel" %% "kittens" % "1.0.0-RC2"

  import cats.Functor
  import cats.syntax.functor._

  sealed trait Tree[+A]
  final case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]
  final case class Leaf[A](value: A) extends Tree[A]

  implicit val treeFunctor: Functor[Tree] = cats.derive.functor[Tree]

  implicit val branchFunctor: Functor[Branch] =
    new Functor[Branch] {
      def map[A, B](fa: Branch[A])(f: A => B): Branch[B] =
        fa match {
          case Branch(left, right) =>
            Branch(left.map(f), right.map(f))
        }
    }

    // or without extension method
//  implicit def branchFunctor(implicit treeFunctor: Functor[Tree]): Functor[Branch] =
//    new Functor[Branch] {
//      def map[A, B](fa: Branch[A])(f: A => B): Branch[B] =
//        fa match {
//          case Branch(left, right) =>
//            Branch(treeFunctor.map(left)(f), treeFunctor.map(right)(f))
//        }
//    }

  implicit val leafFunctor: Functor[Leaf] =
    new Functor[Leaf] {
      def map[A, B](fa: Leaf[A])(f: A => B): Leaf[B] =
        fa match {
          case Leaf(value) =>
            Leaf(f(value))
        }
    }

  def main(args: Array[String]): Unit = {
    (Branch(Leaf(10), Leaf(20)): Tree[Int]).map(_ * 2)
    Branch(Leaf(10), Leaf(20)).map(_ * 2)
    Leaf(10).map(_ * 2)
  }

Actually then you can derive all three instances:

  implicit val treeFunctor: Functor[Tree] = cats.derive.functor[Tree]
  implicit val leafFunctor: Functor[Leaf] = cats.derive.functor[Leaf]
  implicit val branchFunctor: Functor[Branch] = cats.derive.functor[Branch]

  def main(args: Array[String]): Unit = {
    (Branch(Leaf(10), Leaf(20)): Tree[Int]).map(_ * 2)
    Branch(Leaf(10), Leaf(20)).map(_ * 2)
    Leaf(10).map(_ * 2)
  }

Why can find `Functor` instance for Tree but not for Branch or Leaf?

2 Answers2

Linked