sbtb2019.scala

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)
}