Annihilator -- Structure with element that "annihilates" any other element of the set

[theamytran]

There is a concept called the Annihilator (wikipedia) which basically defines the multiplicative zero of a set. Here's a blog post that shows an example Annihilator: http://underscore.io/blog/posts/2015/07/02/annihilators-in-scala.html

I'm interested in such a type class included here. A sample use case would be set intersection: consider the following pieces of code, reflecting use of a Monoid[Option[?]].

Hypothetical monoid

implicit object IntSetIntersectionMonoid extends Monoid[Set[Int]] {
   def append(a: Set[Int], b: => Set[Int]): Set[Int] = a intersect b
   def identity = // the universe. This is impossible, which is why we need the annihilator to exist
   def zero = Set()
}

Existing monoid:

val a = Set(1, 2).some
val b = none

a |+| b // returns Set(1, 2)

With annihilation:

val a = Set(1, 2).some
val b = none

a |*| b // returns empty set

There are possibly many other examples other than set intersection that may be useful. Also, apologies if anything is unclear. This is my first time using GitHub issues. Thanks!

[non]

Hi @theamytran,

So it sounds like your proposal is something like this?

trait Annihilating[A] {
  def combine(x: A, y: A): A
  def annihilator: A
}

// and then elsewhere
class AnnihilatingForSet[A: Semigroup] extends Annihilating[Set[A]] {
  def combine(x: Set[A], y: Set[A]): Set[A] = x & y
  def annihilator: Set[A] = Set.empty[A]
}

val x = Set(1,2,3)
val y = Set.empty[Int]
AnnihilatingForSet[Int].combine(x, y) // returns Set()

Currently it would be possible to do something similar by defining a Semiring[Set[A]] using empty sets, unions, and intersections (which we currently have: https://github.com/typelevel/algebra/blob/master/core/src/main/scala/algebra/instances/set.scala#L26).

I guess I have a few questions for the group:

1. Does anyone know of any algorithms or structures that need only multiplication and zero?
2. How often do people encounter semigroups which can't be monoids but could be annihilators?
3. Would it make more sense to put this in the semigroup hierarchy or keep it alone?

My 2¢ is that it seems reasonable to add AnnihilatingSemigroup (and AnnihilatingMonoid) if we can think of more use cases that would benefit from having them. The set example is less compelling to me only because we already have Semiring[Set[A]].

[theamytran]

Here's another use case: interval intersection. https://gist.github.com/kenbot/1c37f10cd2ac8de2e988

[johnynek]

IntervalSets can also have Semirings as a note.

@theamytran do you have an algorithm in mind that you would write that uses a annihilation in the abstract?