CODEWITHSUNDEEP
scalafunctional-programminghigher-order-functions
prajwal
prajwal

Reputation: 69

Functional Programming scala

I was following "Functional Programming Principles in Scala" from coursera and in the second week the assignments is about "Purely Functional Sets" We have,

type Set = Int => Boolean

and followed by some functions like 

def union(s: Set, t: Set): Set = (element: Int) => s(element) || t(element)

So, when I do,

val u = union(Set(1, 2, 3), Set(4, 5, 6))

in scala console, it gives

u: Set = <\function1\>

a) why is it returning a function?

b) when I do contains(u, 6) it returns true but can I display all elements in u or because u is a function I cannot?

c) How does union(Set(1, 2, 3), Set(4, 5, 6)) return all elements in those two sets without any iteration?

Upvotes: 3

Views: 316

Answers (2)

jwvh
jwvh

Reputation: 51271

a) why is it returning a function?

Because Set is a function. Int => Boolean means "a function taking an Int and returning a Boolean."

b) when I do contains(u,6) it returns true but can I display all elements in u or because u is a function I cannot?

You cannot display all elements because a Set doesn't actually "contain" elements. A Set is a function of one or more tests returning true/false.

c) How does union(Set(1,2,3),Set(4,5,6)) return all elements in those two sets without any iteration?

The only way to know what values return true from a given Set is to pass in all possible values (or some accepted approximation). Values in the Set will return true otherwise you get false.

Note: This only applies to Set as defined in the question. The Set found in the Scala Standard Library is a different animal.

Upvotes: 7

Apurva Singh
Apurva Singh

Reputation: 5010

no doubt this is complicated business. Let's see how it goes.
Now I did this:

  type Sett = Int => Boolean

  def union(s: Sett, t: Sett): Sett = 
    (element: Int) => s(element) || t(element)

  val x = Set(1, 2, 3).asInstanceOf[Sett]
  val y = Set(4, 5, 6).asInstanceOf[Sett]
  val u = union(x, y)

  def contains(s: Sett, elem: Int): Boolean = s(elem)

  println(contains(u, 6))

Notice I am using Sett! Not Set. The Set above is actually scala.collections.immutable.Set. Sett is my own custom 'type'. The type is defined as Int => Boolean i.e. a function type which takes Int as parameter and returns a boolean. I renamed the custom type to Sett to avoid the confusion that one is my type, and other belongs to Scala library.
Another thing I have highlighted in my code above is, I am casting Scala's Set to my Sett! This cast works! How does it work? This is due to the fact that immutable Set inherits from Function1.. so works great.. this comment is thanks to Jorge below
The Scala Set is actually Set[Int], since it is Set(1,2,3) etc. So it is perfectly legit to cast it to subclass Sett which conforms legitimately to Int => Boolean. Just do 

val x = Set(1,2,3)
println(x(2))
println(x(4))

So it proves Scala's Set is compatible in signature to Sett for this one operation.
Iterations in union are not needed. The type Sett holds reference to two sets. If you go this:

  def union(s: Sett, t: Sett): Sett =
    (element: Int) => {
      println(element)
      s(element) || t(element)
    }

val u=union(Set(1,2,3),Set(4,5,6))

.. and then you call u(2) or whatever, the union def gets called with parameter element=2. Then the "s(element) || t(element)" is called. Set operations are of order 1 i.e. constant time. There is no need for iterations for s(element) operation because Sets are basically Maps with the value part not used.. only key is used, and keys are unique.
Martin Odersky really jumped the gun here and went too far. Should have been slower. Too many concepts covered.

Upvotes: -3

Related Questions