14

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 ?

2
  • I assume you are aware that Function1 is a monoid under composition? Commented Jan 30, 2012 at 20:29
  • 1
    @dcsobral Function1[A, A], aka Endo[A], is.
    – retronym
    Commented Jan 30, 2012 at 22:39

3 Answers 3

28

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
3
  • Thanks a lot ! I hadn't realized that PartialFunction is isomorphic to A => LazyOption[B] Commented Jan 31, 2012 at 15:49
  • Thanks, @retronym! Tagged Types are available only in scalaz-seven, for previous version it's necessary to use FirstOption trait, am I right?
    – lester
    Commented Jan 31, 2012 at 16:05
  • 2
    @lester yep, exactly. Tagged Types have a few sharp edges, unfortunately, we might need better scalac support before we recommend them. Example is: List(Tag(1)) gives a ClassCastException as one part of the compiler treats the arguments as an object array, and a later part as a primitive array.
    – retronym
    Commented Feb 1, 2012 at 14:09
2

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

1
  • 1
    @Heiko Sorry, but your statement is clearly wrong. Even if the answer is wrong it is far from clear (at least to me).
    – ziggystar
    Commented Jan 30, 2012 at 19:43
0

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
  }
}
5
  • Can you give a counter-example?
    – ziggystar
    Commented Jan 30, 2012 at 19:11
  • For which e and a is it violated?
    – ziggystar
    Commented Jan 30, 2012 at 19:40
  • Your version is a monoid. The version of the OP is a monoid too. Commented Jan 30, 2012 at 19:43
  • 1
    Shame on me: I thought that throwing an exception would violate identity, but as isDefined will return false this is not the case. Commented Jan 30, 2012 at 19:52
  • (S1 orElse zero) == (zero orElse S1) == S1, so what's being violated about it? If S1 is defined, then the result is S1. If S1 is zero (ie, not defined), the result is zero. Commented Jan 30, 2012 at 20:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.