階乗とフィボナッチの両方で使えるhylomorphismを書いてみる

hylomorphism.sc

import cats.Functor
import cats.syntax.functor._

// hylomorphism -----------------
type Algebra[F[_],   B] = F[B] => B
type Coalgebra[F[_], A] = A    => F[A]

def hylomorphism[F[_]: Functor, A, B](
    alg:   Algebra[F, B],
    coalg: Coalgebra[F, A])(seed: A): B =
  alg(coalg(seed) map hylomorphism(alg, coalg))

type Pair[X, A] = Option[(X, A)]
def algebra[A, B, C](c: C, f: (A, B) => C)(o: Pair[A, B]): C = o.fold(c)(f.tupled)
def coalgebra[A, B](g: A => (B, A), p: A => Boolean)(n: A): Pair[B, A] =
  if (p(n)) None else Option(g(n))

//consHylo -----------------
implicit def consHyloFunc[X]: Functor[Pair[X, ?]] = new Functor[Pair[X, ?]] {
  override def map[A, B](fa: Pair[X, A])(f: A => B): Pair[X, B] =
    fa.map(p => (p._1, f(p._2)))
}
def consHylo[A, B, C](c: C, f: (B, C) => C)(g: A => (B, A), p: A => Boolean): A => C =
  hylomorphism[Pair[B, ?], A, C](algebra[B, C, C](c, f), coalgebra(g, p))

//treeHylo -----------------
type MaybeTree[A] = Pair[A, A]

implicit val treeHyloFunctor: Functor[MaybeTree] = new Functor[MaybeTree] {
  override def map[A, B](fa: MaybeTree[A])(f: A => B): MaybeTree[B] =
    fa.map(p => (f(p._1), f(p._2)))
}
def treeHylo[A, C](c: C, f: (C, C) => C)(g: A => (A, A), p: A => Boolean): A => C =
  hylomorphism[MaybeTree, A, C](algebra(c, f), coalgebra(g, p))

//factorial -----------------
val fact = consHylo[Int, Int, Int](1, _ * _)(n => (n, n - 1), _ == 0)
(0 to 5).toList.map(fact)
consHylo[Int, Long, String]("1", (r1, r2) => s"$r1 * $r2")(n => (n, n - 1), _ == 0)(10)

// fibonacchi -----------------
val fib = treeHylo[Int, Long](1, _ + _)(x => (x - 1, x - 2), _ < 2)
(0 to 5).toList.map(fib)

val fib2 = treeHylo[Int, String]("1", (l, r) => s"$l$r")(x => (x - 1, x - 2), _ < 2)
treeHylo[Int, String]("1", (l, r) => s"$l$r")(x => (x - 1, x - 2), _ < 2)(5)

sealed trait Tree
case class Leaf(a: Long) extends Tree
case class Branch[A](l: Tree, r: Tree) extends Tree

treeHylo[Int, Tree](Leaf(1), (l, r) => Branch(l, r))(x => (x - 1, x - 2), _ < 2)(4)