Last active
November 9, 2018 18:57
-
-
Save stephen-lazaro/a7186312c455fd2586b6a979c1c95cd2 to your computer and use it in GitHub Desktop.
Lifting arbitrary semirings to alternatives via const...
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment