The product method implemented using foldRight _can_ in fact terminate early

[georgms]

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:

fpinscala/exercises/src/main/scala/fpinscala/datastructures/List.scala

Line 49 in 71a7931

def product2(ns: List[Double]) =

The answer given is no, it cannot terminate early:

fpinscala/answerkey/datastructures/07.answer.scala

Line 2 in 71a7931

No, this is not possible! The reason is because _before_ we ever call our function, `f`, we evaluate its argument, which in the case of `foldRight` means traversing the list all the way to the end. We need _non-strict_ evaluation to support early termination---we discuss this in chapter 5.

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 sidebar

To 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)
  }
}