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 ?

Kenji Yoshida
  • 3,108
  • 24
  • 39

3 Answers3

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
retronym
  • 54,768
  • 12
  • 155
  • 168
  • Thanks a lot ! I hadn't realized that PartialFunction is isomorphic to A => LazyOption[B] – Kenji Yoshida Jan 31 '12 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 Jan 31 '12 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 Feb 01 '12 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?

Dave Griffith
  • 20,435
  • 3
  • 55
  • 76
  • 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 Jan 30 '12 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
  }
}
Heiko Seeberger
  • 3,702
  • 21
  • 20