Free.md

December 5, 2024 · View on GitHub

Free constructions

abstractionfree construction
MonoidList, Vector
FunctorYoneda, Coyoneda, Density, Codensity, Right Kan Extension, Left Kan Extension, Day Convolution
ApplicativeFreeApplicative
AlternativeFree Alternative
TraversableCoFree Traverse
MonadFree Monads, Codensity, Right Kan Extension
ComonadCoFree, Density
ProfunctorProfunctor CoYoneda, Profunctor Yoneda, Tambara, Pastro, Cotambara, Copastro, TambaraSum, PastroSum, CotambaraSum, CopastroSum, Closure, Environment, CofreeTraversing, FreeTraversing, Traversing
ProfunctorFunctorProfunctor CoYoneda, Profunctor Yoneda, Tambara, Pastro, Cotambara, Copastro, TambaraSum, PastroSum, CotambaraSum, CopastroSum, Closure, Environment, CofreeTraversing, FreeTraversing
ProfunctorMonadPastro, Copastro, PastroSum, CopastroSum, Environment, FreeTraversing
ProfunctorComonadTambara, Cotambara, TambaraSum, CotambaraSum, Closure, CofreeTraversing
StrongTambara, Pastro, Traversing
CostrongCotambara, Copastro
ChoiceTambaraSum, PastroSum
CochoiceCotambaraSum, CopastroSum, Traversing
ClosedClosure, Environment
TraversingCofreeTraversing, FreeTraversing
ArrowFree Arrow

Free Applicative

  • Implementations: Scalaz 7 Haskell

  • Resources

    • Cats docs
    • Free Applicative Functors - Paolo Capriotti, Ambrus Kaposi (paper)
    • Move Over Free Monads: Make Way for Free Applicatives! - John deGoes (video)
    • Flavours of free applicative functors - Roman Cheplyaka (blog post)

Free Monads

ADT (sometimes implemented using Fix point data type)

sealed trait FreeMonad[F[_], A]
final case class Return[F[_], A](a: A) extends FreeMonad[F, A]
final case class Suspend[F[_], A](s: F[FreeMonad[F,A]]) extends FreeMonad[F,A]

that form a Monad, if F is a functor

def freeMonad[F[_]](implicit FF: Functor[F]): Monad[FreeMonad[F, *]] = new Monad[FreeMonad[F, *]] {
  def flatMap[A, B](ma: FreeMonad[F, A])(f: A => FreeMonad[F, B]): FreeMonad[F, B] =
    ma match {
      case Return(a) => f(a)
      case Suspend(m) => Suspend{
        def ff: FreeMonad[F, A] => FreeMonad[F, B] = x => flatMap(x)(f)
        FF.map(m)(ff)
      }
  }
  def pure[A](a: A): FreeMonad[F, A] = Return(a)
}

Free Monad transformers

Cofree

Create comonad for any given type A. It is based on rose tree (multiple nodes, value in each node) where List is replaced with any Functor F. Functor F dedicdes how Cofree comonad is branching.

case class Cofree[A, F[_]](extract: A, sub: F[Cofree[A, F]])(implicit functor: Functor[F]) {
  def map[B](f: A => B): Cofree[B, F] = Cofree(f(extract), functor.map(sub)(_.map(f)))
  def duplicate: Cofree[Cofree[A, F], F] = Cofree(this, functor.map(sub)(_.duplicate))
  def extend[B](f: Cofree[A, F] => B): Cofree[B, F] = duplicate.map(f) // coKleisi composition
}

Cofree Traverse

Free Alternative

Free Arrow