Scala foldLeft, хотя некоторые условия выполняются

Question

Как эмулировать следующее поведение в Scala?т.е. продолжайте складывать, пока выполняются некоторые определенные условия на аккумуляторе.

def foldLeftWhile[B](z: B, p: B => Boolean)(op: (B, A) => B): B

Например,

scala> val seq = Seq(1, 2, 3, 4)
seq: Seq[Int] = List(1, 2, 3, 4)
scala> seq.foldLeftWhile(0, _ < 3) { (acc, e) => acc + e }
res0: Int = 1
scala> seq.foldLeftWhile(0, _ < 7) { (acc, e) => acc + e }
res1: Int = 6

ОБНОВЛЕНИЯ:

Основываясь на ответе @Dima, я понял, чтомое намерение было немного побочным.Поэтому я синхронизировал его с takeWhile, то есть не было бы улучшения, если предикат не совпадает.И добавьте еще несколько примеров, чтобы было понятнее.(Примечание: это не будет работать с Iterator s)

Answer 1

Первый пример: предикат для каждого элемента

Сначала вы можете использовать внутреннюю хвостовую рекурсивную функцию

implicit class TravExt[A](seq: TraversableOnce[A]) {
  def foldLeftWhile[B](z: B, f: A => Boolean)(op: (A, B) => B): B = {
    @tailrec
    def rec(trav: TraversableOnce[A], z: B): B = trav match {
      case head :: tail if f(head) => rec(tail, op(head, z))
      case _ => z
    }
    rec(seq, z)
  }
}

Или короткую версию

implicit class TravExt[A](seq: TraversableOnce[A]) {
  @tailrec
  final def foldLeftWhile[B](z: B, f: A => Boolean)(op: (A, B) => B): B = seq match {
    case head :: tail if f(head) => tail.foldLeftWhile(op(head, z), f)(op)
    case _ => z
  }
}

Затем используйте ее

val a = List(1, 2, 3, 4, 5, 6).foldLeftWhile(0, _ < 3)(_ + _) //a == 3

Второй пример: для значения аккумулятора:

implicit class TravExt[A](seq: TraversableOnce[A]) {
  def foldLeftWhile[B](z: B, f: A => Boolean)(op: (A, B) => B): B = {
    @tailrec
    def rec(trav: TraversableOnce[A], z: B): B = trav match {
      case _ if !f(z) => z
      case head :: tail => rec(tail, op(head, z))
      case _ => z
    }
    rec(seq, z)
  }
}

или короткая версия

implicit class TravExt[A](seq: TraversableOnce[A]) {
  @tailrec
  final def foldLeftWhile[B](z: B, f: A => Boolean)(op: (A, B) => B): B = seq match {
    case _ if !f(z) => z
    case head :: tail => tail.foldLeftWhile(op(head, z), f)(op)
    case _ => z
  }
}

Answer 2

Через некоторое время я получил много красивых ответов.Итак, я объединил их в этот единственный пост

очень сжатое решение от @ Dima

implicit class FoldLeftWhile[A](seq: Seq[A]) {

  def foldLeftWhile[B](z: B)(p: B => Boolean)(op: (B, A) => B): B = {
    seq.toStream.scanLeft(z)(op).takeWhile(p).lastOption.getOrElse(z)
  }
}

от @ElBaulP (я немного изменил, чтобы соответствовать комментарию @Dima)

implicit class FoldLeftWhile[A](seq: Seq[A]) {

  def foldLeftWhile[B](z: B)(p: B => Boolean)(op: (B, A) => B): B = {
    @tailrec
    def foldLeftInternal(acc: B, seq: Seq[A]): B = seq match {
      case x :: _ =>
        val newAcc = op(acc, x)
        if (p(newAcc))
          foldLeftInternal(newAcc, seq.tail)
        else
          acc
      case _ => acc
    }

    foldLeftInternal(z, seq)
  }
}

Ответ от меня (с побочными эффектами)

implicit class FoldLeftWhile[A](seq: Seq[A]) {

  def foldLeftWhile[B](z: B)(p: B => Boolean)(op: (B, A) => B): B = {
    var accumulator = z
    seq
      .map { e =>
        accumulator = op(accumulator, e)
        accumulator -> e
      }
      .takeWhile { case (acc, _) =>
        p(acc)
      }
      .lastOption
      .map { case (acc, _) =>
        acc
      }
      .getOrElse(z)
  }
}

Answer 3

А как насчет этого:

def foldLeftWhile[A, B](z: B, xs: Seq[A], p: B => Boolean)(op: (B, A) => B): B = {
  def go(acc: B, l: Seq[A]): B = l match {
    case h +: t => 
        val nacc = op(acc, h)
        if(p(nacc)) go(op(nacc, h), t) else nacc
    case _ => acc
  }
  go(z, xs)
}

val a = Seq(1,2,3,4,5,6)
val r = foldLeftWhile(0, a, (x: Int) => x <= 3)(_ + _)
println(s"$r")

Выполнить рекурсивную итерацию по коллекции, пока предикат равен true, а затем вернуть аккумулятор.

Вы можете попробовать его на scalafiddle

Answer 4

Довольно просто определить, что вы хотите в Scala.Вы можете определить неявный класс, который добавит вашу функцию к любому TraversableOnce (включая Seq).

implicit class FoldLeftWhile[A](trav: TraversableOnce[A]) {
  def foldLeftWhile[B](init: B)(where: B => Boolean)(op: (B, A) => B): B = {
    trav.foldLeft(init)((acc, next) => if (where(acc)) op(acc, next) else acc)
  }
}
Seq(1,2,3,4).foldLeftWhile(0)(_ < 3)((acc, e) => acc + e)

Обновление, поскольку вопрос был изменен:

implicit class FoldLeftWhile[A](trav: TraversableOnce[A]) {
  def foldLeftWhile[B](init: B)(where: B => Boolean)(op: (B, A) => B): B = {
    trav.foldLeft((init, false))((a,b) => if (a._2) a else {
      val r = op(a._1, b)
      if (where(r)) (op(a._1, b), false) else (a._1, true)
    })._1
  }
}

Обратите внимание, что я разделилваш (z: B, p: B => Boolean) на две функции высшего порядка.Это просто личное предпочтение в стиле scala.

Answer 5

Во-первых, обратите внимание, что ваш пример кажется неверным.Если я правильно понимаю, что вы описываете, результатом должно быть 1 (последнее значение, на котором был выполнен предикат _ < 3), а не 6

Самый простой способ сделать это - использовать return утверждение, которое очень неодобрительно в scala, но я подумал, что упомяну его для полноты.

def foldLeftWhile[A, B](seq: Seq[A], z: B, p: B => Boolean)(op: (B, A) => B): B = foldLeft(z) { case (b, a) => 
   val result = op(b, a) 
   if(!p(result)) return b
   result
}

Поскольку мы хотим избежать использования return, scanLeft может бытьвозможность:

seq.toStream.scanLeft(z)(op).takeWhile(p).last

Это немного расточительно, потому что он накапливает все (соответствующие) результаты.Вы можете использовать iterator вместо toStream, чтобы избежать этого, но Iterator по какой-то причине не имеет .last, поэтому вам придется явно просматривать его в дополнительное время:

 seq.iterator.scanLeft(z)(op).takeWhile(p).foldLeft(z) { case (_, b) => b }

Answer 6

Просто используйте условие ветвления на аккумуляторе:

seq.foldLeft(0, _ < 3) { (acc, e) => if (acc < 3) acc + e else acc}

Однако вы будете запускать каждую запись последовательности.