value map is not a member of Branch[Int]

Question

I have following ADT:

import cats.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]

and do implementation in the functor:

implicit def treeFunctor = 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(v) => Leaf(f(v))
    }
}

and uses it as follow:

val b = Branch(left = Branch(Branch(Leaf(5), Leaf(3)), Leaf(10)), Leaf(45))
val functorTree = Functor[Tree].map(b)((v) => v * 4)

But following:

Branch(Leaf(10), Leaf(20)).map(_ * 2)

I've got the compiler error:

Error:(21, 29) value map is not a member of A$A90.this.Branch[Int]
Branch(Leaf(10), Leaf(20)).map(_ * 2)
                           ^

My question is why do I get the error?

Answer 1

Method treeFunctor gives you an instance of Functor[Tree] for any Tree, but that doesn't mean that any Tree is automatically converted to it. It's just that for any Tree, you have an implicit instance of Functor[Tree] in the scope.

This implicit instance has a method map which takes two parameters: instance of Functor[Tree] to map over, and the mapping function itself.

So this should work:

implicitly[Functor[Tree]].map(Branch(Leaf(10), Leaf(20)))(_ * 2)

or simply

Functor[Tree].map(Branch(Leaf(10), Leaf(20)))(_ * 2)

(since scalaz and cats usually have this convenience apply() for type classes)

EDIT: When reading your question, I missed the Functor[Tree].map(b)((v) => v * 4) part. So what you're actually interested in is the following part.

If you want to keep your syntax for invoking map, you can create an implicit class as a wrapper:

implicit class toTreeFunctor[A](tree: Tree[A]) {
  def map[B](f: A => B) = Functor[Tree].map(tree)(f)
}

Branch(Leaf(10), Leaf(20)).map(_ * 2)

As pointed out by @P. Frolov, you can get this implicit conversion for free from import scalaz.syntax.functor._ or import cats.syntax.functor._, but note that you have to explicitly upcast your Branch to be an instance of Tree.

Answer 2

Since you're using Cats, you can import cats.syntax.functor._ in order to get your map. Note that you need to convert branch into the base type, because Functor instance is defined for Tree, not just a separate Branch. You can use type annotation or smart constructors in companion object to do so.

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 def treeFunctor = 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(v) => Leaf(f(v))
    }
}

val tree: Tree[Int] = Branch(Leaf(10), Leaf(20))
tree.map(_ * 2) // Branch(Leaf(20), Leaf(40))

cats.syntax.functor is actually just a singleton object that extends a FunctorSyntax trait, packing an implicit conversion from the class that implements Functor to the wrapper like one in slouc's answer. Wrapper itself, Functor.Ops, is generated by a Simulacrum @typeclass macro.