Difference between Ad-hoc polymorphism and Parametric polymorphism in Scala

Question

So, I have been searching documentation about the main difference between parametric polymorphism and adhoc-polymorphism, but I still have some doubts.

For instance, methods like head in Collections, are clearly parametric polymorphism, since the code used to obtain the head in a List[Int] is the same as in any other List.

List[T] {
    def head: T = this match {
        case x :: xs => x
        case Nil => throw new RuntimeException("Head of empty List.") 
    }
}

(Not sure if that's the actual implementation of head, but it doesn't matter)

On the other hand, type classes are considered adhoc-polymorphism. Since we can provide different implementations, bounded to the types.

trait Expression[T] {
    def evaluate(expr: T): Int
}

object ExpressionEvaluator {
  def evaluate[T: Expression](value: T): Int = implicitly[Expression[T]].evaluate(value)
}

implicit val intExpression: Expression[Int] = new Expression[Int] {
  override def evaluate(expr: Int): Int = expr
}

ExpressionEvaluator.evaluate(5)
// 5

In the middle, we have methods like filter, that are parametrized, but we can provide different implementations, by providing different functions.

List(1,2,3).filter(_ % 2 == 0)
// List(2)

Are methods like filter, map, etc, considered ad-hoc polymorphism? Why or why not?

Answer 1

The method filter on Lists is an example of parametric polymorphism. The signature is

def filter(p: (A) ⇒ Boolean): List[A] 

It works in exactly the same way for all types A. Since it can be parameterized by any type A, it's ordinary parametric polymorphism.

Methods like map make use of both types of polymorphism simultaneously.

Full signature of map is:

final def map[B, That]
  (f: (A) ⇒ B)
  (implicit bf: CanBuildFrom[List[A], B, That])
: That  

This method relies on the presence of an implicit value (the CBF-gizmo), therefore it's ad-hoc polymorphism. However, some of the implicit methods that provide the CBFs of the right type are actually themselves parametrically polymorphic in types A and B. Therefore, unless the compiler manages to find some very special ad-hoc construct like an CanBuildFrom[List[String], Int, BitSet] in the implicit scope, it will sooner or later fall back to something like

implicit def ahComeOnGiveUpAndJustBuildAList[A, B]
: CanBuildFrom[List[A], B, List[B]]

Therefore, I think one could say that it's a kind-of "hybrid parametric-ad-hoc polymorphism" that first attempts to find the most appropriate ad-hoc type class CanBuildFrom[List[A], B, That] in the implicit scope, but eventually falls back to ordinary parametric polymorphism, and returns a one-fits-all CanBuildFrom[List[A], B, List[B]]-solution that is parametrically polymorphic in both A and B.