Trampoline

type Trampoline[A] = Free[Function0, A]

// Construction
def done[A](a: A): Trampoline[A]
def defer[A](a: => Trampoline[A]): Trampoline[A]
def delay[A](a: => A): Trampoline[A]

// Execution (inherited from Free)
def run: A
def runM[M[_]](f: Function0[Trampoline[A]] => M[Trampoline[A]])(implicit M: Monad[M]): M[A]

implicit def catsFreeMonadForId: Monad[Free[Id, ?]]
implicit def catsFreeDeferForId: Defer[Free[Id, ?]]

import cats.free.Trampoline._

// Traditional recursive factorial (will stack overflow for large n)
def factorial(n: BigInt): BigInt = {
  if (n <= 1) 1
  else n * factorial(n - 1)
}

// Stack-safe version using Trampoline
def factorialTrampoline(n: BigInt): Trampoline[BigInt] = {
  if (n <= 1) done(1)
  else defer(factorialTrampoline(n - 1)).map(_ * n)
}

// Execute safely
val result = factorialTrampoline(100000).run  // Won't stack overflow

// Tail-recursive version with accumulator
def factorialTailRec(n: BigInt, acc: BigInt = 1): Trampoline[BigInt] = {
  if (n <= 1) done(acc)
  else defer(factorialTailRec(n - 1, n * acc))
}

val result = factorialTailRec(100000).run

// Mutually recursive functions (even/odd)
def isEven(n: Int): Trampoline[Boolean] = {
  if (n == 0) done(true)
  else defer(isOdd(n - 1))
}

def isOdd(n: Int): Trampoline[Boolean] = {
  if (n == 0) done(false)
  else defer(isEven(n - 1))
}

// Safe execution
val evenResult = isEven(100000).run  // false
val oddResult = isOdd(100001).run    // true

sealed trait Tree[A]
case class Leaf[A](value: A) extends Tree[A]
case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]

// Stack-safe tree sum
def sumTree(tree: Tree[Int]): Trampoline[Int] = tree match {
  case Leaf(value) => done(value)
  case Branch(left, right) => for {
    leftSum  <- defer(sumTree(left))
    rightSum <- defer(sumTree(right))
  } yield leftSum + rightSum
}

// Create a deep tree
def deepTree(depth: Int): Tree[Int] = {
  if (depth <= 0) Leaf(1)
  else Branch(deepTree(depth - 1), deepTree(depth - 1))
}

val tree = deepTree(20)
val sum = sumTree(tree).run  // Stack-safe even for very deep trees

// Convert recursive algorithms to iterative ones
def fibonacci(n: Int): Trampoline[BigInt] = {
  def fibHelper(i: Int, prev: BigInt, curr: BigInt): Trampoline[BigInt] = {
    if (i == n) done(curr)
    else defer(fibHelper(i + 1, curr, prev + curr))
  }
  
  if (n <= 0) done(0)
  else if (n == 1) done(1)
  else defer(fibHelper(1, 0, 1))
}

val fib100 = fibonacci(100).run

// Stack-safe list operations
def mapTrampoline[A, B](list: List[A])(f: A => B): Trampoline[List[B]] = {
  def mapHelper(remaining: List[A], acc: List[B]): Trampoline[List[B]] = remaining match {
    case Nil => done(acc.reverse)
    case head :: tail => defer(mapHelper(tail, f(head) :: acc))
  }
  
  defer(mapHelper(list, Nil))
}

def foldLeftTrampoline[A, B](list: List[A], initial: B)(f: (B, A) => B): Trampoline[B] = {
  def foldHelper(remaining: List[A], acc: B): Trampoline[B] = remaining match {
    case Nil => done(acc)
    case head :: tail => defer(foldHelper(tail, f(acc, head)))
  }
  
  defer(foldHelper(list, initial))
}

// Usage
val largeList = (1 to 100000).toList
val doubled = mapTrampoline(largeList)(_ * 2).run
val sum = foldLeftTrampoline(largeList, 0)(_ + _).run

import cats.arrow.FunctionK
import cats.~>

// Example algebra
sealed trait CalculatorA[A]
case class Add(x: Int, y: Int) extends CalculatorA[Int]
case class Multiply(x: Int, y: Int) extends CalculatorA[Int]

type Calculator[A] = Free[CalculatorA, A]

def add(x: Int, y: Int): Calculator[Int] = Free.liftF(Add(x, y))
def multiply(x: Int, y: Int): Calculator[Int] = Free.liftF(Multiply(x, y))

// Interpreter to Trampoline
val calculatorToTrampoline: CalculatorA ~> Trampoline = new (CalculatorA ~> Trampoline) {
  def apply[A](fa: CalculatorA[A]): Trampoline[A] = fa match {
    case Add(x, y) => delay(x + y)
    case Multiply(x, y) => delay(x * y)
  }
}

// Program using Calculator algebra
val program: Calculator[Int] = for {
  sum     <- add(5, 3)
  product <- multiply(sum, 4)
  final   <- add(product, 10)
} yield final

// Execute as Trampoline
val result: Int = program.foldMap(calculatorToTrampoline).run

import cats.effect.IO

// Trampoline in IO context
def trampolineInIO[A](trampoline: Trampoline[A]): IO[A] = {
  IO(trampoline.run)
}

// Or using natural transformation
val trampolineToIO: Trampoline ~> IO = new (Trampoline ~> IO) {
  def apply[A](fa: Trampoline[A]): IO[A] = IO(fa.run)
}

// Example: Stack-safe recursive IO operation
def recursiveIO(n: Int): IO[Int] = {
  val trampolineResult = factorialTrampoline(n)
  trampolineInIO(trampolineResult)
}

// Pattern: Direct recursion to Trampoline
// From: def f(x) = if (base) baseCase else f(recurse(x))
// To:   def f(x) = if (base) done(baseCase) else defer(f(recurse(x)))

// Example: List length
def lengthTrampoline[A](list: List[A]): Trampoline[Int] = list match {
  case Nil => done(0)
  case _ :: tail => defer(lengthTrampoline(tail)).map(_ + 1)
}

// Combining multiple Trampoline computations
def composedComputation(n: Int): Trampoline[String] = for {
  fact <- factorialTrampoline(n)
  fib  <- fibonacci(n)
  sum  <- delay(fact + fib)
} yield s"Factorial: $fact, Fibonacci: $fib, Sum: $sum"

val result = composedComputation(100).run