semi-rng.scala

trait SemiRng[S] {
  def add(lhs: S, rhs: S): S
  def mult(lhs: S, rhs: S): S
}

object SemiRng {
  opaque type Add[S] = S
  object Add {
    def apply[S](s: S): Add[S] = s
    def (a: Add[S]) unwrap[S]: S = a
  }
  instance AddSemigroup[S] with (S: SemiRng[S]) of Semigroup[Add[S]] {
    import Add.unwrap
    override def append(lhs: Add[S], rhs: Add[S]): Add[S] = Add(S.add(lhs.unwrap, rhs.unwrap))
  }
  instance RunAdd[S] of RunDSL[Add[S], S] {
    import Add.unwrap
    override def runDSL(a: Add[S]): S = a.unwrap
  }


  opaque type Mult[S] = S
  object Mult {
    def apply[S](s: S): Mult[S] = s
    def (a: Mult[S]) unwrap[S]: S = a
  }
  instance MultSemigroup[S] with (S: SemiRng[S]) of Semigroup[Mult[S]] {
    import Mult.unwrap
    override def append(lhs: Mult[S], rhs: Mult[S]): Mult[S] = Mult(S.mult(lhs.unwrap, rhs.unwrap))
  }
  instance RunMult[S] of RunDSL[Mult[S], S] {
    import Mult.unwrap
    override def runDSL(a: Mult[S]): S = a.unwrap
  }
}

semigroup-to-right.scala

@FunctionalInterface
trait Semigroup[S] {
  def append(lhs: S, rhs: S): S
}

object Semigroup {
  def (lhs: S) ++ [S](rhs: S) with (S: Semigroup[S]): S = S.append(lhs, rhs)

  trait RewriteToRight[S] {
    def toLeftOf(rhs: S): S
    def terminal: S
  }

  @FunctionalInterface
  def RewriteToRightTerminal[S](term: S) with (S: Semigroup[S]): RewriteToRight[S] = new {
    override def toLeftOf(rhs: S): S = S.append(terminal, rhs)
    override def terminal: S = term
  }

  instance RewriteToRightAppend[S] of Semigroup[RewriteToRight[S]] {
    override def append(lhs: RewriteToRight[S], rhs: RewriteToRight[S]): RewriteToRight[S] = new {
      override def terminal: S = lhs.toLeftOf(rhs.terminal)
      override def toLeftOf(r: S): S = lhs.toLeftOf(rhs.toLeftOf(r))
    }
  }

  trait RewriteToLeft[S] {
    def toRightOf(lhs: S): S
    def terminal: S
  }

  @FunctionalInterface
  def RewriteToLeftTerminal[S](term: S) with (S: Semigroup[S]): RewriteToLeft[S] = new {
    override def toRightOf(lhs: S): S = S.append(lhs, terminal)
    override def terminal: S = term
  }

  instance RewriteToLeftAppend[S] of Semigroup[RewriteToLeft[S]] {
    override def append(lhs: RewriteToLeft[S], rhs: RewriteToLeft[S]): RewriteToLeft[S] = new {
      override def terminal: S = rhs.toRightOf(lhs.terminal)
      override def toRightOf(l: S): S = rhs.toRightOf(lhs.toRightOf(l))
    }
  }
}