CODEWITHSUNDEEP
scala
Michiel Borkent
Michiel Borkent

Reputation: 34800

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

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

}

Upvotes: 3

Views: 101

Answers (2)

Aldo Stracquadanio
Aldo Stracquadanio

Reputation: 6237

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

Upvotes: 4

Mik378
Mik378

Reputation: 22171

Regarding your comments, you have this: 

object Tree {

  def size[A](t: Tree[A]): Int = {  //you would want to avoid specifying the first [A]
    t match {
      case Leaf => 1
      case Branch(l,r) => 1 + size(l) + size(r)
    }
  }

}

Notice that a companion object doesn't involve a generic type, so you have to specify it on its method(s), otherwise the compiler would search for a A class (while parsing the size's parameters), that obviously doesn't exist.
You want to tell the compiler: A is meant to be a generic type, not a particular one!

So it's not really a boilerplate, it's what the compiler requires and it seems perfectly logical.

Upvotes: 0

Related Questions