Carry on information about previous computations

Question

I'm new to functional programming, so some problems seems harder to solve using functional approach.

Let's say I have a list of numbers, like 1 to 10.000, and I want to get the items of the list which sums up to at most a number n (let's say 100). So, it would get the numbers until their sum is greater than 100.

In imperative programming, it's trivial to solve this problem, because I can keep a variable in each interaction, and stop once the objective is met.

But how can I do the same in functional programming? Since the sum function operates on completed lists, and I still don't have the completed list, how can I 'carry on' the computation?

If sum was lazily computed, I could write something like that:

           (1 to 10000).sum.takeWhile(_ < 100)

P.S.:Even though any answer will be appreciated, I'd like one that doesn't compute the sum each time, since obviously the imperative version will be much more optimal regarding speed.

Edit:

I know that I can "convert" the imperative loop approach to a functional recursive function. I'm more interested in finding if one of the existing library functions can provide a way for me not to write one each time I need something.

Answer 1

Use Stream.

scala> val ss = Stream.from(1).take(10000)
ss: scala.collection.immutable.Stream[Int] = Stream(1, ?)

scala> ss.scanLeft(0)(_ + _)
res60: scala.collection.immutable.Stream[Int] = Stream(0, ?)

scala> res60.takeWhile(_ < 100).last
res61: Int = 91

EDIT:

Obtaining components is not very tricky either. This is how you can do it:

scala> ss.scanLeft((0, Vector.empty[Int])) { case ((sum, compo), cur) => (sum + cur, compo :+ cur) }
res62: scala.collection.immutable.Stream[(Int, scala.collection.immutable.Vector[Int])] = Stream((0,Vector()), ?)

scala> res62.takeWhile(_._1 < 100).last
res63: (Int, scala.collection.immutable.Vector[Int]) = (91,Vector(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13))

The second part of the tuple is your desired result.

As should be obvious, in this case, building a vector is wasteful. Instead we can only store the last number from the stream that contributed to sum.

scala> ss.scanLeft(0)(_ + _).zipWithIndex
res64: scala.collection.immutable.Stream[(Int, Int)] = Stream((0,0), ?)

scala> res64.takeWhile(_._1 < 100).last._2
res65: Int = 13

Answer 2

The way I would do this is with recursion. On each call, add the next number. Your base case is when the sum is greater than 100, at which point you return all the way up the stack. You'll need a helper function to do the actual recursion, but that's no big deal.