Advanced Functional Programming: Category Theory and Algebraic Data Types
Advanced functional programming leverages mathematical foundations from category theory to build elegant, composable software systems. This comprehensive lesson explores algebraic data types, advanced monads, functors, applicatives, and the theoretical underpinnings that make functional programming so powerful and expressive.
Category Theory Fundamentals
Categories, Functors, and Natural Transformations
import scala.language.higherKinds
import scala.util.{Try, Success, Failure}
import scala.concurrent.{Future, ExecutionContext}
import scala.annotation.tailrec
// Category theory abstractions in Scala
object CategoryTheoryBasics {
// Functor laws and implementations
trait Functor[F[_]] {
def map[A, B](fa: F[A])(f: A => B): F[B]
// Functor laws (should be satisfied by all implementations):
// 1. Identity: map(fa)(identity) == fa
// 2. Composition: map(map(fa)(f))(g) == map(fa)(f.andThen(g))
}
// Functor instances
implicit val optionFunctor: Functor[Option] = new Functor[Option] {
def map[A, B](fa: Option[A])(f: A => B): Option[B] = fa.map(f)
}
implicit val listFunctor: Functor[List] = new Functor[List] {
def map[A, B](fa: List[A])(f: A => B): List[B] = fa.map(f)
}
implicit def eitherFunctor[E]: Functor[Either[E, *]] = new Functor[Either[E, *]] {
def map[A, B](fa: Either[E, A])(f: A => B): Either[E, B] = fa.map(f)
}
implicit val tryFunctor: Functor[Try] = new Functor[Try] {
def map[A, B](fa: Try[A])(f: A => B): Try[B] = fa.map(f)
}
// Applicative functor (allows applying functions in context)
trait Applicative[F[_]] extends Functor[F] {
def pure[A](a: A): F[A]
def ap[A, B](fab: F[A => B])(fa: F[A]): F[B]
// Derived operations
def map2[A, B, C](fa: F[A], fb: F[B])(f: (A, B) => C): F[C] =
ap(map(fa)(f.curried))(fb)
def map3[A, B, C, D](fa: F[A], fb: F[B], fc: F[C])(f: (A, B, C) => D): F[D] =
ap(ap(map(fa)(f.curried))(fb))(fc)
def sequence[A](fas: List[F[A]]): F[List[A]] =
fas.foldRight(pure(List.empty[A]))(map2(_, _)(_ :: _))
def traverse[A, B](as: List[A])(f: A => F[B]): F[List[B]] =
sequence(as.map(f))
}
// Applicative instances
implicit val optionApplicative: Applicative[Option] = new Applicative[Option] {
def pure[A](a: A): Option[A] = Some(a)
def map[A, B](fa: Option[A])(f: A => B): Option[B] = fa.map(f)
def ap[A, B](fab: Option[A => B])(fa: Option[A]): Option[B] =
(fab, fa) match {
case (Some(f), Some(a)) => Some(f(a))
case _ => None
}
}
implicit val listApplicative: Applicative[List] = new Applicative[List] {
def pure[A](a: A): List[A] = List(a)
def map[A, B](fa: List[A])(f: A => B): List[B] = fa.map(f)
def ap[A, B](fab: List[A => B])(fa: List[A]): List[B] =
for {
f <- fab
a <- fa
} yield f(a)
}
// Monad (composable computations)
trait Monad[F[_]] extends Applicative[F] {
def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]
// Monad laws:
// 1. Left identity: flatMap(pure(a))(f) == f(a)
// 2. Right identity: flatMap(fa)(pure) == fa
// 3. Associativity: flatMap(flatMap(fa)(f))(g) == flatMap(fa)(a => flatMap(f(a))(g))
// Derived from flatMap
def ap[A, B](fab: F[A => B])(fa: F[A]): F[B] =
flatMap(fab)(f => map(fa)(f))
// Kleisli composition
def compose[A, B, C](f: A => F[B], g: B => F[C]): A => F[C] =
a => flatMap(f(a))(g)
// Monad join operation
def join[A](ffa: F[F[A]]): F[A] = flatMap(ffa)(identity)
}
// Monad instances
implicit val optionMonad: Monad[Option] = new Monad[Option] {
def pure[A](a: A): Option[A] = Some(a)
def map[A, B](fa: Option[A])(f: A => B): Option[B] = fa.map(f)
def flatMap[A, B](fa: Option[A])(f: A => F[B]): Option[B] = fa.flatMap(f)
}
implicit val listMonad: Monad[List] = new Monad[List] {
def pure[A](a: A): List[A] = List(a)
def map[A, B](fa: List[A])(f: A => B): List[B] = fa.map(f)
def flatMap[A, B](fa: List[A])(f: A => F[B]): List[B] = fa.flatMap(f)
}
implicit def eitherMonad[E]: Monad[Either[E, *]] = new Monad[Either[E, *]] {
def pure[A](a: A): Either[E, A] = Right(a)
def map[A, B](fa: Either[E, A])(f: A => B): Either[E, B] = fa.map(f)
def flatMap[A, B](fa: Either[E, A])(f: A => Either[E, B]): Either[E, B] = fa.flatMap(f)
}
// Natural transformations
trait NaturalTransformation[F[_], G[_]] {
def apply[A](fa: F[A]): G[A]
}
// Example natural transformations
val optionToList: NaturalTransformation[Option, List] = new NaturalTransformation[Option, List] {
def apply[A](fa: Option[A]): List[A] = fa.toList
}
val listToOption: NaturalTransformation[List, Option] = new NaturalTransformation[List, Option] {
def apply[A](fa: List[A]): Option[A] = fa.headOption
}
val tryToEither: NaturalTransformation[Try, Either[Throwable, *]] =
new NaturalTransformation[Try, Either[Throwable, *]] {
def apply[A](fa: Try[A]): Either[Throwable, A] = fa.toEither
}
// Syntax for easier usage
implicit class FunctorOps[F[_], A](fa: F[A])(implicit F: Functor[F]) {
def map[B](f: A => B): F[B] = F.map(fa)(f)
def void: F[Unit] = map(_ => ())
def as[B](b: B): F[B] = map(_ => b)
}
implicit class ApplicativeOps[F[_], A](fa: F[A])(implicit F: Applicative[F]) {
def <*>[B](fab: F[A => B]): F[B] = F.ap(fab)(fa)
}
implicit class MonadOps[F[_], A](fa: F[A])(implicit F: Monad[F]) {
def flatMap[B](f: A => F[B]): F[B] = F.flatMap(fa)(f)
def >>=[B](f: A => F[B]): F[B] = flatMap(f)
}
}
// Advanced algebraic data types
object AlgebraicDataTypes {
// Sum types (coproducts)
sealed trait HttpResponse[+A]
case class Success[A](data: A, status: Int = 200) extends HttpResponse[A]
case class ClientError(message: String, status: Int = 400) extends HttpResponse[Nothing]
case class ServerError(message: String, status: Int = 500) extends HttpResponse[Nothing]
case object NotFound extends HttpResponse[Nothing]
// Product types
case class User(id: UserId, name: String, email: Email, age: Age)
case class Order(id: OrderId, userId: UserId, items: List[OrderItem], total: Money)
case class OrderItem(productId: ProductId, quantity: Quantity, price: Money)
// Phantom types for type safety
case class Id[T](value: String) extends AnyVal
type UserId = Id[User]
type OrderId = Id[Order]
type ProductId = Id[Product]
case class Quantity(value: Int) extends AnyVal {
require(value > 0, "Quantity must be positive")
}
case class Money(amount: BigDecimal) extends AnyVal {
require(amount >= 0, "Money amount cannot be negative")
def +(other: Money): Money = Money(amount + other.amount)
def -(other: Money): Money = Money(amount - other.amount)
def *(factor: BigDecimal): Money = Money(amount * factor)
}
case class Email(value: String) extends AnyVal {
require(value.contains("@"), "Invalid email format")
}
case class Age(value: Int) extends AnyVal {
require(value >= 0 && value <= 150, "Invalid age")
}
// Recursive data types
sealed trait Tree[+A]
case object Empty extends Tree[Nothing]
case class Leaf[A](value: A) extends Tree[A]
case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]
// Tree operations with fold
def foldTree[A, B](tree: Tree[A])(empty: B, leaf: A => B, branch: (B, B) => B): B = {
tree match {
case Empty => empty
case Leaf(value) => leaf(value)
case Branch(left, right) =>
branch(foldTree(left)(empty, leaf, branch), foldTree(right)(empty, leaf, branch))
}
}
// Tree height
def height[A](tree: Tree[A]): Int =
foldTree(tree)(0, _ => 1, (l, r) => 1 + math.max(l, r))
// Tree size
def size[A](tree: Tree[A]): Int =
foldTree(tree)(0, _ => 1, _ + _)
// Tree map
def mapTree[A, B](tree: Tree[A])(f: A => B): Tree[B] =
foldTree(tree)(Empty: Tree[B], a => Leaf(f(a)), Branch(_, _))
// List-like recursive structure with fold
sealed trait FList[+A]
case object FNil extends FList[Nothing]
case class FCons[A](head: A, tail: FList[A]) extends FList[A]
def foldRight[A, B](list: FList[A])(z: B)(f: (A, B) => B): B = {
list match {
case FNil => z
case FCons(head, tail) => f(head, foldRight(tail)(z)(f))
}
}
def foldLeft[A, B](list: FList[A])(z: B)(f: (B, A) => B): B = {
@tailrec
def loop(acc: B, remaining: FList[A]): B = remaining match {
case FNil => acc
case FCons(head, tail) => loop(f(acc, head), tail)
}
loop(z, list)
}
// Generic ADT for expressions
sealed trait Expr[A]
case class Const[A](value: A) extends Expr[A]
case class Add(left: Expr[Int], right: Expr[Int]) extends Expr[Int]
case class Multiply(left: Expr[Int], right: Expr[Int]) extends Expr[Int]
case class Equal[A](left: Expr[A], right: Expr[A]) extends Expr[Boolean]
case class IfThenElse[A](condition: Expr[Boolean], thenBranch: Expr[A], elseBranch: Expr[A]) extends Expr[A]
// Expression evaluator
def eval[A](expr: Expr[A]): A = expr match {
case Const(value) => value
case Add(left, right) => eval(left) + eval(right)
case Multiply(left, right) => eval(left) * eval(right)
case Equal(left, right) => eval(left) == eval(right)
case IfThenElse(condition, thenBranch, elseBranch) =>
if (eval(condition)) eval(thenBranch) else eval(elseBranch)
}
// Expression optimizer
def optimize[A](expr: Expr[A]): Expr[A] = expr match {
case Add(Const(0), right) => optimize(right)
case Add(left, Const(0)) => optimize(left)
case Add(Const(a), Const(b)) => Const(a + b)
case Multiply(Const(0), _) => Const(0)
case Multiply(_, Const(0)) => Const(0)
case Multiply(Const(1), right) => optimize(right)
case Multiply(left, Const(1)) => optimize(left)
case Multiply(Const(a), Const(b)) => Const(a * b)
case Add(left, right) => Add(optimize(left), optimize(right))
case Multiply(left, right) => Multiply(optimize(left), optimize(right))
case Equal(left, right) => Equal(optimize(left), optimize(right))
case IfThenElse(condition, thenBranch, elseBranch) =>
IfThenElse(optimize(condition), optimize(thenBranch), optimize(elseBranch))
case other => other
}
}Advanced Monads and Monad Transformers
// Advanced monad patterns
object AdvancedMonads {
import CategoryTheoryBasics._
// State monad for stateful computations
case class State[S, A](run: S => (S, A)) {
def map[B](f: A => B): State[S, B] =
State(s => {
val (newState, a) = run(s)
(newState, f(a))
})
def flatMap[B](f: A => State[S, B]): State[S, B] =
State(s => {
val (s1, a) = run(s)
f(a).run(s1)
})
}
object State {
def pure[S, A](a: A): State[S, A] = State(s => (s, a))
def get[S]: State[S, S] = State(s => (s, s))
def put[S](newState: S): State[S, Unit] = State(_ => (newState, ()))
def modify[S](f: S => S): State[S, Unit] = State(s => (f(s), ()))
def gets[S, A](f: S => A): State[S, A] = State(s => (s, f(s)))
}
// Reader monad for dependency injection
case class Reader[R, A](run: R => A) {
def map[B](f: A => B): Reader[R, B] =
Reader(r => f(run(r)))
def flatMap[B](f: A => Reader[R, B]): Reader[R, B] =
Reader(r => f(run(r)).run(r))
}
object Reader {
def pure[R, A](a: A): Reader[R, A] = Reader(_ => a)
def ask[R]: Reader[R, R] = Reader(identity)
def asks[R, A](f: R => A): Reader[R, A] = Reader(f)
def local[R, A](f: R => R)(reader: Reader[R, A]): Reader[R, A] =
Reader(r => reader.run(f(r)))
}
// Writer monad for logging
case class Writer[W, A](run: (W, A)) {
def map[B](f: A => B): Writer[W, B] =
Writer((run._1, f(run._2)))
def flatMap[B](f: A => Writer[W, B])(implicit M: Monoid[W]): Writer[W, B] = {
val (w1, a) = run
val (w2, b) = f(a).run
Writer((M.combine(w1, w2), b))
}
}
object Writer {
def pure[W, A](a: A)(implicit M: Monoid[W]): Writer[W, A] =
Writer((M.empty, a))
def tell[W](w: W): Writer[W, Unit] = Writer((w, ()))
def listen[W, A](writer: Writer[W, A]): Writer[W, (A, W)] = {
val (w, a) = writer.run
Writer((w, (a, w)))
}
}
// Monoid for Writer
trait Monoid[A] {
def empty: A
def combine(x: A, y: A): A
}
implicit val stringMonoid: Monoid[String] = new Monoid[String] {
def empty: String = ""
def combine(x: String, y: String): String = x + y
}
implicit val intMonoid: Monoid[Int] = new Monoid[Int] {
def empty: Int = 0
def combine(x: Int, y: Int): Int = x + y
}
implicit def listMonoid[A]: Monoid[List[A]] = new Monoid[List[A]] {
def empty: List[A] = List.empty
def combine(x: List[A], y: List[A]): List[A] = x ++ y
}
// IO monad for pure functional effects
sealed trait IO[A] {
def map[B](f: A => B): IO[B] = IO.Map(this, f)
def flatMap[B](f: A => IO[B]): IO[B] = IO.FlatMap(this, f)
def run(): A = IO.run(this)
}
object IO {
case class Pure[A](value: A) extends IO[A]
case class Effect[A](effect: () => A) extends IO[A]
case class Map[A, B](source: IO[A], f: A => B) extends IO[B]
case class FlatMap[A, B](source: IO[A], f: A => IO[B]) extends IO[B]
def pure[A](a: A): IO[A] = Pure(a)
def effect[A](a: => A): IO[A] = Effect(() => a)
def println(s: String): IO[Unit] = effect(scala.Predef.println(s))
def readLine: IO[String] = effect(scala.io.StdIn.readLine())
@tailrec
def run[A](io: IO[A]): A = io match {
case Pure(value) => value
case Effect(effect) => effect()
case Map(source, f) => f(run(source))
case FlatMap(source, f) => run(f(run(source)))
}
}
// Monad transformers for composing effects
case class OptionT[F[_], A](value: F[Option[A]])(implicit F: Monad[F]) {
def map[B](f: A => B): OptionT[F, B] =
OptionT(F.map(value)(_.map(f)))
def flatMap[B](f: A => OptionT[F, B]): OptionT[F, B] =
OptionT(F.flatMap(value) {
case Some(a) => f(a).value
case None => F.pure(None)
})
def getOrElse(default: => A): F[A] =
F.map(value)(_.getOrElse(default))
def orElse(alternative: => OptionT[F, A]): OptionT[F, A] =
OptionT(F.flatMap(value) {
case some @ Some(_) => F.pure(some)
case None => alternative.value
})
}
object OptionT {
def pure[F[_], A](a: A)(implicit F: Monad[F]): OptionT[F, A] =
OptionT(F.pure(Some(a)))
def none[F[_], A](implicit F: Monad[F]): OptionT[F, A] =
OptionT(F.pure(None))
def fromOption[F[_], A](option: Option[A])(implicit F: Monad[F]): OptionT[F, A] =
OptionT(F.pure(option))
def liftF[F[_], A](fa: F[A])(implicit F: Monad[F]): OptionT[F, A] =
OptionT(F.map(fa)(Some(_)))
}
case class EitherT[F[_], E, A](value: F[Either[E, A]])(implicit F: Monad[F]) {
def map[B](f: A => B): EitherT[F, E, B] =
EitherT(F.map(value)(_.map(f)))
def flatMap[B](f: A => EitherT[F, E, B]): EitherT[F, E, B] =
EitherT(F.flatMap(value) {
case Right(a) => f(a).value
case Left(e) => F.pure(Left(e))
})
def leftMap[E2](f: E => E2): EitherT[F, E2, A] =
EitherT(F.map(value)(_.left.map(f)))
def fold[B](onLeft: E => B, onRight: A => B): F[B] =
F.map(value)(_.fold(onLeft, onRight))
}
object EitherT {
def pure[F[_], E, A](a: A)(implicit F: Monad[F]): EitherT[F, E, A] =
EitherT(F.pure(Right(a)))
def left[F[_], E, A](e: E)(implicit F: Monad[F]): EitherT[F, E, A] =
EitherT(F.pure(Left(e)))
def fromEither[F[_], E, A](either: Either[E, A])(implicit F: Monad[F]): EitherT[F, E, A] =
EitherT(F.pure(either))
def liftF[F[_], E, A](fa: F[A])(implicit F: Monad[F]): EitherT[F, E, A] =
EitherT(F.map(fa)(Right(_)))
}
// Validation monad for accumulating errors
sealed trait Validation[+E, +A]
case class Valid[A](value: A) extends Validation[Nothing, A]
case class Invalid[E](errors: List[E]) extends Validation[E, Nothing]
object Validation {
def valid[E, A](value: A): Validation[E, A] = Valid(value)
def invalid[E, A](error: E): Validation[E, A] = Invalid(List(error))
def fromEither[E, A](either: Either[E, A]): Validation[E, A] = either match {
case Right(a) => Valid(a)
case Left(e) => Invalid(List(e))
}
implicit def validationApplicative[E]: Applicative[Validation[E, *]] =
new Applicative[Validation[E, *]] {
def pure[A](a: A): Validation[E, A] = Valid(a)
def map[A, B](fa: Validation[E, A])(f: A => B): Validation[E, B] = fa match {
case Valid(a) => Valid(f(a))
case Invalid(errors) => Invalid(errors)
}
def ap[A, B](fab: Validation[E, A => B])(fa: Validation[E, A]): Validation[E, B] =
(fab, fa) match {
case (Valid(f), Valid(a)) => Valid(f(a))
case (Invalid(e1), Invalid(e2)) => Invalid(e1 ++ e2)
case (Invalid(e), _) => Invalid(e)
case (_, Invalid(e)) => Invalid(e)
}
}
}
// Example usage of advanced monads
def statefulComputation(): State[Int, String] = {
for {
initial <- State.get[Int]
_ <- State.modify[Int](_ + 10)
current <- State.get[Int]
_ <- State.put(current * 2)
final <- State.get[Int]
} yield s"Initial: $initial, Final: $final"
}
def readerComputation(): Reader[String, String] = {
for {
env <- Reader.ask[String]
prefix <- Reader.asks[String, String](_.toUpperCase)
} yield s"$prefix: Hello from $env"
}
def writerComputation(): Writer[String, Int] = {
for {
_ <- Writer.tell("Starting computation\n")
a <- Writer.pure[String, Int](10)
_ <- Writer.tell(s"Computed value: $a\n")
b <- Writer.pure[String, Int](20)
_ <- Writer.tell(s"Computed value: $b\n")
result = a + b
_ <- Writer.tell(s"Final result: $result\n")
} yield result
}
def ioComputation(): IO[Unit] = {
for {
_ <- IO.println("What's your name?")
name <- IO.readLine
_ <- IO.println(s"Hello, $name!")
} yield ()
}
}Free Monads and Interpreters
// Free monads for building composable DSLs
object FreeMonads {
// Free monad definition
sealed trait Free[F[_], A]
case class Pure[F[_], A](value: A) extends Free[F, A]
case class Suspend[F[_], A](fa: F[A]) extends Free[F, A]
case class FlatMapped[F[_], A, B](sub: Free[F, A], f: A => Free[F, B]) extends Free[F, B]
object Free {
def pure[F[_], A](a: A): Free[F, A] = Pure(a)
def liftF[F[_], A](fa: F[A]): Free[F, A] = Suspend(fa)
implicit def freeMonad[F[_]]: Monad[Free[F, *]] = new Monad[Free[F, *]] {
def pure[A](a: A): Free[F, A] = Pure(a)
def map[A, B](fa: Free[F, A])(f: A => B): Free[F, B] = fa match {
case Pure(a) => Pure(f(a))
case Suspend(fa) => FlatMapped(fa, (a: A) => Pure(f(a)))
case FlatMapped(sub, g) => FlatMapped(sub, g.andThen(_.map(f)))
}
def flatMap[A, B](fa: Free[F, A])(f: A => Free[F, B]): Free[F, B] = fa match {
case Pure(a) => f(a)
case Suspend(fa) => FlatMapped(Suspend(fa), f)
case FlatMapped(sub, g) => FlatMapped(sub, g.andThen(_.flatMap(f)))
}
}
// Interpreter for Free monads
def foldMap[F[_], G[_], A](fa: Free[F, A])(nt: NaturalTransformation[F, G])(implicit G: Monad[G]): G[A] = {
@tailrec
def step[A](free: Free[F, A]): Either[F[Free[F, A]], A] = free match {
case Pure(a) => Right(a)
case Suspend(fa) => Left(fa.asInstanceOf[F[Free[F, A]]])
case FlatMapped(Pure(a), f) => step(f(a))
case FlatMapped(Suspend(fa), f) => Left(fa.asInstanceOf[F[Any]].asInstanceOf[F[Free[F, A]]])
case FlatMapped(FlatMapped(sub, g), f) => step(FlatMapped(sub, g.andThen(_.flatMap(f))))
}
step(fa) match {
case Right(a) => G.pure(a)
case Left(fa) => G.flatMap(nt(fa))(foldMap(_)(nt))
}
}
}
// DSL for console operations
sealed trait ConsoleOp[A]
case class PrintLine(message: String) extends ConsoleOp[Unit]
case object ReadLine extends ConsoleOp[String]
type Console[A] = Free[ConsoleOp, A]
object Console {
def printLine(message: String): Console[Unit] = Free.liftF(PrintLine(message))
def readLine: Console[String] = Free.liftF(ReadLine)
}
// DSL for HTTP operations
sealed trait HttpOp[A]
case class Get(url: String) extends HttpOp[String]
case class Post(url: String, body: String) extends HttpOp[String]
case class Put(url: String, body: String) extends HttpOp[String]
case class Delete(url: String) extends HttpOp[Unit]
type Http[A] = Free[HttpOp, A]
object Http {
def get(url: String): Http[String] = Free.liftF(Get(url))
def post(url: String, body: String): Http[String] = Free.liftF(Post(url, body))
def put(url: String, body: String): Http[String] = Free.liftF(Put(url, body))
def delete(url: String): Http[Unit] = Free.liftF(Delete(url))
}
// Combined DSL using coproducts
sealed trait App[A]
case class ConsoleOp[A](op: ConsoleOp[A]) extends App[A]
case class HttpOp[A](op: HttpOp[A]) extends App[A]
type Application[A] = Free[App, A]
object Application {
def printLine(message: String): Application[Unit] =
Free.liftF(ConsoleOp(PrintLine(message)))
def readLine: Application[String] =
Free.liftF(ConsoleOp(ReadLine))
def httpGet(url: String): Application[String] =
Free.liftF(HttpOp(Get(url)))
def httpPost(url: String, body: String): Application[String] =
Free.liftF(HttpOp(Post(url, body)))
}
// Interpreters
import CategoryTheoryBasics._
import AdvancedMonads.IO
val consoleToIO: NaturalTransformation[ConsoleOp, IO] =
new NaturalTransformation[ConsoleOp, IO] {
def apply[A](fa: ConsoleOp[A]): IO[A] = fa match {
case PrintLine(message) => IO.println(message)
case ReadLine => IO.readLine
}
}
val httpToIO: NaturalTransformation[HttpOp, IO] =
new NaturalTransformation[HttpOp, IO] {
def apply[A](fa: HttpOp[A]): IO[A] = fa match {
case Get(url) => IO.effect(s"GET response from $url")
case Post(url, body) => IO.effect(s"POST response from $url with body: $body")
case Put(url, body) => IO.effect(s"PUT response from $url with body: $body")
case Delete(url) => IO.effect(())
}
}
val appToIO: NaturalTransformation[App, IO] =
new NaturalTransformation[App, IO] {
def apply[A](fa: App[A]): IO[A] = fa match {
case ConsoleOp(op) => consoleToIO(op)
case HttpOp(op) => httpToIO(op)
}
}
// Example program using the DSL
def exampleProgram(): Application[Unit] = {
import Application._
for {
_ <- printLine("Enter a URL:")
url <- readLine
response <- httpGet(url)
_ <- printLine(s"Response: $response")
_ <- printLine("Enter request body:")
body <- readLine
postResponse <- httpPost(url, body)
_ <- printLine(s"POST Response: $postResponse")
} yield ()
}
// Testing interpreter for pure testing
case class TestState(
outputs: List[String] = List.empty,
inputs: List[String] = List.empty,
httpResponses: Map[String, String] = Map.empty
)
val appToState: NaturalTransformation[App, State[TestState, *]] =
new NaturalTransformation[App, State[TestState, *]] {
def apply[A](fa: App[A]): State[TestState, A] = fa match {
case ConsoleOp(PrintLine(message)) =>
State.modify[TestState](s => s.copy(outputs = message :: s.outputs)).map(_ => ())
case ConsoleOp(ReadLine) =>
for {
state <- State.get[TestState]
input = state.inputs.headOption.getOrElse("")
_ <- State.put(state.copy(inputs = state.inputs.drop(1)))
} yield input
case HttpOp(Get(url)) =>
State.gets[TestState, String](_.httpResponses.getOrElse(url, s"Mock response for $url"))
case HttpOp(Post(url, body)) =>
State.gets[TestState, String](_.httpResponses.getOrElse(url, s"Mock POST response for $url"))
case HttpOp(Put(url, body)) =>
State.gets[TestState, String](_.httpResponses.getOrElse(url, s"Mock PUT response for $url"))
case HttpOp(Delete(url)) =>
State.pure[TestState, Unit](())
}
}
}Conclusion
Advanced functional programming with category theory provides powerful mathematical foundations for building elegant, composable software. Key concepts include:
Category Theory Foundations:
- Functors for structure-preserving mappings
- Applicative functors for independent computations
- Monads for sequential, dependent computations
- Natural transformations for polymorphic functions
Algebraic Data Types:
- Sum types for modeling alternatives and errors
- Product types for combining data
- Phantom types for compile-time safety
- Recursive types for complex data structures
Advanced Monads:
- State monad for stateful computations
- Reader monad for dependency injection
- Writer monad for logging and accumulation
- IO monad for pure functional effects
Monad Transformers:
- OptionT for optional computations in context
- EitherT for error handling in context
- Validation for accumulating multiple errors
- Composition of multiple effects
Free Monads:
- Separation of DSL definition from interpretation
- Multiple interpreters for different environments
- Composable and testable effectful programs
- Pure functional architecture patterns
Practical Applications:
- Domain modeling with precise types
- Error handling without exceptions
- Dependency injection without frameworks
- Testing with pure functions
- Composable business logic
Mathematical Properties:
- Laws ensure predictable behavior
- Composition preserves structure
- Abstraction enables code reuse
- Types guide correct implementations
Design Principles:
- Immutability by default
- Composition over inheritance
- Pure functions for reasoning
- Types as specifications
Advanced functional programming techniques enable developers to build robust, maintainable systems that leverage mathematical principles for correctness, composability, and expressiveness while maintaining clarity and elegance in complex business domains.
Comments
Be the first to comment on this lesson!