tessl/maven-org-typelevel--cats-free-2-11

Free monads and related constructs for functional programming in Scala, providing Free and FreeT monads, Free applicatives, Cofree comonads, and Yoneda lemmas for DSL embedding and performance optimization.

Overview

Eval results

Files

Trampoline

Name: tessl/maven-org-typelevel--cats-free-2-11
Author: tessl

Trampoline provides stack-safe recursion by converting recursive computations into iterative ones using the Free monad over Function0.

Core API

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]

Type Class Instances

Trampoline inherits all Free monad instances:

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

Basic Usage

Stack-Safe Recursion

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 Optimization

// 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

Advanced Usage

Mutual Recursion

// 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

Tree Traversal

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

Iterative Algorithms

// 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

List Processing

// 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

Integration with Free Programs

Converting Free Programs to Trampoline

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

Combining with Other Monads

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

Performance Considerations

Stack Safety: Primary benefit - eliminates stack overflow for deep recursion
Overhead: Slight performance overhead compared to direct recursion
Memory: Uses heap instead of stack, which is generally more abundant
Tail Call Optimization: JVM doesn't optimize tail calls, but Trampoline provides the benefit
Best Use Cases: Deep recursion, mutual recursion, converting recursive algorithms

Common Patterns

Converting Recursive Functions

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

Monadic Composition

// 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

Install with Tessl CLI

npx tessl i tessl/maven-org-typelevel--cats-free-2-11

docs