Cata's, Phi's, Mu's Oh My's

fold_Fix.scala

package com.emilypi.scalaupnorth.fold

/**
  * Created by emilypi on 5/18/17.
  */
case class Mu[F[_]](unFix: F[Mu[F]])

fold_Functor.scala

package com.emilypi.scalaupnorth.fold

/**
  * Created by emilypi on 5/18/17.
  */
trait Functor[F[_]] {
  def fmap[A, B](f: A => B)(fa: F[A]): F[B]
}

fold_GeneralizedFold.scala

package com.emilypi.scalaupnorth.fold

/**
  * Created by emilypi on 5/18/17.
  */
object GeneralizedFold {
  import Instances._

  def nil[H] = Mu[ListF[H, ?]](NilF)

  def cons[H] = (h: H, t: Mu[ListF[H, ?]]) => Mu[ListF[H, ?]](Cons(h, t))

  def cata[B, F[_] : Functor](phi: F[B] => B)(fix: Mu[F]): B =
    phi(implicitly[Functor[F]].fmap(cata[B, F](phi))(fix.unFix))

  def sumListF = cata[Int, ListF[Int, ?]]{ case Cons(h, t) => h + t; case NilF => 0 } _
  def countListF = cata[Int, ListF[Int, ?]]{ case Cons(h, t) => 1 + t; case NilF => 0 } _


}

fold_Instances.scala

package com.emilypi.scalaupnorth.fold

/**
  * Created by emilypi on 5/18/17.
  */
object Instances {

  implicit def listFFunctor[H] = new Functor[ListF[H, ?]] {
    def fmap[A, B](f: A => B)(fa: ListF[H, A]): ListF[H, B] =
      fa match {
        case NilF => NilF
        case Cons(x, xs) => Cons(x, f(xs))
      }
  }
}

fold_ListF.scala

package com.emilypi.scalaupnorth.fold

import scala.annotation.tailrec

/**
  * Created by emilypi on 5/18/17.
  */
sealed trait ListF[+H, +T]
final case class Cons[H, +T](head: H, tail: T) extends ListF[H, T]
final case object NilF extends ListF[Nothing, Nothing]