Lifting arbitrary semirings to alternatives via const...

alternatives_as_semirings.scala

trait Semiring[A] {
  def zero: A
  def plus(x: A, y: A): A 
  def one: A
  def times(x: A, y: A): A
}

trait Alternative[F[_]] {
  def pure[A](x: A): F[A]
  def product[A, B](fa: F[A])(fb: F[B]): F[(A, B)]
  def empty[A]: F[A]
  def combineK[A](x: F[A], y: F[A]): F[A]
}

final case class Const[A, B](getConst: A) {
  /**
   * changes the type of the second type parameter
   */
  def retag[C]: Const[A, C] =
    this.asInstanceOf[Const[A, C]]
}

implicit def liftSemiring[C: Semiring]: Alternative[Const[C, ?]] = new Alternative[Const[C, ?]] {
  def pure[A](x: A): Const[C, A] = Const(Semiring[C].zero).retag[A]
  
  def product[A, B](fa: Const[C, A])(fb: Const[C, B]): Const[C, (A, B)] =
    Const(Semiring[C].times(ff.getConst, fa.getConst)).retag[(A, B)]
  
  def empty[A]: Const[C, A] = Const(Semiring[C].one).retag[A]

  def combineK[A](x: Const[C, A], y: Const[C, A]): Const[C, A] =
    Const(Semiring[C].add(x.getConst, y.getConst)).retag[A]
}

implicit val semiringForBoolean = new Semiring[Boolean] {
  def one: Boolean = true
  
  def times(x: Boolean, y: Boolean): Boolean = x && y
  
  def zero: Boolean = false
  
  // I actually think this is a full ring, but we don't need that power, could just as well use ||
  def plus(x: Boolean, y: Boolean): Boolean = x ^ y
}

implicit val constAlternativeSemiring: Alternative[Const[Boolean, ?]] = liftSemiring[Boolean]

Alternative[Const[Boolean, ?]].combineK(Const(true), Const(false)) // -> Const(true)
Alternative[Const[Boolean, ?]].product(Const(true), Const(false))  // -> Const(false)