Manuel Schmidt - 8 months ago 38

Scala 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?

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.

Answer

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 `None`

s or "failing fast".