Free.md

Free constructions

abstraction	free construction
Monoid	List, Vector
Functor	Yoneda, Coyoneda, Density, Codensity, Right Kan Extension, Left Kan Extension, Day Convolution
Applicative	FreeApplicative
Alternative	Free Alternative
Traversable	CoFree Traverse
Monad	Free Monads, Codensity, Right Kan Extension
Comonad	CoFree, Density
Profunctor	Profunctor CoYoneda, Profunctor Yoneda, Tambara, Pastro, Cotambara, Copastro, TambaraSum, PastroSum, CotambaraSum, CopastroSum, Closure, Environment, CofreeTraversing, FreeTraversing, Traversing
ProfunctorFunctor	Profunctor CoYoneda, Profunctor Yoneda, Tambara, Pastro, Cotambara, Copastro, TambaraSum, PastroSum, CotambaraSum, CopastroSum, Closure, Environment, CofreeTraversing, FreeTraversing
ProfunctorMonad	Pastro, Copastro, PastroSum, CopastroSum, Environment, FreeTraversing
ProfunctorComonad	Tambara, Cotambara, TambaraSum, CotambaraSum, Closure, CofreeTraversing
Strong	Tambara, Pastro, Traversing
Costrong	Cotambara, Copastro
Choice	TambaraSum, PastroSum
Cochoice	CotambaraSum, CopastroSum, Traversing
Closed	Closure, Environment
Traversing	CofreeTraversing, FreeTraversing
Arrow	Free Arrow

• Usage of Free construction in Haskell

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

• Resources
  • Cats docs
  • Why the free Monad isn’t free - Kelley Robinson: https://www.youtube.com/watch?v=wvNgoeZza2g
  • Beyond Free Monads - John DeGoes: https://www.youtube.com/watch?v=A-lmrvsUi2Y
  • Free as in Monads - Daniel Spiewak: https://www.youtube.com/watch?v=aKUQUIHRGec
  • Free Monoids and Free Monads - Rúnar Bjarnason (blog post)
  • (Haskell) Free Monoids in Haskell - Dan Doel (blog post)
  • (Haskell) Many Roads to Free Monads - Dan Doel (blog post)
  • (Haskell) Meta-programming with the Free Monad - John Wiegley (blog post)
  • (Haskell) Notes on Free monads - John Wiegley (blog post)
  • (Theory) nLab

Free Monad transformers

• Implementations: Haskell transformers-free Haskell free Purescript

• Resources

  • Free monad transformers - Gabriella Gonzalez (blog post)

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
}

• Resources
  • Cofree used to process events Kafka tenable/Kastle
  • Scala Comonad Tutorial, Part 2 - Rúnar Bjarnason (blog post)
  • scalaz (src Cofree)
  • Cofree Comonads and their Uses - λC 2018 - Nihil Shah (video)

Cofree Traverse

• Resources
  • Cofree Traversable Functors - Love Waern (paper)
  • KingoftheHomeless/Cofree-Traversable-Functors
  • The Cofree Traversable (Reddit)
  • Twitter discussion

Free Alternative

• Resources
  • Haskell free/Control.Alternative.Free
  • Structurally enforced Free Alternative, without left distributivity - SO
  • Routing With Cofree Comonad - Marcin Szamotulski (video) (slides) (repo)
  • Applicative Regular Expressions using the Free Alternative - Justin Le (blog pos)

Free Arrow

• Implementations

  • Purescript
  • Scala

• Resources

  • Building free arrows from components (blog post)