Свободная монада

Формальное определение

Свободная монада обеспечивает:

абстрактное синтаксическое дерево (AST - abstract syntax tree) для выражения монадических операций
API для написания интерпретаторов, которые придают значение этому AST

Определение в виде кода на Scala

sealed trait Free[F[_], A]
final case class Unit[F[_], A](a: A) extends Free[F, A]
final case class FlatMap[F[_], A, B](a: Free[F, A], fx: A => Free[F, B]) extends Free[F, B]

given freeFunctor[F[_]]: Functor[[X] =>> Free[F, X]] with
  extension [A](as: Free[F, A])
    override def map[B](f: A => B): Free[F, B] =
      FlatMap(as, a => Unit(f(a)))

given freeMonad[F[_]]: Monad[[X] =>> Free[F, X]] with
  override def unit[A](a: => A): Free[F, A] = Unit(a)

  extension [A](fa: Free[F, A]) override def flatMap[B](f: A => Free[F, B]): Free[F, B] = FlatMap(fa, f)

Ссылки: