How to use foldM of Foldable?

Question

I am trying to understand foldM of Foldable in cats trying a simple example: suppose I need to sum up the numbers in a list while the running sum is positive and break when it is not.

val sumUp: (Int, Int) => Option[Int] = (x, y) => {
  println(s"x = $x, y = $y")
  val sum = x + y
  if (sum > 0) Some(sum) else None 
} 

scala> val xs  = List(1, 2, 3, -2, -5, 1, 2, 3)
xs: List[Int] = List(1, 2, 3, -2, -5, 1, 2, 3)

scala> Foldable[Stream].foldM(xs.toStream, 0)(sumUp)
x = 0, y = 1
x = 1, y = 2
x = 3, y = 3
x = 6, y = -2
x = 4, y = -5
res27: Option[Int] = None

Now I need to write new function sumUp2 to get the input stream tail, which starts where the running sum becomes <= 0 and the foldM breaks. For example, I need to get something like this:

scala> val tail = Foldable[Stream].foldM(xs.toStream, 0)(sumUp2)
tail: Stream[Int] = Stream(-5, ?)

scala>tail.toList
res28: List[Int] = List(-5, 1, 2, 3)

How to write sumUp2 ?

Here is an example that may help: https://stackoverflow.com/a/61187517/5115898 — Tobi, Oct 09 '20 at 10:13
@Tobi Thanks a lot. This early abort of fold is a great example ! — Michael, Oct 09 '20 at 10:16

Jordão · Answer 1 · 2017-04-15T14:06:21.960

3

What you can do is accumulate two values (in a tuple): the running sum up until it turns negative or zero; and the tail, which starts to accumulate values then.

val sumUp2: ((Int, List[Int]), Int) => Id[(Int, List[Int])] = (x, y) => {
  val sum = if (x._1 < 0) x._1 else x._1 + y
  if (sum > 0) (sum, x._2) else (-1, x._2 ++ List(y))
}

Then, you can get the tail from the second element in the tuple:

val xs  = List(1, 2, 3, -2, -5, 1, 2, 3)
val res = Foldable[Stream].foldM(xs.toStream, (0, List[Int]()))(sumUp2)

println(res._2)

Fiddle here.

edited Apr 15 '17 at 14:06

answered Apr 15 '17 at 13:23

Jordão

55,340
13
112
144

Unfortunately, `sumUp2` is invoked for _all_ elements of `xs` but I would like to stop invoking the fuction when the running sum <= 0. Thank you anyway. – Michael Apr 15 '17 at 14:56

score 1 · Answer 2 · answered Apr 15 '17 at 16:46

I wrote sumUp2 to return Either[Int, (Int, Int)]: left is the number of visited elements and the right is a pair of the number of visited elements and running sum.

type IntOr[A] = Either[Int, A]
val sumUp2: ((Int, Int), Int) => IntOr[(Int, Int)] = (pair, y) => {
  val (size, x) = pair
  val sum = x + y
  println(s"sum = $sum, y = $y")
  if (sum > 0) (size + 1, sum).asRight else size.asLeft 
}

We know that foldM stops when sumUp2 returns Left so sumUp2 won't be invoked for all elements:

scala> val r = Foldable[Stream].foldM(xs.toStream, (0, 0))(sumUp2)
sum = 1, y = 1
sum = 3, y = 2
sum = 6, y = 3
sum = 4, y = -2
sum = -1, y = -5
r: IntOr[(Int, Int)] = Left(4)

Given r: Either[Int, (Int, Int)] we can get the tail:

scala> r match { case Right(_) => Nil; case Left(n) => xs.drop(n) }
res63: List[Int] = List(-5, 1, 2, 3)

The solution seems to work fine but doesn't look nice to me. How would you improve it ?

I was about to propose the `Either` solution as well. Now I'll just leave mine untouched (+1). — Jordão, Apr 15 '17 at 17:55
Thanks. Do you understand how `foldM` "knows" to stop when the function returns `Left` ? Maybe I will post a separate question about understanding how `foldM` works. — Michael, Apr 15 '17 at 17:59

How to use foldM of Foldable?

2 Answers2