Free Monads

sealed abstract class Free[S[_], A] extends Product with Serializable

// Construction
def pure[S[_], A](a: A): Free[S, A]
def liftF[F[_], A](value: F[A]): Free[F, A]
def roll[F[_], A](value: F[Free[F, A]]): Free[F, A]
def defer[F[_], A](value: => Free[F, A]): Free[F, A]

// Monadic Operations
def map[B](f: A => B): Free[S, B]
def flatMap[B](f: A => Free[S, B]): Free[S, B]

// Transformation
def mapK[T[_]](f: S ~> T): Free[T, A]
def compile[T[_]](f: FunctionK[S, T]): Free[T, A]

// Execution
def foldMap[M[_]](f: FunctionK[S, M])(implicit M: Monad[M]): M[A]
def run(implicit S: Comonad[S]): A
def runM[M[_]](f: S[Free[S, A]] => M[Free[S, A]])(implicit S: Functor[S], M: Monad[M]): M[A]
def runTailRec(implicit S: Monad[S]): S[A]

// Evaluation
def step: Free[S, A]
def resume(implicit S: Functor[S]): Either[S[Free[S, A]], A]
def go(f: S[Free[S, A]] => Free[S, A])(implicit S: Functor[S]): A
def fold[B](r: A => B, s: S[Free[S, A]] => B)(implicit S: Functor[S]): B

// Injection
def inject[G[_]](implicit ev: InjectK[S, G]): Free[G, A]

// Natural transformations
def mapK[F[_], G[_]](fk: FunctionK[F, G]): FunctionK[Free[F, ?], Free[G, ?]]
def foldMap[F[_], M[_]: Monad](fk: FunctionK[F, M]): FunctionK[Free[F, ?], M]

// Injection helpers
def inject[F[_], G[_]]: FreeInjectKPartiallyApplied[F, G]
def liftInject[G[_]]: FreeLiftInjectKPartiallyApplied[G]
def injectRoll[F[_], G[_], A](ga: G[Free[F, A]])(implicit I: InjectK[G, F]): Free[F, A]
def match_[F[_], G[_], A](fa: Free[F, A])(implicit F: Functor[F], I: InjectK[G, F]): Option[G[Free[F, A]]]

implicit def catsFreeMonadForFree[S[_]]: Monad[Free[S, ?]]
implicit def catsFreeDeferForFree[S[_]]: Defer[Free[S, ?]]
implicit def catsFreeFoldableForFree[F[_]](implicit foldableF: Foldable[F]): Foldable[Free[F, ?]]
implicit def catsFreeTraverseForFree[F[_]](implicit traversableF: Traverse[F]): Traverse[Free[F, ?]]

// Define your domain-specific operations
sealed trait ConsoleA[A]
case class WriteLine(line: String) extends ConsoleA[Unit]
case class ReadLine() extends ConsoleA[String]

// Create type alias for convenience
type Console[A] = Free[ConsoleA, A]

// Smart constructors
def writeLine(line: String): Console[Unit] = liftF(WriteLine(line))
def readLine(): Console[String] = liftF(ReadLine())

val program: Console[String] = for {
  _    <- writeLine("What's your name?")
  name <- readLine()
  _    <- writeLine(s"Hello, $name!")
} yield name

import cats.Id
import cats.arrow.FunctionK

// Interpreter to Id (for testing)
val testInterpreter = new FunctionK[ConsoleA, Id] {
  def apply[A](fa: ConsoleA[A]): Id[A] = fa match {
    case WriteLine(line) => println(line)
    case ReadLine()      => "Test User"
  }
}

// Interpreter to IO
import cats.effect.IO

val ioInterpreter = new FunctionK[ConsoleA, IO] {
  def apply[A](fa: ConsoleA[A]): IO[A] = fa match {
    case WriteLine(line) => IO(println(line))
    case ReadLine()      => IO(scala.io.StdIn.readLine())
  }
}

// Run with test interpreter
val testResult: String = program.foldMap(testInterpreter)

// Run with IO interpreter  
val ioResult: IO[String] = program.foldMap(ioInterpreter)

import cats.free.InjectK

sealed trait LogA[A]
case class Log(message: String) extends LogA[Unit]

class ConsoleOps[F[_]](implicit I: InjectK[ConsoleA, F]) {
  def writeLine(line: String): Free[F, Unit] = Free.liftInject[F](WriteLine(line))
  def readLine(): Free[F, String] = Free.liftInject[F](ReadLine())
}

class LogOps[F[_]](implicit I: InjectK[LogA, F]) {
  def log(message: String): Free[F, Unit] = Free.liftInject[F](Log(message))
}

// Use with coproduct
import cats.data.Coproduct
type App[A] = Coproduct[ConsoleA, LogA, A]

def program[F[_]](implicit C: ConsoleOps[F], L: LogOps[F]): Free[F, String] = {
  import C._, L._
  for {
    _    <- log("Starting program")
    _    <- writeLine("Enter name:")
    name <- readLine()
    _    <- log(s"User entered: $name")
  } yield name
}

def factorial(n: BigInt): Free[Id, BigInt] = {
  if (n <= 1) Free.pure(1)
  else factorial(n - 1).map(_ * n)
}

// This will not stack overflow due to Free's trampolining
val result = factorial(100000).run