Zac - 7 months ago 42

Scala Question

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

`Set`

`type Set = Int => Boolean`

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;

`u1`

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

`union`

`x`

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

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`

.