Geek asks and answers

Post information about previous calculations

I am new to functional programming, so some problems are more difficult to solve using a functional approach.

Let's say I have a list of numbers, for example, from 1 to 10.000, and I want to get the elements of a list that adds up to no more than the number n (say, 100). Thus, he will receive the numbers until their amount becomes more than 100.

In imperative programming, it is trivial to solve this problem, because I can store the variable in each interaction and stop after reaching the goal.

But how can I do the same in functional programming? Since the sum function works with complete lists, and I still don't have a complete list, how can I continue with the calculation?

If the amount were lazily calculated, I could write something like this:

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

PS: Even if any answer is appreciated, I would like it to not calculate the sum every time, since, obviously, the imperative version will be much more optimal with respect to speed.

Edit:

I know that I can "transform" the imperative loop approach to a functional recursive function. I'm more interested in searching if one of the existing library functions can provide me with the opportunity not to write every time I need something.

+5
source share
4 answers

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:

Getting the components is not too difficult. So you can do this:

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.

, . , .

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
+7

, , - . . - 100, . , .

+1

"" .
, , , , .

, , N:

  • , ; .
  • N, ; .
  • H .
    , , , N - H, "cons" H , .
    , , , .

:

sum_to (n, ls) = if isEmpty ls or n < (head ls)
                 then Nil
                 else (head ls) :: sum_to (n - head ls, tail ls)

sum_to(100, some_list)
+1

, , , . ,

, , ,

, : map fold filter zip .. - , , ,

0
source

More articles: