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

Interpreters and Natural Transformations

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

Interpreters convert Free programs into concrete effects using natural transformations. This is where the separation between program description and execution is realized.

Core API

// Natural transformation type alias
type ~>[F[_], G[_]] = FunctionK[F, G]

trait FunctionK[F[_], G[_]] {
  def apply[A](fa: F[A]): G[A]
}

// Execution methods on Free
def foldMap[M[_]](f: FunctionK[S, M])(implicit M: Monad[M]): M[A]
def compile[T[_]](f: FunctionK[S, T]): Free[T, A]
def mapK[T[_]](f: S ~> T): Free[T, A]

Natural Transformation Construction

// Lambda syntax for natural transformations
def λ[F[_] ~> G[_]](f: F ~> G): F ~> G

// Identity natural transformation
def id[F[_]]: F ~> F

// Composition
def andThen[F[_], G[_], H[_]](f: F ~> G, g: G ~> H): F ~> H
def compose[F[_], G[_], H[_]](g: G ~> H, f: F ~> G): F ~> H

Basic Interpreter Patterns

Simple Algebra Interpretation

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

type Console[A] = Free[ConsoleA, A]

def writeLine(line: String): Console[Unit] = Free.liftF(WriteLine(line))
def readLine(): Console[String] = Free.liftF(ReadLine())

// Basic interpreter to Id (for testing)
import cats.Id

val consoleToId: ConsoleA ~> Id = new (ConsoleA ~> Id) {
  def apply[A](fa: ConsoleA[A]): Id[A] = fa match {
    case WriteLine(line) => println(line)
    case ReadLine()      => "test input"
  }
}

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

val result: String = program.foldMap(consoleToId)

Effectful Interpreters

import cats.effect.IO

val consoleToIO: ConsoleA ~> IO = new (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())
  }
}

// Execute with effects
val ioResult: IO[String] = program.foldMap(consoleToIO)

Advanced Interpreter Patterns

State-Based Interpreters

import cats.data.State

// Key-Value store algebra
sealed trait KVStoreA[A]
case class Put[T](key: String, value: T) extends KVStoreA[Unit]
case class Get[T](key: String) extends KVStoreA[Option[T]]
case class Delete(key: String) extends KVStoreA[Unit]

type KVStore[A] = Free[KVStoreA, A]

def put[T](key: String, value: T): KVStore[Unit] = Free.liftF(Put(key, value))
def get[T](key: String): KVStore[Option[T]] = Free.liftF(Get(key))
def delete(key: String): KVStore[Unit] = Free.liftF(Delete(key))

// State interpreter
type KVState = Map[String, Any]
type StateInterpreter[A] = State[KVState, A]

val kvToState: KVStoreA ~> StateInterpreter = new (KVStoreA ~> StateInterpreter) {
  def apply[A](fa: KVStoreA[A]): StateInterpreter[A] = fa match {
    case Put(key, value) => State.modify(_.updated(key, value))
    case Get(key)        => State.inspect(_.get(key).asInstanceOf[Option[A]])
    case Delete(key)     => State.modify(_ - key)
  }
}

// Usage
val kvProgram: KVStore[Option[String]] = for {
  _      <- put("name", "Alice")
  _      <- put("age", 30)
  name   <- get[String]("name")
  _      <- delete("age")
  result <- get[String]("name")
} yield result

val (finalState, result) = kvProgram.foldMap(kvToState).run(Map.empty).value

Logging Interpreters

import cats.data.Writer
import cats.implicits._

// Add logging to any interpreter
def withLogging[F[_], G[_]](
  interpreter: F ~> G,
  logger: F ~> Writer[List[String], ?]
)(implicit G: Monad[G]): F ~> Writer[List[String], G[?]] = {
  
  new (F ~> Writer[List[String], G[?]]) {
    def apply[A](fa: F[A]): Writer[List[String], G[A]] = {
      val logEntry = logger(fa)
      Writer(logEntry.written, interpreter(fa))
    }
  }
}

// Logger for KVStore operations
val kvLogger: KVStoreA ~> Writer[List[String], ?] = new (KVStoreA ~> Writer[List[String], ?]) {
  def apply[A](fa: KVStoreA[A]): Writer[List[String], A] = fa match {
    case Put(key, value) => Writer(List(s"PUT $key = $value"), ())
    case Get(key)        => Writer(List(s"GET $key"), None.asInstanceOf[A]) // Placeholder
    case Delete(key)     => Writer(List(s"DELETE $key"), ())
  }
}

// Note: This is a simplified example - real logging interpreters would be more complex

Testing Interpreters

// Mock interpreter for testing
case class MockConsoleState(inputs: List[String], outputs: List[String])

val mockConsoleInterpreter: ConsoleA ~> State[MockConsoleState, ?] = 
  new (ConsoleA ~> State[MockConsoleState, ?]) {
    def apply[A](fa: ConsoleA[A]): State[MockConsoleState, A] = fa match {
      case WriteLine(line) => 
        State.modify[MockConsoleState](s => s.copy(outputs = s.outputs :+ line))
      case ReadLine() => 
        State { s =>
          s.inputs match {
            case head :: tail => (s.copy(inputs = tail), head.asInstanceOf[A])
            case Nil => (s, "".asInstanceOf[A])
          }
        }
    }
  }

// Test setup
val initialState = MockConsoleState(List("Alice", "Bob"), List())
val (finalState, result) = program.foldMap(mockConsoleInterpreter).run(initialState).value
// finalState.outputs contains all the written lines

Interpreter Composition

Sequential Composition

// Compose interpreters in sequence
def composeSequential[F[_], G[_], H[_]](
  first: F ~> G,
  second: G ~> H
): F ~> H = new (F ~> H) {
  def apply[A](fa: F[A]): H[A] = second(first(fa))
}

// Example: KVStore -> State -> IO
val kvToIO: KVStoreA ~> IO = composeSequential(kvToState, stateToIO)

def stateToIO[S]: State[S, ?] ~> IO = new (State[S, ?] ~> IO) {
  def apply[A](sa: State[S, A]): IO[A] = {
    // This is simplified - you'd need to manage state properly
    IO(sa.runA(???.asInstanceOf[S]).value)
  }
}

Parallel Composition with Coproducts

import cats.data.Coproduct

// Define multiple algebras
sealed trait FileA[A]
case class ReadFile(path: String) extends FileA[String]
case class WriteFile(path: String, content: String) extends FileA[Unit]

sealed trait NetworkA[A]
case class HttpGet(url: String) extends NetworkA[String]
case class HttpPost(url: String, body: String) extends NetworkA[String]

// Combine algebras
type AppAlgebra[A] = Coproduct[FileA, NetworkA, A]
type App[A] = Free[AppAlgebra, A]

// Individual interpreters
val fileToIO: FileA ~> IO = new (FileA ~> IO) {
  def apply[A](fa: FileA[A]): IO[A] = fa match {
    case ReadFile(path) => IO(scala.io.Source.fromFile(path).mkString)
    case WriteFile(path, content) => IO {
      val writer = new java.io.PrintWriter(path)
      try writer.write(content) finally writer.close()
    }
  }
}

val networkToIO: NetworkA ~> IO = new (NetworkA ~> IO) {
  def apply[A](fa: NetworkA[A]): IO[A] = fa match {
    case HttpGet(url) => IO(s"GET response from $url")
    case HttpPost(url, body) => IO(s"POST response from $url with $body")
  }
}

// Combine interpreters
val appToIO: AppAlgebra ~> IO = fileToIO or networkToIO

// Helper functions
def readFile(path: String): App[String] = 
  Free.liftF(Coproduct.leftc(ReadFile(path)))

def httpGet(url: String): App[String] = 
  Free.liftF(Coproduct.rightc(HttpGet(url)))

// Combined program
val appProgram: App[String] = for {
  config <- readFile("config.txt")
  result <- httpGet(s"https://api.example.com?config=$config")
} yield result

val finalResult: IO[String] = appProgram.foldMap(appToIO)

Error Handling in Interpreters

Either-Based Error Handling

sealed trait DatabaseError
case class ConnectionError(message: String) extends DatabaseError
case class QueryError(message: String) extends DatabaseError

sealed trait DatabaseA[A]
case class ExecuteQuery(sql: String) extends DatabaseA[List[String]]
case class ExecuteUpdate(sql: String) extends DatabaseA[Int]

type Database[A] = Free[DatabaseA, A]

val databaseToEither: DatabaseA ~> Either[DatabaseError, ?] = 
  new (DatabaseA ~> Either[DatabaseError, ?]) {
    def apply[A](fa: DatabaseA[A]): Either[DatabaseError, A] = fa match {
      case ExecuteQuery(sql) => 
        if (sql.contains("DROP")) Left(QueryError("DROP not allowed"))
        else Right(List("result1", "result2").asInstanceOf[A])
      case ExecuteUpdate(sql) => 
        if (sql.contains("invalid")) Left(QueryError("Invalid SQL"))
        else Right(1.asInstanceOf[A])
    }
  }

def executeQuery(sql: String): Database[List[String]] = 
  Free.liftF(ExecuteQuery(sql))

val dbProgram: Database[List[String]] = executeQuery("SELECT * FROM users")
val result: Either[DatabaseError, List[String]] = dbProgram.foldMap(databaseToEither)

MonadError Integration

import cats.MonadError
import cats.effect.IO

val databaseToIO: DatabaseA ~> IO = new (DatabaseA ~> IO) {
  def apply[A](fa: DatabaseA[A]): IO[A] = fa match {
    case ExecuteQuery(sql) => 
      if (sql.contains("DROP")) 
        IO.raiseError(new RuntimeException("DROP not allowed"))
      else 
        IO.pure(List("result1", "result2").asInstanceOf[A])
    case ExecuteUpdate(sql) => 
      if (sql.contains("invalid")) 
        IO.raiseError(new RuntimeException("Invalid SQL"))
      else 
        IO.pure(1.asInstanceOf[A])
  }
}

// Error handling with MonadError
val safeDbProgram = dbProgram.foldMap(databaseToIO).handleErrorWith {
  case error => IO.pure(List(s"Error: ${error.getMessage}"))
}

Performance Optimization

Batch Operations

// Optimize multiple operations into batches
sealed trait OptimizedKVA[A]
case class BatchOps(operations: List[KVStoreA[Any]]) extends OptimizedKVA[List[Any]]

val batchingInterpreter: KVStoreA ~> OptimizedKVA = new (KVStoreA ~> OptimizedKVA) {
  def apply[A](fa: KVStoreA[A]): OptimizedKVA[A] = 
    BatchOps(List(fa)).asInstanceOf[OptimizedKVA[A]]
}

// Then optimize the batched operations
val optimizedToIO: OptimizedKVA ~> IO = new (OptimizedKVA ~> IO) {
  def apply[A](fa: OptimizedKVA[A]): IO[A] = fa match {
    case BatchOps(ops) => 
      // Execute all operations in a single database transaction
      IO(ops.map(executeOperation)).asInstanceOf[IO[A]]
  }
}

def executeOperation(op: KVStoreA[Any]): Any = {
  // Batch execution logic
  ???
}

Testing Strategies

Property-Based Testing of Interpreters

import org.scalacheck._

// Generate random programs
def genKVProgram: Gen[KVStore[Option[String]]] = for {
  key <- Gen.alphaStr
  value <- Gen.alphaStr
} yield for {
  _      <- put(key, value)
  result <- get[String](key)
} yield result

// Test interpreter equivalence
def interpretersAgree[F[_], A](
  program: Free[F, A],
  interp1: F ~> Id,
  interp2: F ~> Id
): Boolean = {
  program.foldMap(interp1) == program.foldMap(interp2)
}

// Property: mock and real interpreters should agree on pure operations
val interpretEqualityProp = Prop.forAll(genKVProgram) { program =>
  interpretersAgree(program, mockKvInterpreter, realKvInterpreter)
}

Best Practices

Single Responsibility: Each interpreter should handle one concern
Composability: Design interpreters to be composable
Error Handling: Use appropriate error handling strategies (Either, MonadError, etc.)
Testing: Create mock interpreters for testing
Performance: Consider batching and optimization where appropriate
Type Safety: Use phantom types or tagged types to ensure correct interpretation

Install with Tessl CLI

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

docs