0

How optimize following code in good, functional way?

  List(1,2,3,4,5).foldLeft(0) {
    case (acc, e) =>
      if(acc > 5) acc
      else acc + e
  }

It is of course simple example, I am asking for general way, how do not iterate all collection if we known that accumulator will not change

user1511848
  • 35
  • 7

2 Answers2

3

You can consider using @tailrec instead of foldLeft:

import scala.annotation.tailrec
@tailrec
def methodOption1(values: List[Int])(acc: Int): Int = {
  if(acc > 5 || values.isEmpty) acc
  else method(values.tail)(acc + values.head)
}

@tailrec
def methodOption2(values: List[Int])(sum: Int): Int = {
  values match {
    case Nil => sum
    case _ if sum > 5 => sum
    case e :: tail => method(tail)(sum + e)
  }
}
methodOption1(List(1, 2, 3, 4, 5))(0)
methodOption2(List(1, 2, 3, 4, 5))(0)

You also can make Mapper to "view" it as .foldLeft

implicit class ListMapper[A](xs: List[A]) {
 def foldLeftAsTailRecWithStop[B](z: B)(op: (B, A) => B)(stop: B => Boolean): B = {
    @tailrec
    def tailrec(xs: List[A])(acc: B): B = {
      if(xs.isEmpty || stop(acc)) acc
      else tailrec(xs.tail)(op(acc, xs.head))
    }
    tailrec(xs)(z)
  }
  
  def foldLeftAsTailRec[B](z: B)(op: (B, A) => B): B = {
    @tailrec
    def tailrec(xs: List[A])(acc: B): B = {
      if(xs.isEmpty) acc
      else tailrec(xs.tail)(op(acc, xs.head))
    }
    tailrec(xs)(z)
  }
}

List(1, 2, 3,4,5).foldLeft(0)(_ + _)
List(1, 2, 3,4,5).foldLeftAsTailRec(0)(_ + _)
List(1, 2, 3,4,5).foldLeftAsTailRecWithStop(0)(_ + _)(_ > 5)

Outputs:

res0: Int = 15
res1: Int = 15
res2: Int = 6
Zvi Mints
  • 1,072
  • 1
  • 8
  • 20
  • This is not doing the same operation as the original code. The `>5` test is on the accumulated value, not the current element. And it would be `takeWhile` not `filterNot`. – Tim Jan 27 '21 at 10:55
  • @Tim Thanks for the notice, I thought he is checking the curr value and not the acc - Edited. – Zvi Mints Jan 27 '21 at 10:57
  • Thanks for response, I've thought about tail recursion but but I was wondering if i can use some kind of dedicated method (like foldLeft). – user1511848 Jan 27 '21 at 11:01
  • Other answers show how this can be done with dedicated methods, but I strongly suggest that you get comfortable with writing this sort of thing as a recursive function because it is often the cleanest and fastest solution. – Tim Jan 27 '21 at 11:32
  • Is there a reason to use curried versions of the recursive method rather than just two arguments? – Tim Jan 27 '21 at 11:37
  • @Tim - You mean with `(_ > 5)`? - No, just though it will look nicer, there any side-effects that I'm not aware of? – Zvi Mints Jan 27 '21 at 12:50
  • I means `(values: List[Int])(acc: Int)` rather than the more usual `(values: List[Int], acc: Int)` – Tim Jan 27 '21 at 14:08
  • @Tim Is there a specific reason not to use the curried version? I mean convention and etc, can you please elaborate? – Zvi Mints Feb 07 '22 at 09:17
  • The main reason for currying is to allow partial application and to improve type inference. If neither of these are required then the convention is to use the uncurried form for clarity and efficiency. – Tim Feb 07 '22 at 10:18
  • Wdym by “partial application and to improve type inference”? can you please eloberate? – Zvi Mints Feb 11 '22 at 08:53
3

You can use scanLeft(produces a lazy list containing cumulative results of applying the operator going left to right, including the initial value) and find (finds the first element of the lazy list satisfying a predicate, if any):

 List(1,2,3,4,5)
  .to(LazyList) 
  .scanLeft(0)(_ + _)
  .find(_ > 5) // Some(6): Option[Int]

UPD

To tackle the issue raised by @jwvh in the comments I was able to come up only with this ugly design:

List(1,2,3,4,5)
  .to(LazyList)
  .scanLeft((0, 0))((t, c) => (t._1 + c, t._1)) // aggregate contains current and previous value
  .takeWhile(t => (t._1 > 5 && t._2 <= 5) || t._1 <= 5)
  .last._1

So I would say that writing custom tailrec function as in @Zvi Mints's answer should be a better option here.

Guru Stron
  • 102,774
  • 10
  • 95
  • 132