Scala的PartialFunction可以成为Monoid吗？

Question

我认为PartialFunction可以成为Monoid。我的思路正确吗？

import scalaz._
import scala.{PartialFunction => -->}

implicit def partialFunctionSemigroup[A,B]:Semigroup[A-->B] = new Semigroup[A-->B]{
  def append(s1: A-->B, s2: => A-->B): A-->B = s1.orElse(s2)
}

implicit def partialFunctionZero[A,B]:Zero[A-->B] = new Zero[A-->B]{
  val zero = new (A-->B){
    def isDefinedAt(a:A) = false
    def apply(a:A) = sys.error("error")
  }
}

但现在的版本Scalaz(6.0.4)没有包含它。有什么原因导致它没有被包含进去吗？

- Kenji Yoshida

---

我假设你已经知道Function1在组合下是一个幺半群吗？ - Daniel C. Sobral

@dcsobral Function1[A, A]，也被称为 Endo[A]，是什么。 - retronym

Answer 1

让我们从不同的角度来看这个问题。

PartialFunction[A, B] 等同于 A => Option[B]。（实际上，为了能够检查给定的 A 是否定义，而不触发 B 的求值，您需要 A => LazyOption[B]）

因此，如果我们能找到一个 Monoid[A => Option[B]]，我们就证明了你的断言。

给定 Monoid[Z]，我们可以按照以下方式形成 Monoid[A => Z]：

implicit def readerMonoid[Z: Monoid] = new Monoid[A => Z] {
   def zero = (a: A) => Monoid[Z].zero
   def append(f1: A => Z, f2: => A => Z) = (a: A) => Monoid[Z].append(f1(a), f2(a))
}

如果我们使用Option[B]作为我们的Z，那么我们有哪些Monoid呢？Scalaz 提供了三种。其中主要实例需要一个Semigroup[B]。

implicit def optionMonoid[B: Semigroup] = new Monoid[Option[B]] {
  def zero = None
  def append(o1: Option[B], o2: => Option[B]) = o1 match {
    case Some(b1) => o2 match {
       case Some(b2) => Some(Semigroup[B].append(b1, b2)))
       case None => Some(b1)
    case None => o2 match {
       case Some(b2) => Some(b2)
       case None => None
    }
  }
}

使用这个：

scala> Monoid[Option[Int]].append(Some(1), Some(2))
res9: Option[Int] = Some(3)

但这并不是合并两个 Options 的唯一方法。我们可以选择仅选取两者中的第一个或最后一个，而不是在它们都是 Some 时附加两者的内容。为了实现这个目的，我们使用一种被称为标记类型的技巧创建了一个不同的类型。这在精神上类似于 Haskell 的 newtype。

scala> import Tags._
import Tags._

scala> Monoid[Option[Int] @@ First].append(Tag(Some(1)), Tag(Some(2)))
res10: scalaz.package.@@[Option[Int],scalaz.Tags.First] = Some(1)

scala> Monoid[Option[Int] @@ Last].append(Tag(Some(1)), Tag(Some(2)))
res11: scalaz.package.@@[Option[Int],scalaz.Tags.Last] = Some(2)

Option[A] @@ First是通过其Monoid附加的，使用与您示例相同的orElse语义。

因此，将所有这些放在一起：

scala> Monoid[A => Option[B] @@ First]
res12: scalaz.Monoid[A => scalaz.package.@@[Option[B],scalaz.Tags.First]] = 
       scalaz.std.FunctionInstances0$$anon$13@7e71732c

- retronym

---

非常感谢！我之前没有意识到PartialFunction与A => LazyOption[B]是同构的。 - Kenji Yoshida

谢谢@retronym！标记类型只在scalaz-seven中可用，对于之前的版本需要使用FirstOption特性，我说得对吗？ - lester

@lester 是的，完全正确。标记类型有一些尖锐的边缘，不幸的是，在我们推荐它们之前，我们可能需要更好的scalac支持。例如：List(Tag(1))会产生一个ClassCastException，因为编译器的一部分将参数视为对象数组，而后面的一部分将其视为原始数组。 - retronym

Answer 2

不错，符合（非交换）幺半群的要求。这是个有趣的想法。你想支持哪些使用案例？

- Dave Griffith

---

@Heiko 抱歉，但您的陈述显然是错误的。即使答案是错误的，它也远非清晰明了（至少对我来说）。 - ziggystar

Answer 3

你的零元素肯定违反了单位元素公理，但我认为单位（部分）函数应该没问题。

你的追加操作也不符合幺半群法则，但是你可以使用andThen（组合）代替orElse。但这只适用于A == B的情况：

implicit def partialFunctionSemigroup[A]: Semigroup[A --> A] = new Semigroup[A --> A] {
  def append(s1: A --> A, s2: => A --> A): A-->A = s1 andThen s2
}

implicit def partialFunctionZero[A]: Zero[A --> A] = new Zero[A --> A] {
  val zero = new (A --> A) {
    def isDefinedAt(a:A) = true
    def apply(a:A) = a
  }
}

- Heiko Seeberger

---

你能给出一个反例吗？ - ziggystar

对于哪些 e 和 a 违反了它？ - ziggystar

你的版本是一个幺半群。OP的版本也是一个幺半群。 - Didier Dupont

我真该感到羞愧：我曾认为抛出异常会违反身份验证，但由于 isDefined 返回 false，事实并非如此。 - Heiko Seeberger

(S1 orElse zero) == (zero orElse S1) == S1，那么它有什么问题呢？如果 S1 被定义了，那么结果就是 S1。如果 S1 是 zero（即未被定义），那么结果就是 zero。 - Daniel C. Sobral