Why do I have to include extra type information in this function

Question

I'm trying to refresh a bit of Scala during my spare time. My question, why do I have to annotate 'size' with the polymorphic type A here. I'm not interested in that information when I'm calculating the size of a tree. Nonetheless the Scala compiler forces me to write it like this:

def size[A](t: Tree[A]): Int = {
    t match {
      case Leaf => 1
      case Branch(l,r) => 1 + size(l) + size(r)
    }
}

Instead of:

def size(t: Tree): Int = {
    t match {
      case Leaf => 1
      case Branch(l,r) => 1 + size(l) + size(r)
    }
}

Context of this function:

package fpinscala.datastructures

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

object Tree {

  def size[A](t: Tree[A]): Int = {
    t match {
      case Leaf => 1
      case Branch(l,r) => 1 + size(l) + size(r)
    }
  }

}

Answer 1

First notice that your function has a problem:

case Leaf => 1

Matches on equality with the Leaf companion object and not on the case class; you should write instead:

case Leaf(_) => 1

Then you can resort to wildcard existential types to avoid the type:

def size(t: Tree[_]): Int = {
  t match {
    case Leaf(_) => 1
    case Branch(l,r) => 1 + size(l) + size(r)
  }
}

Also notice that your size function will count also the number of branches and I think it more likely that you just want to count leafs; in that case change it to:

case Branch(l,r) => size(l) + size(r)

Counting branches:

size(Branch(Branch(Leaf(1),Leaf(2)),Leaf(3))) = 5

Counting leafs:

Branch(Branch(Leaf(1),Leaf(2)),Leaf(3)) = 3