Cartesian Product and Map Combined in Scala

Question

This is a followup to: Expand a Set of Sets of Strings into Cartesian Product in Scala

The idea is you want to take:

val sets = Set(Set("a","b","c"), Set("1","2"), Set("S","T"))

and get back:

Set("a&1&S", "a&1&T", "a&2&S", ..., "c&2&T")

A general solution is:

def combine[A](f:(A, A) => A)(xs:Iterable[Iterable[A]]) =
    xs.reduceLeft { (x, y) => x.view.flatMap {a => y.map(f(a, _)) } }

used as follows:

val expanded = combine{(x:String, y:String) => x + "&" + y}(sets).toSet

Theoretically, there should be a way to take input of type Set[Set[A]] and get back a Set[B]. That is, to convert the type while combining the elements.

An example usage would be to take in sets of strings (as above) and output the lengths of their concatenation. The f function in combine would something of the form:

(a:Int, b:String) => a + b.length

I was not able to come up with an implementation. Does anyone have an answer?

score 9 · Accepted Answer · edited May 23 '17 at 10:33

If you really want your combiner function to do the mapping, you can use a fold but as Craig pointed out you'll have to provide a seed value:

def combine[A, B](f: B => A => B, zero: B)(xs: Iterable[Iterable[A]]) =         
    xs.foldLeft(Iterable(zero)) { 
       (x, y) => x.view flatMap { y map f(_) } 
    }

The fact that you need such a seed value follows from the combiner/mapper function type (B, A) => B (or, as a curried function, B => A => B). Clearly, to map the first A you encounter, you're going to need to supply a B.

You can make it somewhat simpler for callers by using a Zero type class:

trait Zero[T] {
   def zero: T
}
object Zero {
   implicit object IntHasZero extends Zero[Int] {
      val zero = 0
   }
   // ... etc ...
}

Then the combine method can be defined as:

def combine[A, B : Zero](f: B => A => B)(xs: Iterable[Iterable[A]]) =         
    xs.foldLeft(Iterable(implicitly[Zero[B]].zero)) { 
       (x, y) => x.view flatMap { y map f(_) }
    }

Usage:

combine((b: Int) => (a: String) => b + a.length)(sets)

Scalaz provides a Zero type class, along with a lot of other goodies for functional programming.

If the zero for Strings is "", and the combiner function puts "&" in between strings, then this solution will result in an extra "&" at the front of every string in the output (going back to the OP). — Craig P. Motlin, Dec 23 '10 at 13:25

Craig P. Motlin · Answer 2 · 2010-12-22T23:45:26.930

The problem that you're running into is that reduce(Left|Right) takes a function (A, A) => A which doesn't allow you to change the type. You want something more like foldLeft which takes (B, A) ⇒ B, allowing you to accumulate an output of a different type. folds need a seed value though, which can't be an empty collection here. You'd need to take xs apart into a head and tail, map the head iterable to be Iterable[B], and then call foldLeft with the mapped head, the tail, and some function (B, A) => B. That seems like more trouble than it's worth though, so I'd just do all the mapping up front.

def combine[A, B](f: (B, B) => B)(g: (A) => B)(xs:Iterable[Iterable[A]]) =
  xs.map(_.map(g)).reduceLeft { (x, y) => x.view.flatMap {a => y.map(f(a, _)) } }
val sets = Set(Set(1, 2, 3), Set(3, 4), Set(5, 6, 7))
val expanded = combine{(x: String, y: String) => x + "&" + y}{(i: Int) => i.toString}(sets).toSet

Cartesian Product and Map Combined in Scala

2 Answers2

Linked