Scala中的笛卡尔积和映射组合

Question

这是对以下问题的跟进：如何在Scala中将一组字符串集合扩展为笛卡尔积 你想要实现的是：

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

并获取返回结果：

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

一个通用的解决方案是：

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

使用方法如下：

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

理论上，应该有一种方法可以接收类型为Set[Set[A]]的输入，并返回一个Set[B]。也就是说，在组合元素的同时转换类型。

一个示例用法是将字符串集合（如上所述）输入并输出它们连接后的长度。在combine函数中，f函数形式应为：

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

我无法提供实现方法。有人有答案吗？

- dsg

Answer 1

如果您真的希望您的组合函数来进行映射，可以使用fold，但是正如Craig指出的那样，您需要提供一个种子值：

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(_) } 
    }

你需要这样一个种子值的事实源于组合器/映射器函数类型 (B, A) => B (或者，作为柯里化函数，B => A => B)。 显然，为了映射遇到的第一个 A，你需要提供一个 B。

你可以通过使用一个 Zero 类型类使调用者的操作更加简单：

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

接下来可以定义combine方法：

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(_) }
    }

使用方法：

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

Scalaz 提供了一个 Zero 类型类，以及许多其他函数式编程好用的工具。

- Aaron Novstrup

---

如果字符串的零是“”，并且组合函数在字符串之间放置“&”，那么这个解决方案将导致输出中每个字符串前面都有一个额外的“&”（回到OP）。 - Craig P. Motlin

Answer 2

你遇到的问题是 reduce(Left|Right) 接受 (A, A) => A 这样的函数，它不允许你改变类型。你需要更像 foldLeft 的东西，它接受 (B, A) ⇒ B，允许你累积不同类型的输出。但是 fold 需要一个种子值，这里不能是空集合。你需要将 xs 拆分成头和尾，将头迭代器映射为 Iterable[B]，然后使用映射的头、尾和某个函数 (B, A) => B 调用 foldLeft。不过，这似乎不值得费那么大劲，所以我会提前完成所有的映射。

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

- Craig P. Motlin