Search code examples
scalafunctional-programmingtypeclassfunctorscala-cats

Cannot Resolve Map in a Functor Defined for Binary Tree


I am doing the Functor exercise from the "Scala with Cats" book. One of the exercises is to define a functor for a binary tree.

Here is my attempt (I put this code in a scala worksheet):

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]

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)
  }
}

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

Tree.branch(Tree.leaf(10), Tree.leaf(20)).map(_ * 2)

This fails, it says "cannot resolve symbol map" in the final line.

What is going on and how can I fix it? As far as I am aware, I have an equivalent solution to the one provide in the book.


Solution

  • import cats.implicits._ is missing which gives you Ops extension methods

    import cats.implicits._
    Tree.branch(Tree.leaf(10), Tree.leaf(20)).map(_ * 2)
    // res0: Tree[Int] = Branch(Leaf(20),Leaf(40))
    

    this works because it expands to

    toFunctorOps(Tree.branch(Tree.leaf(10), Tree.leaf(20)))(treeFunctor).map(_ * 2)
    

    Without extension methods in scope you could summon treeFunctor instance using companion object with main method convention Functor.apply[Tree]

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