FoldLeft, но сохранить оригинальную структуру данных

Question

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

Пример игрушки:

def getStrings(lst: Traversable[String]): Traversable[String] = {
  val someStrings = lst.filter(_.length >= 6)
  val stringCount = someStrings.foldLeft(0)((accum, line) => accum + 1)
  println(stringCount)
  someStrings
}

Этот пример обладает необходимой функциональностью, но он выполняет два прохода по структуре данных: один для фильтрации, а другой для уменьшения. То, что я хочу выполнить sh, это какая-то операция "foldLeft", которая вычисляет текущий подсчет, но также возвращает исходную структуру данных. Идея примерно такая:

def getStrings(lst: Traversable[String]): Traversable[String] = {
  val strings = lst.filter(_.length >= 6).smoothOperator(0)((accum, line) => {
    if (line.isLast) {
      println(accum)
    } else {
      accum + 1
    }
  })

  strings
}

В идеале, приложение smoothOperator должно хорошо распараллеливаться, как и любая другая операция с картой, и добавлять к аккумулятору по мере прохождения данных, минимизируя таким образом количество итераций. поверх структуры данных.

Возможно ли это?

Answer 1

То, что вам нужно, это IMHO isomorphi c для запуска foldLeft, но для чего-то, что делает несколько сгибов одновременно:

def doubleFoldLeft[A, B, C](traversable: Traversable[A], firstZero: B, secondZero: C)(
  firstFold: (B, A) => B
)(
  secondFold: (C, A) => C
): (B, C) = traversable.foldLeft(firstZero -> secondZero) {
  case ((b, c), a) =>
    firstFold(b, a) -> secondFold(c, a)
}

то, что вы запрашиваете точно, потребовало бы его динамического построения, поэтому что бы вы повернули:

def zipWithFoldLeftUntilElement[A, B](
  traversable: Traversable[A],
  zero: B
)(fold: (B, A) => B): Traversable[(A, B)] = ...

с тем, что вы все равно в конечном итоге будете использовать в конце команду fold:

zipWithFoldLeftUntilElement[(myTraversable.filter(...), zero) {
  ...
}.foldLeft(anotherZero) { case ((a, b), c) =>
  ... // do sth with a and c
  b -> c
} // (B, C) - tuple of 2 fold results

Короче говоря, если вы хотите использовать поток один раз, но вычислить несколько вещей параллельно ... просто вычислите больше чем одну вещь в .foldLeft. Если ваша логика c более сложная, чем это ... я бы подумал об использовании реактивных потоков, таких как Akka Streams или FS2. Если лог c действительно действительно испорчен, я бы попробовал Графики Akka Streams .

Answer 2

Вот мое решение

object GetStringsTest extends App{

  def getStringsOriginal(lst: Traversable[String]): Traversable[String] = {
    val someStrings = lst.filter(_.length >= 6)
    val stringCount = someStrings.foldLeft(0)((accum, line) => accum + 1)
    println(stringCount)
    someStrings
  }

  def getStringsOnePass(lst: Traversable[String]): Traversable[String] = {
    val folded = lst.foldRight((IndexedSeq[String](), 0)){ (e, acc) =>
      if (e.length >= 6) (e +: acc._1, acc._2 + 1)
      else acc
    }
    println(folded._2)
    folded._1
  }

  val myList = List("hi", "defenestration", "supercilious", "football", "tea")
  println(getStringsOriginal(myList))
  println(getStringsOnePass(myList))
}

Я использовал foldRight на всякий случай, если вы хотите поменять IndexedSeq на List. Если вы создаете список, вам нужно использовать foldRight вместо foldLeft.

Мое решение возвращает последовательность правильного типа, но она может быть другого типа, чем входной Traversable. Выходные данные всегда будут иметь тип IndexedSeq [String]. Если вход имеет тип List [String], выход будет другого типа.

Answer 3

  // with immutable List
  def foldAndFilter1[A, M](orig: Iterable[A])(p: A => Boolean)(mEmpty: M)(mf: (M, A) => M): (M, Iterable[A]) =
    orig.foldLeft((mEmpty, List.empty[A])) { case ((meta, filtered), item) =>
      (mf(meta, item), if (p(item)) item::filtered else filtered)
    } match { case (meta, list) => (meta, list.reverse) }

  // with mutable ListBuffer
  def foldAndFilter2[A, M](orig: Iterable[A])(p: A => Boolean)(mEmpty: M)(mf: (M, A) => M): (M, Iterable[A]) =
    orig.foldLeft((mEmpty, ListBuffer.empty[A])) { case ((meta, filtered), item) =>
      (mf(meta, item), if (p(item)) filtered:+item else filtered)
    }

  val rs1: (Int, Iterable[Int]) = foldAndFilter1(1 to 10 toList)(n => n%2 == 0)(0)((m, _) => m+1)
  val rs2: (Int, Iterable[Int]) = foldAndFilter2(1 to 10 toList)(n => n%2 == 0)(0)((m, _) => m+1)

foldRight не имеет никакого смысла, поскольку может использоваться только на IndexedSeq, а эффективное распараллеливание может быть достигнуто только на IndexedSeq, чтобы обеспечить быструю операцию разделения *

также может быть выражается через Cats, но вам нужно иметь моноид для вашего типа М

  import cats.{Applicative, Monoid, Traverse}
  import cats.syntax.applicative._
  def foldAndFilter3[F[_]: Traverse: Applicative, A, M](orig: F[A])(p: A => Boolean)(mf: (M, A) => M)(implicit fam: Monoid[F[A]], mm: Monoid[M]): (M, F[A]) =
    Traverse[F].foldLeft(orig, (mm.empty, fam.empty)) { case ((meta, filtered), item) =>
      (mf(meta, item), if (p(item)) fam.combine(filtered, item.pure[F]) else filtered )
    }

  import cats.instances.list._
  import cats.instances.int._
  val rs3: (Int, Iterable[Int]) = foldAndFilter3(1 to 10 toList)(n => n%2 == 0)((m:Int, _) => m+1)

, но любое обобщение, с одной стороны, приводит к более читабельному, легкому для написания коду, но с другой стороны менее оптимизированы в конкретном случае.

Answer 4

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