Why is a Set a function?

Question

In Scala a Set is a function:

trait Set[A] extends (A => Boolean)

This make it impossible to have a covariant immutable Set because type A occurs in contravariant position. In contrast Seq is not defined as a function. There is already some content about the question why Sets and Seqs are designed this way:

• Why is Scala's immutable Set not covariant in its type?
• Scala: Why does Seq.contains take an Any argument, instead of an argument of the sequence type?
• Why does Seq.contains accept type Any rather than the type parameter A?

One answer says that the reason for this is the mathematical background. But this answer wasn't explained a little more. So, what are the concrete advantages to define a Set as a function or what would be the disadvantages if it is implemented differently?

Answer 1

The set of type Set[A] has to have a method that tests if an element of type A is in the set. This method (apply) has to have a parameter of type A representing that element, and that parameter is in the contravariant position. This means that sets cannot be covariant in their type parameter A. So - it's not the extending of the function interface that makes it impossible to have covariant immutable sets, it's the existence of the contravariant apply method.

And for reasons of convenience, it makes sense to extend the Function1 interface to be able to pass sets around and treat them as functions.

By contrast, sequence abstraction doesn't have a method that tests if an element is in the sequence, it only has the indexing method - apply takes an integer index, and returns the element at that index. Sequences are also defined as functions, but functions of type Int => A (which are covariant in A), not A => Boolean, as sets.

If you want to know more about how type safety would be broken if sets were defined as covariant in their type parameter A, see this example in which the set implementation does some writing to private members for reasons of caching the lookups (below @uV is the annotation which disables variance checking and expensiveLookup is meant to simulate a call to a computationally expensive check if an element is in the set):

import annotation.unchecked.{uncheckedVariance => uV}

trait Set[+A] {
  def apply(elem: A @uV): Boolean
}

class CachingSet[+A >: Null] extends Set[A] {
  private var lastLookup: (A @uV, Boolean) = (null, false)
  private def expensiveLookup(elem: A @uV) = (elem, true)
  def apply(elem: A @uV): Boolean = {
    if (elem != lastLookup._1) lastLookup = expensiveLookup(elem)
    lastLookup._2
  }
  def lastQueriedElement: A = lastLookup._1
}

object Main extends App {
  val css = new CachingSet[String]
  val csa: CachingSet[AnyRef] = css

  csa.apply(new AnyRef)
  val s: String = css.lastQueriedElement // you'll get a ClassCastException here
}

Answer 2

In contrast Seq is not defined as a function.

Not true.

Seq[T] extends (Int) => T