What does "abstract over" mean?

Question

Often in the Scala literature, I encounter the phrase "abstract over", but I don't understand the intent. For example, Martin Odersky writes

You can pass methods (or "functions") as parameters, or you can abstract over them. You can specify types as parameters, or you can abstract over them.

As another example, in the "Deprecating the Observer Pattern" paper,

A consequence from our event streams being first-class values is that we can abstract over them.

I have read that first order generics "abstract over types", while monads "abstract over type constructors". And we also see phrases like this in the Cake Pattern paper. To quote one of many such examples:

Abstract type members provide flexible way to abstract over concrete types of components.

Even relevant stack overflow questions use this terminology. "can't existentially abstract over parameterized type..."

So... what does "abstract over" actually mean?

Answer 1

In algebra, as in everyday concept formation, abstractions are formed by grouping things by some essential characteristics and omitting their specific other characteristics. The abstraction is unified under a single symbol or word denoting the similarities. We say that we abstract over the differences, but this really means we're integrating by the similarities.

For example, consider a program that takes the sum of the numbers 1, 2, and 3:

val sumOfOneTwoThree = 1 + 2 + 3 

This program is not very interesting, since it's not very abstract. We can abstract over the numbers we're summing, by integrating all lists of numbers under a single symbol ns:

def sumOf(ns: List[Int]) = ns.foldLeft(0)(_ + _) 

And we don't particularly care that it's a List either. List is a specific type constructor (takes a type and returns a type), but we can abstract over the type constructor by specifying which essential characteristic we want (that it can be folded):

trait Foldable[F[_]] {   def foldl[A, B](as: F[A], z: B, f: (B, A) => B): B }  def sumOf[F[_]](ns: F[Int])(implicit ff: Foldable[F]) =   ff.foldl(ns, 0, (x: Int, y: Int) => x + y) 

And we can have implicit Foldable instances for List and any other thing we can fold.

implicit val listFoldable = new Foldable[List] {   def foldl[A, B](as: List[A], z: B, f: (B, A) => B) = as.foldLeft(z)(f) }  implicit val setFoldable = new Foldable[Set] {   def foldl[A, B](as: Set[A], z: B, f: (B, A) => B) = as.foldLeft(z)(f) }  val sumOfOneTwoThree = sumOf(List(1,2,3)) 

What's more, we can abstract over both the operation and the type of the operands:

trait Monoid[M] {   def zero: M   def add(m1: M, m2: M): M }  trait Foldable[F[_]] {   def foldl[A, B](as: F[A], z: B, f: (B, A) => B): B   def foldMap[A, B](as: F[A], f: A => B)(implicit m: Monoid[B]): B =     foldl(as, m.zero, (b: B, a: A) => m.add(b, f(a))) }  def mapReduce[F[_], A, B](as: F[A], f: A => B)                          (implicit ff: Foldable[F], m: Monoid[B]) =   ff.foldMap(as, f) 

Now we have something quite general. The method mapReduce will fold any F[A] given that we can prove that F is foldable and that A is a monoid or can be mapped into one. For example:

case class Sum(value: Int) case class Product(value: Int)  implicit val sumMonoid = new Monoid[Sum] {   def zero = Sum(0)   def add(a: Sum, b: Sum) = Sum(a.value + b.value) }  implicit val productMonoid = new Monoid[Product] {   def zero = Product(1)   def add(a: Product, b: Product) = Product(a.value * b.value) }  val sumOf123 = mapReduce(List(1,2,3), Sum) val productOf456 = mapReduce(Set(4,5,6), Product) 

We have abstracted over monoids and foldables.

Answer 2

To a first approximation, being able to "abstract over" something means that instead of using that something directly, you can make a parameter of it, or otherwise use it "anonymously".

Scala allows you to abstract over types, by allowing classes, methods, and values to have type parameters, and values to have abstract (or anonymous) types.

Scala allows you to abstract over actions, by allowing methods to have function parameters.

Scala allows you to abstract over features, by allowing types to be defined structurally.

Scala allows you to abstract over type parameters, by allowing higher-order type parameters.

Scala allows you to abstract over data access patterns, by allowing you to create extractors.

Scala allows you to abstract over "things that can be used as something else", by allowing implicit conversions as parameters. Haskell does similarly with type classes.

Scala doesn't (yet) allow you to abstract over classes. You can't pass a class to something, and then use that class to create new objects. Other languages do allow abstraction over classes.

("Monads abstract over type constructors" is only true in a very restrictive way. Don't get hung up on it until you have your "Aha! I understand monads!!" moment.)

The ability to abstract over some aspect of computation is basically what allows code reuse, and enables the creation of libraries of functionality. Scala allows many more sorts of things to be abstracted over than more mainstream languages, and libraries in Scala can be correspondingly more powerful.