Commutative Semigroup on Sealed Trait

I’m trying to implement a commutative Semigroup.combine for a sealed trait, but this seems to result in a lot of code duplication. Here is a very simplified example:

sealed trait Foo

case class Adjective(x: String) extends Foo
case class Subject(x: String) extends Foo

def combine(f1: Foo, f2: Foo): Foo = {
  (f1, f2) match {
    case (Adjective(a), Subject(s)) => Subject(a + s)
    case (Subject(s), Adjective(a)) => Subject(a + s)

    case _ => ???

The reason I want this is that I’m analyzing an AST where terms can appear in arbitrary order, but build up to a type the same way nonetheless.

What I’ve tried:

  • Writing a macro that rewrites the Tree of the match expression to also try reverse order, but this results in the exhaustiveness check reporting false positives, even if I add a case _.

  • Creating a typeclass T[A <: Foo, B <: Foo] with combine(a: A, b: B): Foo and a given that reverses the order of parameters, but I can’t figure out how to derive a Semigroup from that.

Is there some construct in Scala I can use to encode this behaviour in an elegant way?

Actually my first post here,

Just my 5cents opinion, you could do

def combine(f1: Foo, f2: Foo, rec:Boolean = false): Foo = {
  (f1, f2) match {
    case (Adjective(a), Subject(s)) => a + s

    case (a, b) if ! rec => combine(f2, f1, true)

We can just re-run the match swapping the args, careful to not create a recursion loop.

Unfortunately it also won’t check exhaustiveness correctly.

You can also play with Extractor Objects | Tour of Scala | Scala Documentation “unapply” I think, never did that, but I think you could create an extractor that wouldn’t take the order of the input in consideration. (To be Validated)

What type is your semigroup? If you can’t combine all values of your semigroup, it’s not a semigroup. It’s not even a magma. Please look up the definition of semigroup.

Unfortunately the way extractors work, it’s not possible to “duplicate” a pattern given at the match-site through the extractor (as far as I know). Extractors work in the other direction.

My type obeys the laws of a Semigroup just fine. I can combine any two given values. I just don’t want to write a bunch of patterns twice because the order they appear in is irrelevant.

1 Like