Zac Zac - 1 year ago 65
Scala Question

Using partial functions to model Set in Scala, e.g. type alias: Set = Int => Boolean

I'm trying to understand how type alias works and by extension, how a simple

type modeled on
type Set = Int => Boolean
would be rewritten as a class with partial functions.

Background: I understand that I can create a type alias like above, and use it as a simple functional set data type:

type Set = Int => Boolean
def union(s: Set, t: Set): Set = (x => s(x) || t(x))
def contains(s: Set, n: Int): Boolean = s(n)
val s1 = Set(3)
val s2 = Set(7)
val u1 = union(s1, s2)
contains(u1, 3) // res4: Boolean = true

All well and good. Takes some thinking but I get how it works;

essentially becomes a partial function based on:

union(s: (Int => Boolean), t: (Int => Boolean)): Int => Boolean

So if I wanted to turn this into a class, my first attempt would be something like this:

case class Set(v: Int) {
def apply(i: Int) = i == v
def contains(n: Int): Boolean = this(n)
def union(n: Set): Set = (x => n(x) || apply(x)) // Missing param

But that doesn't work (the definition of
has a compile error,
is a missing parameter).

After fiddling with this for a while, I'm stumped on how to go about implementing a similar type without resorting to a more imperative approach (like actually creating a collection-based Set class). There must be a way to do this in a purely functional way...

Answer Source

You need to wrap Int => Boolean, not Int. So

case class Set(f: Int => Boolean) {
  def apply(i: Int) = f(i)
  def union(s: Set) = Set(x => this(x) || s(x))
  // or Set(union(f, s.f)) to use existing definition of union

For your own definition of Set, apply makes it a single-element set, so it isn't surprising you can't define union: union of two single-element sets can have more than one element.

Scala has separate namespaces for values and types. type Set or class Set define only the type Set, while val Set, object Set or var Set define a value, and case class defines both. Now, Set(3) needs a value called Set; in your first code sample there is no such value, so it uses the one from scala.Predef, which is imported automatically. scala.Predef.Set(3) returns a scala.collection.Set[Int], which happens to extend Int => Boolean, which is why union(s1, s2) compiles. case class defines both a type and a value; so with above code Set(3) doesn't compile because this value is used instead of scala.Predef.Set.