CODEWITHSUNDEEP
algorithmscalafunctional-programming
danny.lesnik
danny.lesnik

Reputation: 18639

Scala Code - Immutable Set Issues

I'm learning Scala and I would like to convert some of my old algorithms code to Scala.

I have very simple Java code which prints superSet (a combination of all possible sets including empty set and the set itself). 

public static Set<Set<Integer>> createSuperSet(Set<Integer> originalSet){
    Set<Set<Integer>> superSet = new HashSet<Set<Integer>>();

    if (originalSet.size() == 0){
        Set<Integer> empty = new HashSet<Integer>();
        superSet.add(empty);
        return superSet;
    }

    List<Integer> list = new ArrayList<Integer>(originalSet);
    Integer head = list.get(0);
    Set<Integer> rest = new HashSet<Integer>(list.subList(1, list.size()));
    for (Set<Integer> set  : createSuperSet(rest)){
        Set<Integer> newSet = new HashSet<Integer>();
        newSet.add(head);
        newSet.addAll(set);
        superSet.add(newSet);
        superSet.add(set);
    }       
    return superSet;
}

Now I'm trying to achieve the same functionality in Scala:

  def createSuperSet(originalSet: Set[Int]): Set[Set[Int]] ={
     val superSet = Set[Set[Int]]()

     originalSet.toList match {   

       case List() => {superSet + Set[Int]()} 

       case head::restAsList => {
         val rest = restAsList.toSet[Int]
         val result = createSuperSet(rest)
         result.foreach(f=>{
           val newSet:Set[Int] =  f + head
           superSet + f +newSet
         }) 
         superSet
       }
     }   
  }

but unfortunately this code returns empty Set. I'm suspecting that this issue happens due to Immutable collection usage. I was trying to run it in Debugger and I see that recursive call to function always returns empty set and my code is never getting into foreach function.

Please help. Any thoughts are welcomed.

Upvotes: 2

Views: 146

Answers (2)

danny.lesnik
danny.lesnik

Reputation: 18639

I solved the problem this way: 

 def createSuperSet(originalSet: Set[Int]): Set[Set[Int]] ={
     var superSet = Set[Set[Int]]()

     originalSet.toList match {   

       case List() => {superSet + Set[Int]()} 

       case head::restAsList => {
         val rest = restAsList.toSet[Int]
         val result = createSuperSet(rest)
         result.map(f=>{
           superSet = superSet  + f+ (f+head)
         }) 
         superSet
       }
     }   
  }

running println(createSuperSet(Set[Int](1,2,3))

prints 

Set(Set(), Set(3, 1), Set(2), Set(2, 1), Set(3, 2), Set(3), Set(3, 2, 1), Set(1))

but I'll be very glad to find out if there is any more elegant solution

Upvotes: 0

J Cracknell
J Cracknell

Reputation: 3547

In idiomatic scala the + (and -, ++, etc) operator as applied to immutable collections creates a new collection - otherwise they would not be immutable. Instead you have to combine the modification with another piece of syntactic sugar under which if you append = to an operator it assigns the result of the operator to the left-hand variable: superSet += f + newSet.

Upvotes: 4

Related Questions