Carry on information about previous computations

functional-programming, scala

Solution

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

Problem

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.

Original source