在折叠中早期中止

Question

什么是提前终止折扣的最佳方式？作为一个简化的例子,想象一下,我想总结一下数字Iterable,但如果我遇到一些我不期望的东西(比如一个奇数),我可能想要终止.这是第一个近似值

def sumEvenNumbers(nums: Iterable[Int]): Option[Int] = {
  nums.foldLeft (Some(0): Option[Int]) {
    case (Some(s), n) if n % 2 == 0 => Some(s + n)
    case _ => None
  }
}

然而,这个解决方案非常难看(如果我做了.foreach和返回 - 它会更清晰和更清晰),最糟糕的是,它遍历整个迭代,即使它遇到非偶数.

那么编写像这样的折叠最好的方法是什么呢？我应该去递归地写这个,还是有一个更被接受的方式？

Answer 1

我的第一选择通常是使用递归.它只是稍微紧凑,可能更快(当然不会慢),并且在提前终止可以使逻辑更清晰.在这种情况下,您需要嵌套的defs,这有点尴尬:

def sumEvenNumbers(nums: Iterable[Int]) = {
  def sumEven(it: Iterator[Int], n: Int): Option[Int] = {
    if (it.hasNext) {
      val x = it.next
      if ((x % 2) == 0) sumEven(it, n+x) else None
    }
    else Some(n)
  }
  sumEven(nums.iterator, 0)
}

我的第二个选择是使用return,因为它保持其他一切完整,你只需要将折叠包裹在一个def所以你有东西可以返回 - 在这种情况下,你已经有了一个方法,所以:

def sumEvenNumbers(nums: Iterable[Int]): Option[Int] = {
  Some(nums.foldLeft(0){ (n,x) =>
    if ((n % 2) != 0) return None
    n+x
  })
}

在这种特殊情况下,它比递归更紧凑(尽管由于我们必须进行迭代/迭代器转换,我们特别不满意递归).当其他条件相同时,跳跃的控制流是要避免的,但这不是.在有价值的情况下使用它没有害处.

如果我经常这样做并希望它在某个方法的中间(所以我不能只使用return),我可能会使用异常处理来生成非本地控制流.毕竟,它擅长的是什么,错误处理并不是它唯一有用的时间.唯一的技巧是避免生成堆栈跟踪(这实际上很慢),这很容易,因为特征NoStackTrace及其子特征ControlThrowable已经为您做到了.Scala已经在内部使用它(实际上,它是如何实现从折叠内部返回的!).让我们自己做(不能嵌套,虽然可以修复):

import scala.util.control.ControlThrowable
case class Returned[A](value: A) extends ControlThrowable {}
def shortcut[A](a: => A) = try { a } catch { case Returned(v) => v }

def sumEvenNumbers(nums: Iterable[Int]) = shortcut{
  Option(nums.foldLeft(0){ (n,x) =>
    if ((x % 2) != 0) throw Returned(None)
    n+x
  })
}

这里使用当然return更好,但请注意,您可以放在shortcut任何地方,而不仅仅是包装整个方法.

接下来对我来说就是重新实现折叠(要么是我自己,要么找到一个能够完成折叠的库),这样就可以提前终止.这样做的两种自然方式是不传播值,而是Option包含值,None表示终止; 或使用表示完成的第二个指示功能.Kim Stebel展示的Scalaz懒惰折叠已经涵盖了第一种情况,所以我将展示第二种情况(具有可变实现):

def foldOrFail[A,B](it: Iterable[A])(zero: B)(fail: A => Boolean)(f: (B,A) => B): Option[B] = {
  val ii = it.iterator
  var b = zero
  while (ii.hasNext) {
    val x = ii.next
    if (fail(x)) return None
    b = f(b,x)
  }
  Some(b)
}

def sumEvenNumbers(nums: Iterable[Int]) = foldOrFail(nums)(0)(_ % 2 != 0)(_ + _)

(无论是通过递归,返回,懒惰等实现终止,都取决于你.)

我认为这涵盖了主要的合理变体; 还有一些其他选项,但我不确定为什么会在这种情况下使用它们.(Iterator如果它有一个findOrPrevious,它本身就可以正常工作,但它没有,并且手工完成所需的额外工作使得在这里使用它是一个愚蠢的选择.)

Answer 2

您描述的场景(在一些不需要的条件下退出)似乎是该takeWhile方法的一个很好的用例.它本质上是filter,但应该在遇到不符合条件的元素时结束.

例如:

val list = List(2,4,6,8,6,4,2,5,3,2)
list.takeWhile(_ % 2 == 0) //result is List(2,4,6,8,6,4,2)

这也适用于Iterators/Iterables.我建议您使用"偶数总和,但在奇数上打破"的解决方案是:

list.iterator.takeWhile(_ % 2 == 0).foldLeft(...)

而且只是为了证明一旦达到奇数就不会浪费你的时间......

scala> val list = List(2,4,5,6,8)
list: List[Int] = List(2, 4, 5, 6, 8)

scala> def condition(i: Int) = {
     |   println("processing " + i)
     |   i % 2 == 0
     | }
condition: (i: Int)Boolean

scala> list.iterator.takeWhile(condition _).sum
processing 2
processing 4
processing 5
res4: Int = 6

Answer 3

您可以使用scalaz中的惰性版本的foldRight以功能样式执行您想要的操作.有关更深入的解释,请参阅此博客文章.虽然此解决方案使用a Stream,但您可以将其Iterable转换为Stream高效的iterable.toStream.

import scalaz._
import Scalaz._

val str = Stream(2,1,2,2,2,2,2,2,2)
var i = 0 //only here for testing
val r = str.foldr(Some(0):Option[Int])((n,s) => {
  println(i)
  i+=1
  if (n % 2 == 0) s.map(n+) else None
})

这只打印

0
1

这清楚地表明匿名函数只被调用两次(即直到它遇到奇数).这是由于foldr的定义,其签名(如果是Stream)def foldr[B](b: B)(f: (Int, => B) => B)(implicit r: scalaz.Foldable[Stream]): B.请注意,匿名函数将by name参数作为其第二个参数,因此无需进行求值.

顺便说一句,你仍然可以用OP的模式匹配解决方案来编写这个,但我发现if/else和map更优雅.

Answer 4

那么,Scala确实允许非本地回报.关于这是否是一种好的风格,有不同的意见.

scala> def sumEvenNumbers(nums: Iterable[Int]): Option[Int] = {
     |   nums.foldLeft (Some(0): Option[Int]) {
     |     case (None, _) => return None
     |     case (Some(s), n) if n % 2 == 0 => Some(s + n)
     |     case (Some(_), _) => None
     |   }
     | }
sumEvenNumbers: (nums: Iterable[Int])Option[Int]

scala> sumEvenNumbers(2 to 10)
res8: Option[Int] = None

scala> sumEvenNumbers(2 to 10 by 2)
res9: Option[Int] = Some(30)

编辑:

在这个特殊情况下,正如@Arjan建议的那样,你也可以这样做:

def sumEvenNumbers(nums: Iterable[Int]): Option[Int] = {
  nums.foldLeft (Some(0): Option[Int]) {
    case (Some(s), n) if n % 2 == 0 => Some(s + n)
    case _ => return None
  }
}

Answer 5

Cats有一种称为foldM的方法，它可以进行短路（对于Vector, List, Stream, ...）。

它的工作原理如下：

def sumEvenNumbers(nums: Stream[Int]): Option[Long] = {
  import cats.implicits._
  nums.foldM(0L) {
    case (acc, c) if c % 2 == 0 => Some(acc + c)
    case _ => None
  }
}

如果它找到一个非偶数元素，None则不计算其余元素就返回，否则返回偶数条目的总和。

如果您想一直计数直到找到偶数条目，您应该使用 Either[Long, Long]

Answer 6

您可以使用foldM来自cats lib（如@Didac 的建议），但如果您想获得实际总和，我建议使用Either而不是使用Option。

bifoldMap用于从 中提取结果Either。

import cats.implicits._

def sumEven(nums: Stream[Int]): Either[Int, Int] = {
    nums.foldM(0) {
      case (acc, n) if n % 2 == 0 => Either.right(acc + n)
      case (acc, n) => {
        println(s"Stopping on number: $n")
        Either.left(acc)
      }
    }
  }

例子：

println("Result: " + sumEven(Stream(2, 2, 3, 11)).bifoldMap(identity, identity))
> Stopping on number: 3
> Result: 4

println("Result: " + sumEven(Stream(2, 7, 2, 3)).bifoldMap(identity, identity))
> Stopping on number: 7
> Result: 2