CODEWITHSUNDEEP
scala
SJ1987
SJ1987

Reputation: 31

Scala List Operation

Given a List of Int and variable X of Int type . What is the best in Scala functional way to retain only those values in the List (starting from beginning of list) such that sum of list values is less than equal to variable.

Upvotes: 2

Views: 159

Answers (3)

Biswanath
Biswanath

Reputation: 9185

I will go with something like this, which is more functional and should be efficient. 

def takeSumLessThan(x:Int,l:List[Int]): List[Int] = (x,l) match {
      case (_ , List())  => List()
      case (x, _) if x<= 0 => List()
      case (x, lh :: lt) => lh :: takeSumLessThan(x-lh,lt)
}

Edit 1 : Adding tail recursion and implicit for shorter call notation

import scala.annotation.tailrec

implicit class MyList(l:List[Int]) {

    def takeSumLessThan(x:Int) = {
      @tailrec
      def f(x:Int,l:List[Int],acc:List[Int]) : List[Int] = (x,l) match {
        case (_,List()) => acc
        case (x, _ ) if x <= 0 => acc 
        case (x, lh :: lt ) =>  f(x-lh,lt,acc ++ List(lh))
      }
      f(x,l,Nil)
    }
  }

Now you can use this like 

List(1,2,3,4,5,6,7,8).takeSumLessThan(10)

Upvotes: 1

Akos Krivachy
Akos Krivachy

Reputation: 4966

In addition to Travis' answer (and for the sake of completeness), you can always implement these type of operations as a foldLeft:

def takeWhileLessThanOrEqualTo(maxSum: Int)(list: Seq[Int]): Seq[Int] = {
  // Tuple3: the sum of elements so far; the accumulated list; have we went over x, or in other words are we finished yet
  val startingState = (0, Seq.empty[Int], false)
  val (_, accumulatedNumbers, _) = list.foldLeft(startingState) {
    case ((sum, accumulator, finished), nextNumber) =>
      if(!finished) {
        if (sum + nextNumber > maxSum) (sum, accumulator, true) // We are over the sum limit, finish
        else (sum + nextNumber, accumulator :+ nextNumber, false) // We are still under the limit, add it to the list and sum
      } else (sum, accumulator, finished) // We are in a finished state, just keep iterating over the list
  }
  accumulatedNumbers
}

This only iterates over the list once, so it should be more efficient, but is more complicated and requires a bit of reading code to understand.

Upvotes: 1

Travis Brown
Travis Brown

Reputation: 139028

This is pretty close to a one-liner:

def takeWhileLessThan(x: Int)(l: List[Int]): List[Int] =
  l.scan(0)(_ + _).tail.zip(l).takeWhile(_._1 <= x).map(_._2)

Let's break that into smaller pieces.

First you use scan to create a list of cumulative sums. Here's how it works on a small example:

scala> List(1, 2, 3, 4).scan(0)(_ + _)
res0: List[Int] = List(0, 1, 3, 6, 10)

Note that the result includes the initial value, which is why we take the tail in our implementation.

scala> List(1, 2, 3, 4).scan(0)(_ + _).tail
res1: List[Int] = List(1, 3, 6, 10)

Now we zip the entire thing against the original list. Taking our example again, this looks like the following:

scala> List(1, 2, 3, 4).scan(0)(_ + _).tail.zip(List(1, 2, 3, 4))
res2: List[(Int, Int)] = List((1,1), (3,2), (6,3), (10,4))

Now we can use takeWhile to take as many values as we can from this list before the cumulative sum is greater than our target. Let's say our target is 5 in our example:

scala> res2.takeWhile(_._1 <= 5)
res3: List[(Int, Int)] = List((1,1), (3,2))

This is almost what we want—we just need to get rid of the cumulative sums:

scala> res2.takeWhile(_._1 <= 5).map(_._2)
res4: List[Int] = List(1, 2)

And we're done. It's worth noting that this isn't very efficient, since it computes the cumulative sums for the entire list, etc. The implementation could be optimized in various ways, but as it stands it's probably the simplest purely functional way to do this in Scala (and in most cases the performance won't be a problem, anyway).

Upvotes: 5

Related Questions