Scala: Type Error When Enriching Collections

Question

So I'm trying to work through Norvig & Russell's "Artificial Intelligence, A Modern Approach" as a way to learn Scala. I have a pretty good grasp on the language basics at this point, but I still find myself often "fighting" the type system.

Long story short, breadth-first and depth-first search algorithms are the same aside from the mechanics of pushing/popping to their underlying collection. Depth-first would prepend new possibilities and use a Stack, while Breadth-first would append and use a Queue.

To keep my algorithm the same, I created a typeclass called "GiveGrab" (I know, horrible name) with the intention of pimping ... err ... enriching collections with these "default" push (give) and pop-like (grab) operations.For example, grab would result in a call to .dequeue() for queues, and .pop() for stacks.

Here's (a somewhat abbreviated version of) the code:

object Example extends App {

  trait GiveGrab[A, M[A]] {
    def give(x: A*): M[A]
    def grab(): A
  }

  implicit class GiveGrabQueue[T](q: Queue[T]) extends GiveGrab[T,Queue[T]] {
    override def give(x: T*) = q ++= x
    override def grab() = q.dequeue()
  }

  class TestClass[T, X <% GiveGrab[T, Queue[T]]](var storage: X) {}

  val test = new TestClass[Int, Queue[Int]](new Queue[Int]())

}

When trying to compile this, I get the following errors:

Error:(18, 39) scala.collection.mutable.Queue[T] takes no type parameters, expected: one
  class TestClass[T, X <% GiveGrab[T, Queue[T]]](var storage: X) {}
                                  ^
Error:(13, 67) scala.collection.mutable.Queue[T] takes no type parameters, expected: one
  implicit class GiveGrabQueue[T](q: Queue[T]) extends GiveGrab[T,Queue[T]] {
                                                              ^

That said, it took me a lot of trial and error to even get to this point. I'm not sure if my trait is really supposed to be typed trait GiveGrab[A, M[A]] or trait GiveGrab[A, M[_]] or trait GiveGrab[A, M]

The error "takes no type parameters, expected: one" doesn't make a whole lot of sense to me at this point, and there's only a handful of other posts about that message (some related to dependent types, and some related to the Play framework).

Somewhat related: is there a good article for understanding Scala type signatures? I read through Programming in Scala 2nd Ed, but it didn't really touch on this sort of type gymnastics (either that, or I just missed it.)

Edit: Typos

Answer 1

What @PatrykĆwiek proposed is not a workaround but actually what you are meant to be doing: M[A] in trait GiveGrab defines a type function. Roughly speaking this means: M is a type where you can apply a single type parameter to yield a concrete type. That the parameter is called A is pure coincidence. The following means the same:

trait GiveGrab[A,M[MyRandomName]] { ... }

In the definition of give, you actually use this type function to create a type, when saying M[A]. Therefore, as @PatrykĆwiek said, you should write Queue instead of Queue[T]. While Queue is precisely one of these type functions, Queue[T] is a concrete type and therefore doesn't apply to the definition of M.

The error message you get says exactly that: In the place of M, you are supposed to put a type that takes a parameter (like Queue), but you have put one which takes none (Queue[T] in your case, another example would be String or Int).