Summing a List of Options with Applicative Functors

Question

I have a List[Option[Int]] and want to sum over it using applicative functors. From [1] I understand that it should be something like the following

import scalaz._
import Scalaz._

List(1,2,3).map(some(_)).foldLeft(some(0))({
    case (acc,value) => (acc <|*|> value){_+_}
})

however I am simply not able to figure out the correct way to write this. I would be glad if somebody could help me with this.

Thank you very much

[1] How to combine Option values in Scala?

Edit

Thanks for all the great answers.

If there is any None in the list, I want it to return None. I am trying to replace Null/Exception with Option/Either and see if I can produce some usable code.

Some function will fill my list and I want to process it further as easy as possible without checking if one of the elements was None. It should work similar as Exceptions, where I don't have to check for it in my function, but let the caller take care of it.

Chutney

Hi Manuel! Yes the very important part is always how to handle None: Ignore or Fail fast see here for a related example: gist.github.com/970717 – Doyledoyley

Hi Andreas. Code snippets like yours is what I need. – Chutney

Answer 1

If you have Option[T] and if there's a Monoid for T, then there's a Monoid[Option[T]]:

implicit def optionTIsMonoid[T : Monoid]: Monoid[Option[T]] = new Monoid[Option[T]] {
  val monoid = implicitly[Monoid[T]]
  val zero = None
  def append(o1: Option[T], o2: =>Option[T]) = (o1, o2) match {
    case (Some(a), Some(b)) => Some(monoid.append(a, b))
    case (Some(a), _)       => o1
    case (_, Some(b))       => o2
    case _                  => zero
  }
}

Once you are equipped with this, you can just use sum (better than foldMap(identity), as suggested by @missingfaktor):

 List(Some(1), None, Some(2), Some(3), None).asMA.sum === Some(6)

UPDATE

We can actually use applicatives to simplify the code above:

implicit def optionTIsMonoid[T : Monoid]: Monoid[Option[T]] = new Monoid[Option[T]] {
   val monoid = implicitly[Monoid[T]]
   val zero = None
   def append(o1: Option[T], o2: =>Option[T]) = (o1 |@| o2)(monoid.append(_, _))
}

which makes me think that we can maybe even generalize further to:

implicit def applicativeOfMonoidIsMonoid[F[_] : Applicative, T : Monoid]: Monoid[F[T]] = 
  new Monoid[F[T]] {
    val applic = implicitly[Applicative[F]]
    val monoid = implicitly[Monoid[T]]

    val zero = applic.point(monoid.zero)
    def append(o1: F[T], o2: =>F[T]) = (o1 |@| o2)(monoid.append(_, _))
  }

Like that you would even be able to sum Lists of Lists, Lists of Trees,...

UPDATE2

The question clarification makes me realize that the UPDATE above is incorrect!

First of all optionTIsMonoid, as refactored, is not equivalent to the first definition, since the first definition will skip None values while the second one will return None as soon as there's a None in the input list. But in that case, this is not a Monoid! Indeed, a Monoid[T] must respect the Monoid laws, and zero must be an identity element.

We should have:

zero    |+| Some(a) = Some(a)
Some(a) |+| zero    = Some(a)

But when I proposed the definition for the Monoid[Option[T]] using the Applicative for Option, this was not the case:

None    |+| Some(a) = None
None    |+| None    = None
=> zero |+| a      != a

Some(a) |+| None    = zero
None    |+| None    = zero
=> a    |+| zero   != a

The fix is not hard, we need to change the definition of zero:

// the definition is renamed for clarity
implicit def optionTIsFailFastMonoid[T : Monoid]: Monoid[Option[T]] = 
  new Monoid[Option[T]] {
    monoid = implicitly[Monoid[T]]
    val zero = Some(monoid.zero)
    append(o1: Option[T], o2: =>Option[T]) = (o1 |@| o2)(monoid.append(_, _))
  }

In this case we will have (with T as Int):

Some(0) |+| Some(i) = Some(i)
Some(0) |+| None    = None
=> zero |+| a       = a

Some(i) |+| Some(0) = Some(i)
None    |+| Some(0) = None
=> a    |+| zero    = zero

Which proves that the identity law is verified (we should also verify that the associative law is respected,...).

Now we have 2 Monoid[Option[T]] which we can use at will, depending on the behavior we want when summing the list: skipping Nones or "failing fast".

Opinion

Just after posting this, I realize that I'm not really answering the question, since I'm not using any Applicative. Just consider this as one of the numerous alternatives,... – Opinion

I don't understand how that works... why is there no + anywhere? – Pleasure

.foldMap(identity) can be replaced by .asMA.sum. – Lema

The + is provided by the fact that there is a Monoid for T. If T is an Int Scalaz provides a Monoid[Int] where the append operation is defined using +. So the advantage of my solution is that it's a bit more generic because it extends to anything having an "addition-like" operation. – Opinion

@Opinion A minor mistake: a |+| zero = a for identity law:) – Thunderbolt

Hi Eric, thank you for your detailed answer. I will need some time to fully understand it since I am relatively new to fp. It seems to be a little bit complicated and I at the moment I would prefer to throw an exception – Chutney

Answer 2

You don't really need Scalaz for this. You can just flatten the list, which will convert it to List[Int], removing any items that were None. Then you can reduce it:

List(Some(1), None, Some(2), Some(3), None).flatten.reduce(_ + _) //returns 6: Int

Training

I had interpreted it as wanting to make the result None if any were None, but now that you mention, I'm not so sure I was right... – Pleasure

Very good point, I suppose the OP should specify whether he wants the sum to fail if at least one item is None, or to sum over items that have values, ignoring the Nones. – Training

Answer 3

scala> List(1, 2, 3).map(some).foldLeft(0 some) {
     |   case (r, c) => (r |@| c)(_ + _)
     | }
res180: Option[Int] = Some(6)

Lema

Answer 4

One option would be to sequence the whole list first, then fold it like regular:

val a: List[Option[Int]] = List(1, 2, 3) map (Some(_))
a.sequence map (_.foldLeft(0)(_+_))

Pleasure

Or, indeed, just a.sequence map {_.sum} – Earthaearthborn

Answer 5

With Scalaz's ApplicativeBuilder would be another option.

import scalaz._
import Scalaz._

List(1,2,3).map(_.some).foldl1((acc,v) => (acc |@| v) {_+_}) join

Molton

Answer 6

Found this somewhere a while ago, can't find the source anymore, but it has been working for me

 def sumOpt1(lst: List[Option[Int]]): Option[Int] = {
    lst.foldLeft(Option.empty[Int]) {
      case (prev, elem) =>
        (prev, elem) match {
          case (None, None) => None
          case (None, Some(el)) => Some(el)
          case (Some(p), None) => Some(p)
          case (Some(p), Some(el)) => Some(p + el)
        }
    }
  }

or

 def sumOpt2(lst: List[Option[Int]]): Option[Int] = {
    lst.foldLeft(Option.empty[Int]) {
      case (prev, elem) =>
        (prev, elem) match {
          case (None, None) => None
          case (p, el) => Some(p.getOrElse(0) + el.getOrElse(0))
        }
    }
  }

or

def sumOpt3(lst: List[Option[Int]]): Option[Int] = {
    lst.foldLeft(Option.empty[Int]) {
      case (prev, elem) =>
        (prev, elem) match {
          case (None, el) => el
          case (p, None) => p
          case (Some(p), Some(el)) => Some(p + el)
        }
    }
  }

Cai