Fold on tuples using set union

Given some sample data:

scala.collection.immutable.Set[(Int, Int, Int)] = Set((2,3,5), (3,4,6), (4,5,7))

I’m trying to do a set union on each element in corresponding positions of the tuple i.e. final answer should be

Set( Set(2,3,4), Set(3,4,5), Set(5,6,7) )

My failed attempt:

res3.foldLeft(Set(Set(),Set(),Set())){case (a,b,c) => (_ + a) (_ +b) (_ + c) }

Any help appreciated.

The following is one solution I think of but might not be elegant.

      val x = Set((2,3,5), (31,40,6), (4,5,71)).foldLeft(Set(Set(Integer.MAX_VALUE), Set(Integer.MAX_VALUE - 1),
      Set(Integer.MAX_VALUE - 2))) {
      case (x, (y1,y2,y3)) => x.collect {case s1 if s1.contains(Integer.MAX_VALUE) => s1 + y1
      case s2 if s2.contains(Integer.MAX_VALUE - 1) => s2 + y2
      case s3 if s3.contains(Integer.MAX_VALUE - 2) => s3 + y3}
    }.map(z => z.filter(t => t < Integer.MAX_VALUE - 3))

Another one:

   val y = Set((2, 3, 5), (31, 40, 6), (4, 5, 71)).foldLeft(List(Nil: List[Int], Nil: List[Int], Nil: List[Int])) {
      (x: List[List[Int]], z: Tuple3[Int, Int, Int]) => List(z._1 :: x(0), z._2 :: x(1), z._3 :: x(2))
    }.toSet.map((z:List[Int]) => z.reverse.toSet)

@mohamedallapitchai the .reverse likely isn’t necessary, as Sets are unordered.

1 Like

Good to see you here Emily. I will note that some types of Sets are ordered, though they aren’t the default ones. It is worth knowing about them though as the extent of the Scala collections library is one of the greatest strengths of the language, IMO. For example, the TreeSet and BitSet have both mutable and immutable versions and they come out in sorted order while mutable.LinkedHashSet comes out in the order that things are inserted. Of course, that doesn’t impact this particular code because the default Set type is the immutable.Set which is a supertype that can pick the most efficient implementation for the data it is given and for all but the LinkedHashSet your response is 100% correct that the order of the List being converted to a Set is completely irrelevant.

1 Like

Thanks - both solution work nicely but would have hoped there would have been a much cleaner way.

The problem you’re running into is that Set has a variable arity, Tuple has fixed arity (that’s difficult to abstract over), and you want to transpose those. That leads to an impedence mismatch that makes things not look so nice.

Your first attempt looks close, but has some syntax and inference issues.

As a first step, close to your original solution, I have

val tupleSets = Set((2,3,5), (3,4,6), (4,5,7))


tupleSets.foldLeft((Set.empty[Int],Set.empty[Int],Set.empty[Int])){
  case ((s1, s2, s3), (a,b,c)) => ((s1 + a), (s2 + b), (s3 + c))
}

which gives a (Set[Int], Set[Int], Set[Int]).

you can trivially get that to a Set, val s = Set(t._1, t._2, t._3), but again, it’s a bit less pretty.

Alternatively, you could turn it around, and convert the tuples first. Then you can use stdlib transpose.

Set((2,3,5), (3,4,6), (4,5,7)).map({ case (a, b, c) => List(a, b, c)}).transpose

None of it is exactly clean, but the dirt is going back and forth with lists and tuples, which is IMO forgivable.

Transscript:

C:\Users\marti>scala
Welcome to Scala 2.12.8 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_191).
Type in expressions for evaluation. Or try :help.

scala> val tupleSets = Set((2,3,5), (3,4,6), (4,5,7))
tupleSets: scala.collection.immutable.Set[(Int, Int, Int)] = Set((2,3,5), (3,4,6), (4,5,7))

scala> tupleSets.foldLeft((Set.empty[Int],Set.empty[Int],Set.empty[Int])){
     |       case ((s1, s2, s3), (a,b,c)) => ((s1 + a), (s2 + b), (s3 + c))
     |     }
res0: (scala.collection.immutable.Set[Int], scala.collection.immutable.Set[Int], scala.collection.immutable.Set[Int]) = (Set(2, 3, 4),Set(3, 4, 5),Set(5, 6, 7))

scala> Set(res0._1, res0._2, res0._3)
res1: scala.collection.immutable.Set[scala.collection.immutable.Set[Int]] = Set(Set(2, 3, 4), Set(3, 4, 5), Set(5, 6, 7))

scala> tupleSets.map{ case (a, b, c) => List(a, b, c)}.transpose
res2: scala.collection.immutable.Set[scala.collection.immutable.Set[Int]] = Set(Set(2, 3, 4), Set(3, 4, 5), Set(5, 6, 7))

Ah, yes, that’s clean. In fact, I didn’t need the outer set so I think your res0 is perfect. It was a bit of an abstraction from the real problem but can be easily mapped across.

for foldLeft, make sure that either the first parameter is widened properly to the type you need. This is a well-known annoyance. The simplest form this tends to bite you is

foo.foldLeft(Nil)/* whatever*/

Nil is a List[Nothing], so this infers the result type to List[Nothing], while you want to narrow that to the expression on the right.

The workaround is to either properly widen the initialization variable, like I did with Set.empty[Int], or ascribe the type, e.g. foo.foldLeft[List[Bar]](Nil)

EDIT: things may improve in dotty: https://contributors.scala-lang.org/t/better-type-inference-for-scala-send-us-your-problematic-cases/2410/6

The elements of my tuple (6 in total) are Set’s of tuples and Maps. Instead of explicitly giving the types, can I extract them from a variable previously defined (to cut down on clutter?)
e.g.

val myvar = Map[(A, B), C]

xs.foldLeft[myvar.type] { … something …}

use

type MyMap = Map[(A, B), C]
xs.foldLeft[MyMap] { /* something */ }

for that, that also works.

myvar.type is the type inhabited only by myvar, a singleton type, so unless you want to return myvar itself, it’s too constrained.

@emilyherbert I agree. Thanks

If you use Cats you can use operations from UnorderedFoldable and CommutativeMonoid to do this as a one-liner.

@ import cats.implicits._ 
import cats.implicits._

@ val s = Set((2,3,5), (3,4,6), (4,5,7)) 
s: Set[(Int, Int, Int)] = Set((2, 3, 5), (3, 4, 6), (4, 5, 7))

@ s.unorderedFoldMap { case (a, b, c) => (Set(a), Set(b), Set(c)) } 
res2: (Set[Int], Set[Int], Set[Int]) = (Set(4, 3, 2), Set(5, 4, 3), Set(7, 6, 5))
1 Like