Skip to content

Instantly share code, notes, and snippets.

@andyscott
Created November 13, 2019 02:39
Show Gist options
  • Save andyscott/39c9d241b19826cec0db071f53c95775 to your computer and use it in GitHub Desktop.
Save andyscott/39c9d241b19826cec0db071f53c95775 to your computer and use it in GitHub Desktop.
import cats._
import cats.implicits._
type Coalgebra[F[_], A] = A => F[A]
type Algebra[F[_], A] = F[A] => A
type ListF[A, B] = Option[(A, B)]
implicit def functorListF[A]: Functor[ListF[A, ?]] =
Functor[Option].compose[(A, ?)]
def projectList[E]: Coalgebra[ListF[E, ?], List[E]] = _ match {
case Nil => None
case head :: tail => Some((head, tail))
}
def embedList[E]: Algebra[ListF[E, ?], List[E]] = _ match {
case None => Nil
case Some((head, tail)) => head :: tail
}
val rangeOp: Coalgebra[ListF[Int, ?], Int] =
n => if (n <= 0) None else Some((n, n - 1))
val productOp: Algebra[ListF[Int, ?], Int] = _ match {
case None => 1
case Some((x, y)) => x * y
}
def foldRight[E, B](f: Option[(E, B)] => B): List[E] => B =
new (List[E] => B) { kernel =>
def apply(input: List[E]): B = input match {
case Nil => f(None)
case head :: tail => f(Some((head, kernel(tail))))
}
}
def unfold[E, A](f: A => Option[(E, A)]): A => List[E] =
new (A => List[E]) { kernel =>
def apply(input: A): List[E] = f(input) match {
case None => Nil
case Some((e, a)) => e :: kernel(a)
}
}
def cata[F[_]: Functor, S, B](algebra: Algebra[F, B])(project: Coalgebra[F, S]): S => B =
new (S => B) { kernel =>
def apply(input: S): B =
algebra(project(input).fmap(kernel))
}
def ana[F[_]: Functor, A, S](coalgebra: Coalgebra[F, A])(embed: Algebra[F, S]): A => S =
new (A => S) { kernel =>
def apply(input: A): S =
embed(coalgebra(input).fmap(kernel))
}
def hylo[F[_]: Functor, A, B](algebra: Algebra[F, B], coalgebra: Coalgebra[F, A]): A => B =
new (A => B) { kernel =>
def apply(input: A): B =
algebra(coalgebra(input).fmap(kernel))
}
{
val range: Int => List[Int] = unfold(rangeOp)
val product: List[Int] => Int = foldRight(productOp)
val factorial: Int => Int = product compose range
factorial(4)
}
{
val range: Int => List[Int] = ana(rangeOp)(embedList[Int])
val product: List[Int] => Int = cata(productOp)(projectList[Int])
val factorial: Int => Int = product compose range
factorial(4)
}
{
val factorial: Int => Int = hylo(productOp, rangeOp)
factorial(4)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment