Why this Scala code doesn't type checked

Question

I want to write a function to count the size of a binary tree, the function 'size' works fine, but it's too slow. I then write a function called 'size2', however, it's not type checked. Why?

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]

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

def size2[A](tree: Tree[A]): Int = {
  trait Timing
  case object First extends Timing
  case object TravelLeft extends Timing
  case object TravelRight extends Timing
  type Stack = List[(Tree[A], Timing)]

  def count(history: Stack, res: Int): Int = history match {
    case Nil => res
    case (Leaf(_), _)::tail => count(tail, res + 1)
    case (b@Branch(l, _), First)::tail =>
      val next = (l, First)::(b, TravelLeft)::tail
      count(next, res)
    case (b@Branch(_, r), TravelLeft)::tail =>
      val next = (r, First)::(b, TravelRight)::tail
      count(next, res)
    case (_, TravelRight)::tail => count(tail, res + 1)
  }
  count(List((tree, First)), 0)
}

The error message is as follows:

Error:(19, 23) constructor cannot be instantiated to expected type;
 found   : scala.collection.immutable.::[B]
 required: test.List[(A$A301.this.Tree[A], Timing)]
    case (Leaf(_), _)::tail => count(tail, res + 1)
                     ^
Error:(21, 34) constructor cannot be instantiated to expected type;
 found   : scala.collection.immutable.::[B]
 required: test.List[(A$A301.this.Tree[A], Timing)]
    case (b@Branch(l, _), First)::tail =>
                                ^
Error:(24, 39) constructor cannot be instantiated to expected type;
 found   : scala.collection.immutable.::[B]
 required: test.List[(A$A301.this.Tree[A], Timing)]
    case (b@Branch(_, r), TravelLeft)::tail =>
                                     ^
Error:(27, 27) constructor cannot be instantiated to expected type;
 found   : scala.collection.immutable.::[B]
 required: test.List[(A$A301.this.Tree[A], Timing)]
    case (_, TravelRight)::tail => count(tail, res + 1)
                         ^
Error:(66, 23) constructor cannot be instantiated to expected type;
 found   : scala.collection.immutable.::[B]
 required: test.List[(inst$A$A.Tree[A], Timing)]
    case (Leaf(_), _)::tail => count(tail, res + 1)
                     ^
Error:(68, 34) constructor cannot be instantiated to expected type;
 found   : scala.collection.immutable.::[B]
 required: test.List[(inst$A$A.Tree[A], Timing)]
    case (b@Branch(l, _), First)::tail =>
                                ^
Error:(71, 39) constructor cannot be instantiated to expected type;
 found   : scala.collection.immutable.::[B]
 required: test.List[(inst$A$A.Tree[A], Timing)]
    case (b@Branch(_, r), TravelLeft)::tail =>
                                     ^
Error:(74, 27) constructor cannot be instantiated to expected type;
 found   : scala.collection.immutable.::[B]
 required: test.List[(inst$A$A.Tree[A], Timing)]
    case (_, TravelRight)::tail => count(tail, res + 1)
                         ^

Answer 1

=======================update===========================

Thanks for som-snytt's help. This error raised because I've defined a List in the same package. See the error message, it wants a object of test.List, and the :: object create a List of standard library, which doesn't type checked

========================================================

Ok, thanks for Wickoo's comment. I have tried it again in a Scala file and it works fine. This error only raise in a scala work sheet which I don't know why.