Zyga - 1 year ago 71
Scala Question

Collapse the list of sets based on common element

I have something that looks like an easy enough problem that I wanted to solve functionally using Scala but cannot figure it out.
I am learning Scala and want to make sure that its done using functional programming principles. Below piece of code (which doesnt even work...) is all I managed and
it still has a mutable variable...
Any help is appreciated.

Basically I have a list of sets and I want to join all the sets that has common elements.
And apply that recursively, i.e. keep joining the sets in the list until they are only disjointed ones left.

So for input

`List(Set(1,2,3), Set(4,1,5), Set(6,2,7), Set(8,9))`
I want to get
`List(Set(1,2,3,4,5,6,7), Set(8,9))`
.

My code below - again it doesnt fully work.

``````    def mergeSets(sets: List[Set[Int]]): List[Set[Int]] = {
@tailrec
def go(list: List[Set[Int]], result: List[Set[Int]]): List[Set[Int]] = list match {
case Nil => result
case h :: t => {
var tmpResult = result
tmpResult = list.filter(_.intersect(h).nonEmpty).map(_ ++ h) ::: result
tmpResult = list.filter(_.intersect(h).isEmpty) ::: tmpResult
go(t, tmpResult.toSet.toList)
}
}
go(sets, List())
}
``````

``````val l = val l = List(Set(1,2,3), Set(4,1,5), Set(6,2,7), Set(8,9))
The main ideas is iterate over every set and yield the union of all the appropriate sets. The only trick here is using of `toSet` in order to remove duplicates.