Декартово произведение и карта, объединенные в 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]. То есть для преобразования типа при объединении элементов.

Примером использования было бы взять наборы строк (как указано выше) и вывести длины их конкатенации. Функция f в combine будет иметь вид:

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

Я не смог придумать реализацию. У кого-нибудь есть ответ?

Answer 1

Если вы действительно хотите, чтобы функция объединителя выполняла сопоставление, вы можете использовать fold, но, как указал Крейг , вам нужно будет указать начальное значение:

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класс type, а также множество других полезностей для функционального программирования.

Answer 2

Проблема, с которой вы сталкиваетесь, состоит в том, что Reduce (Left | Right) принимает функцию (A, A) => A, которая не позволяет вам изменять тип.Вы хотите что-то более похожее на foldLeft, который принимает (B, A) ⇒ B, позволяя накапливать выходные данные другого типа.складки требуют начального значения, которое здесь не может быть пустой коллекцией.Вам нужно было бы разделить xs на голову и хвост, отобразить итеративную голову как Iterable [B], а затем вызвать foldLeft с отображенной головой, хвостом и некоторой функцией (B, A) => B.кажется, больше проблем, чем оно того стоит, поэтому я просто сделал бы все картирование заранее.

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