Functional way to take an item in the list to the limit in Scala

Question

The purpose of the method is to take the items in the list until the limit is reached.

eg.

I came up with two different implementations

def take(l: List[Int], limit: Int): List[Int] = { var sum = 0 l.takeWhile { e => sum += e sum <= limit } } 

It is simple, but a mutable state is used.

 def take(l: List[Int], limit: Int): List[Int] = { val summed = l.toStream.scanLeft(0) { case (e, sum) => sum + e } l.take(summed.indexWhere(_ > limit) - 1) } 

It seems cleaner, but it is more verbose and perhaps less memory efficient because a thread is needed.

Is there a better way?

Answer 1

You can also do this in a single pass with a fold:

  def take(l: List[Int], limit: Int): List[Int] = l.fold((List.empty[Int], 0)) { case ((res, acc), next) => if (acc + next > limit) (res, limit) else (next :: res, next + acc) } 

Since standard lists are not lazy, and none of them add up, this will always go through the entire list. One option would be to use cats' iteratorFoldM instead of this implementation to make short circuits after reaching the limit.

You can also write a short trailing fold using tail recursion, something along these lines:

 def take(l: List[Int], limit: Int): List[Int] = { @annotation.tailrec def take0(list: List[Int], accList: List[Int], accSum: Int) : List[Int] = list match { case h :: t if accSum + h < limit => take0(t, h :: accList, h + accSum) case _ => accList } take0(l, Nil, 0).reverse } 

Note that this second solution may be faster, but also less elegant, as it takes extra effort to prove that the implementation is complete, something obvious when using addition.

Answer 2

The first method is perfectly fine, as the result of your function is still completely unchanged.

On the side of the note, in fact, how many functions of the scala collection library are implemented, they create a mutable builder to increase efficiency and return an immutable collection from it.

Answer 3

The functional way is to use a recursive function and ensure stack security.

If you just use the base scala:

  import scala.annotation.tailrec def take(l: List[Int], limit: Int) : List[Int] = { @tailrec def takeHelper(l:List[Int], limit:Int, r:List[Int]):List[Int] = l match { case h::t if (h <= limit ) => takeHelper(t, limit-h, r:+h) case _ => r } takeHelper(l, limit, Nil) } 

If you can use Trampoline skampas, this is a little better:

 import scalaz._ import scalaz.Scalaz._ import Free._ def take(l: List[Int], limit: Int): Trampoline[List[Int]] = { l match { case h :: t if (h <= limit) => suspend(take(t, limit - h)).map(h :: _) case _ => return_(Nil) } } println(take(List(1, 2, 3, 4, 0, 0, 1), 10).run) println(take(List.fill(10000)(1), 100000000).run) 

Answer 4

if you want to expand your own customization method, you can also use something like:

 def custom(con: => Boolean)(i: Int)(a: => List[Int])(body: => Unit): List[Int] = { if (con) { body custom(con)(i + 1)(a)(body) } else { a.slice(0, i) } } 

then name it like this:

 var j = 100 val t = customTake(j > 80)(0)((0 to 99).toList) { j -= 1 } println(t) 

Answer 5

I think your second version is already very good. You can change it a bit, for example:

 val sums = l.toStream.scanLeft(0){_ + _} drop 1 l zip sums takeWhile {_._2 <= limit} map (_._1) 

This way you are not dealing with indexes, which are usually a little easier to track.