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.

Answer 3

An abstraction is a sort of generalization.

http://en.wikipedia.org/wiki/Abstraction

Not only in Scala but many languages there is a need to have such mechanisms to reduce complexity(or at least create a hierarchy that partitions information into easier to understand pieces).

A class is an abstraction over a simple data type. It is sort of like a basic type but actually generalizes them. So a class is more than a simple data type but has many things in common with it.

When he says "abstracting over" he means the process by which you generalize. So if you are abstracting over methods as parameters you are generalizing the process of doing that. e.g., instead of passing methods to functions you might create some type of generalized way to handle it(such as not passing methods at all but building up a special system to deal with it).

In this case he specifically means the process of abstracting a problem and creating a oop like solution to the problem. C has very little ability to abstract(you can do it but it gets messy real quick and the language doesn't directly support it). If you wrote it in C++ you could use oop concepts to reduce the complexity of the problem(well, it's the same complexity but the conceptualization is generally easier(at least once you learn to think in terms of abstractions)).

e.g., If I needed a special data type that was like an int but, lets say restricted I could abstract over it by creating a new type that could be used like an int but had those properties I needed. The process I would use to do such a thing would be called an "abstracting".

Answer 4

Here is my narrow show and tell interpretation. It's self-explanatory and runs in the REPL.

class Parameterized[T] { // type as a parameter
  def call(func: (Int) => Int) = func(1)  // function as a parameter
  def use(l: Long) { println(l) } // value as a parameter
}

val p = new Parameterized[String] // pass type String as a parameter
p.call((i:Int) => i + 1) // pass function increment as a parameter
p.use(1L) // pass value 1L as a parameter


abstract class Abstracted { 
  type T // abstract over a type
  def call(i: Int): Int // abstract over a function
  val l: Long // abstract over value
  def use() { println(l) }
}

class Concrete extends Abstracted { 
  type T = String // specialize type as String
  def call(i:Int): Int = i + 1 // specialize function as increment function
  val l = 1L // specialize value as 1L
}

val a: Abstracted = new Concrete
a.call(1)
a.use()

Answer 5

The other answers give already a good idea of what kinds of abstractions exist. Lets go over the quotes one by one, and provide an example:

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.

Pass function as a parameter: List(1,-2,3).map(math.abs(x)) Clearly abs is passed as parameter here. map itself abstracts over a function that does a certain specialiced thing with each list element. val list = List[String]() specifies a type paramter (String). You could write a collection type which uses abstract type members instead: val buffer = Buffer{ type Elem=String }. One difference is that you have to write def f(lis:List[String])... but def f(buffer:Buffer)..., so the element type is kind of "hidden" in the second method.

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

In Swing an event just "happens" out of the blue, and you have to deal with it here and now. Event streams allow you to do all the plumbing an wiring in a more declarative way. E.g. when you want to change the responsible listener in Swing, you have to unregister the old and to register the new one, and to know all the gory details (e.g. threading issues). With event streams, the source of the events becomes a thing you can simply pass around, making it not very different from a byte or char stream, hence a more "abstract" concept.

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

The Buffer class above is already an example for this.

Answer 6

Answers above provide an excellent explanation, but to summarize it in a single sentence, I would say:

Abstracting over something is the very same as neglecting it where irrelevant.