The product method implemented using foldRight _can_ in fact terminate early #679
Description
The question is if the product2 method implemented using foldRight can terminate early with the result 0.0 if it encounters 0.0 in the list.
The method is defined here:
The answer given is no, it cannot terminate early:
However, providing a second higher-order function that checks for an early termination + a return value for that case makes early termination possible. A crude implementation might look like this:
def foldRight[A, B](as: List[A], z: B)(f: (A, B) => B)(abort: (A => (Boolean), B)): B = // Utility functions
as match {
case Nil => z
case Cons(x, xs) => if (abort._1(x)) abort._2 else f(x, foldRight(xs, z)(f)(abort))
}
def product2(ns: List[Double]) =
foldRight(ns, 1.0)(_ * _)((_ == 0.0, 0.0)) // `_ * _` is more concise notation for `(x,y) => x * y`; see sidebarTo wit:
class ListTest extends munit.FunSuite {
test("product with 0 returns 0") {
assertEquals(List.product2(List(1, 2, 3, 0, 4)), 0d)
}
test("product") {
assertEquals(List.product2(List(1, 2, 3)), 6d)
}
}