Question

I thought PartialFunction can be Monoid. Is my thought process correct ? For example,

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

But current version Scalaz(6.0.4) is not included it. Is there a reason for something not included ?

Was it helpful?

Solution

Let's shine a different light on this.

PartialFunction[A, B] is isomorphic to A => Option[B]. (Actually, to be able to check if it is defined for a given A without triggering evaluation of the B, you would need A => LazyOption[B])

So if we can find a Monoid[A => Option[B]] we've proved your assertion.

Given Monoid[Z], we can form Monoid[A => Z] as follows:

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

So, what Monoid(s) do we have if we use Option[B] as our Z? Scalaz provides three. The primary instance requires a 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
    }
  }
}

Using this:

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

But that's not the only way to combine two Options. Rather than appending the contents of the two options in the case they are both Some, we could simply pick the first or the last of the two. Two trigger this, we create a distinct type with trick called Tagged Types. This is similar in spirit to Haskell's 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, appended through it's Monoid, uses the same orElse semantics as your example.

So, putting this all together:

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

OTHER TIPS

No, this looks good, satisfying both the requirements for (non-commutative) Monoid. Interesting idea. What use case are you trying to support?

Your zero certainly violates the axiom for the identity element, but I think the identity (partial) function would be OK.

Your append also doesn't fulfill the Monoid laws, but instead of orElse you could call andThen (composition). But this would only work for 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
  }
}
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top