使用 Applicative Functor 对选项列表求和 [英] Summing a List of Options with Applicative Functors

问题描述

我有一个 List[Option[Int]] 并且想使用 applicative functors 对它求和.从 [1] 我明白它应该是这样的

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.

非常感谢

[1] 如何在 Scala 中组合 Option 值?

编辑

感谢所有精彩的回答.

如果列表中有任何 None，我希望它返回 None.我正在尝试用 Option/Either 替换 Null/Exception，看看我是否可以生成一些可用的代码.

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.

某些函数会填满我的列表，我想尽可能简单地进一步处理它，而不检查其中一个元素是否为 None.它应该像异常一样工作，我不必在我的函数中检查它，而是让调用者来处理它.

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.

推荐答案

如果您有 Option[T] 并且有 Monoid 用于 Tcode>，然后有一个 Monoid[Option[T]]:

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

一旦你配备了这个，你就可以使用sum(比@missingfaktor建议的foldMap(identity)更好):

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)

更新

我们实际上可以使用 applicatives 来简化上面的代码:

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,...

更新2

问题澄清让我意识到上面的UPDATE是不正确的！

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

首先，重构后的 optionTIsMonoid 并不等同于第一个定义，因为第一个定义将跳过 None 值，而第二个定义将返回 None 只要输入列表中有 None .但在那种情况下，这不是 Monoid！实际上，Monoid[T] 必须遵守 Monoid 定律，并且 zero 必须是 身份 元素.

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.

我们应该:

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

但是当我使用 Applicative 为 Option 提出 Monoid[Option[T]] 的定义时，情况并非如此:

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

修复并不难，我们需要修改zero的定义:

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(_, _))
  }

在这种情况下，我们将有(使用 T 作为 Int):

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

证明身份法得到验证(我们还应该验证associative法得到遵守，...).

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

现在我们有 2 个 Monoid[Option[T]] 我们可以随意使用，这取决于我们在对列表求和时想要的行为:跳过 Nones 或快速失败".

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".

这篇关于使用 Applicative Functor 对选项列表求和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！