Commutative Semigroup on Sealed Trait

Question
1

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?

2

Hello,
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.

3

Unfortunately it also won’t check exhaustiveness correctly.

4

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)

5

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.

6

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