Можно ли объединить несколько карт и сократить функции в один проход в Scala?

Question

У меня несколько картографических функций, работающих над одними и теми же данными, и я хотел бы, чтобы они выполнялись за один проход. Я ищу универсальный c способ сделать это.

val fruits: Seq[String] = Seq("apple", "banana", "cherry")

def mapF(s: String): Char = s.head
def reduceF(c1: Char, c2: Char): Char = if(c1 > c2) c1 else c2

def mapG(s: String): Int = s.length
def reduceG(i1: Int, i2: Int): Int = i1 + i2

val largestStartingChar = fruits.map(mapF).reduce(reduceF)
val totalStringLength = fruits.map(mapG).reduce(reduceG)

Я бы хотел уменьшить количество проходов за fruits. Я могу сделать это generic c для двух карт и сокращений следующим образом:

def productMapFunction[A, B, C](f: A=>B, g: A=>C): A => (B, C) = {
  x => (f(x), g(x))
}

def productReduceFunction[T, U](f: (T, T)=>T, g: (U, U) => U):
    ((T,U), (T,U)) => (T, U) = {
  (tu1, tu2) => (f(tu1._1, tu2._1), g(tu1._2, tu2._2))
}

val xMapFG = productMapFunction(mapF, mapG)
val xReduceFG = productReduceFunction(reduceF, reduceG)

val (largestStartingChar2, totalStringLength2) = 
  fruits.map(xMapFG).reduce(xReduceFG))

Я хотел бы сделать это еще более обобщенно, с произвольным числом карт и функций сокращения, но я не знаю, как поступить, или если это возможно.

Answer 1

Я думаю, вы просто пытаетесь заново изобрести преобразователи . Прошло много времени с тех пор, как я использовал Scala, но есть как минимум одна реализация .

Answer 2

Следующее решение использует Cats 2 и пользовательский тип MapReduce.

Операцию сокращения можно указать с помощью функции reduce: (O, O) => O или cats reducer: Semigroup[O]. Несколько объектов MapReduce могут быть объединены в один с помощью экземпляра Apply, предоставленного implicit def mapReduceApply[I]

import cats._
import cats.implicits._

trait MapReduce[I, O] {
  type R

  def reducer: Semigroup[R]

  def map: I => R

  def mapResult: R => O

  def apply(input: Seq[I]): O = mapResult(input.map(map).reduce(reducer.combine))
}

object MapReduce {
  def apply[I, O, _R](_reducer: Semigroup[_R], _map: I => _R, _mapResult: _R => O): MapReduce[I, O] =
    new MapReduce[I, O] {
      override type R = _R

      override def reducer = _reducer

      override def map = _map

      override def mapResult = _mapResult
    }

  def apply[I, O](map: I => O)(implicit r: Semigroup[O]): MapReduce[I, O] =
    MapReduce[I, O, O](r, map, identity)

  def apply[I, O](map: I => O, reduce: (O, O) => O): MapReduce[I, O] = {
    val reducer = new Semigroup[O] {
      override def combine(x: O, y: O): O = reduce(x, y)
    }
    MapReduce(map)(reducer)
  }

  implicit def mapReduceApply[I] =
    new Apply[({type F[X] = MapReduce[I, X]})#F] {
      override def map[A, B](f: MapReduce[I, A])(fn: A => B): MapReduce[I, B] =
        MapReduce(f.reducer, f.map, f.mapResult.andThen(fn))

      override def ap[A, B](ff: MapReduce[I, (A) => B])(fa: MapReduce[I, A]): MapReduce[I, B] =
        MapReduce(ff.reducer product fa.reducer,
          i => (ff.map(i), fa.map(i)),
          (t: (ff.R, fa.R)) => ff.mapResult(t._1)(fa.mapResult(t._2))
        )
    }

}

object MultiMapReduce extends App {

  val fruits: Seq[String] = Seq("apple", "banana", "cherry")

  def mapF(s: String): Char = s.head

  def reduceF(c1: Char, c2: Char): Char = if (c1 > c2) c1 else c2

  val biggestFirsChar = MapReduce(mapF, reduceF)
  val totalChars = MapReduce[String, Int](_.length) // (Semigroup[Int]) reduce by _ + _
  def count[A] = MapReduce[A, Int](_ => 1)

  val multiMapReduce = (biggestFirsChar, totalChars, count[String]).mapN((_, _, _))
  println(multiMapReduce(fruits))

  val sum = MapReduce[Double, Double](identity)
  val average = (sum, count[Double]).mapN(_ / _)
  println(sum(List(1, 2, 3, 4)))
  println(average(List(1, 2, 3, 4)))

}

Доступная версия также доступна на GitHub .

Answer 3

Интересный вопрос!

Я не знаю ни одной такой реализации в стандартной библиотеке или даже в scalaz / cats. Это не очень удивительно, потому что если ваш список не очень большой, вы можете просто последовательно выполнять уменьшение карты, и я даже не уверен, что затраты на создание множества промежуточных объектов будут меньше, чем затраты на обход списка несколько раз.

И если список потенциально не помещается в память, вы должны использовать одну из потоковых библиотек (fs2 / zio-streams / akka-streams)

Хотя, если вы ввели Iterator вместо List такая функциональность была бы полезна.

Есть интересная статья об этой проблеме: https://softwaremill.com/beautiful-folds-in-scala/

tldr: Рабочий процесс сокращения карты может быть оформлен следующим образом:

trait Fold[I, O] {
  type M
  def m: Monoid[M]

  def tally: I => M
  def summarize: M => O
}

В вашем случае I = List[A], tally = list => list.map(mapF), summarize = list => list.reduce(reduceF).

Чтобы запустить сокращение карты на list используя экземпляр fold вам нужно запустить

fold.summarize(fold.tally(list))

Вы можете определить combine операцию над ними: def combine[I, O1, O2](f1: Fold[I, O1], f2: Fold[I, O2]): Fold[I, (O1, O2)]

Использование combine несколько раз даст вам то, что вы хотите:

combine(combine(f1, f2), f3): Fold[I, ((O1, O2), O3)]