Advanced Functional Programming: Monads, Functors, and Algebraic Data Types

Advanced functional programming in Scala involves understanding mathematical abstractions that provide powerful patterns for composing and structuring code. In this comprehensive lesson, we'll explore monads, functors, algebraic data types, and the category theory principles that underpin modern functional programming.

Understanding Category Theory Foundations

Basic Category Theory Concepts

Category theory provides the mathematical foundation for functional programming abstractions. Understanding these concepts helps us build more robust and composable software.

// Identity: Every object has an identity morphism
trait Identity[F[_]] {
  def identity[A]: F[A] => F[A] = fa => fa
}

// Composition: Morphisms can be composed
trait Compose[F[_]] {
  def compose[A, B, C](f: F[A] => F[B], g: F[B] => F[C]): F[A] => F[C] = 
    fa => g(f(fa))
}

// Associativity: Composition is associative
// (f . g) . h = f . (g . h)

// Example with simple function composition
val addOne: Int => Int = _ + 1
val multiplyTwo: Int => Int = _ * 2
val toString: Int => String = _.toString

val composed1 = (addOne andThen multiplyTwo) andThen toString
val composed2 = addOne andThen (multiplyTwo andThen toString)

// Both should produce the same result
val result1 = composed1(5) // "12"
val result2 = composed2(5) // "12"

Functors: Structure-Preserving Maps

Functors are the foundation of functional programming abstractions, representing containers that can be mapped over while preserving structure.

// Functor trait definition
trait Functor[F[_]] {
  def map[A, B](fa: F[A])(f: A => B): F[B]

  // Functor laws:
  // 1. Identity: map(fa)(identity) = fa
  // 2. Composition: map(map(fa)(f))(g) = map(fa)(f andThen g)
}

// List functor instance
given Functor[List] with {
  def map[A, B](fa: List[A])(f: A => B): List[B] = fa.map(f)
}

// Option functor instance
given Functor[Option] with {
  def map[A, B](fa: Option[A])(f: A => B): Option[B] = fa.map(f)
}

// Either functor instance (right-biased)
given [L]: Functor[Either[L, *]] with {
  def map[A, B](fa: Either[L, A])(f: A => B): Either[L, B] = fa.map(f)
}

// Custom Tree functor
enum Tree[A] {
  case Leaf(value: A)
  case Branch(left: Tree[A], right: Tree[A])
}

given Functor[Tree] with {
  def map[A, B](fa: Tree[A])(f: A => B): Tree[B] = fa match {
    case Tree.Leaf(value) => Tree.Leaf(f(value))
    case Tree.Branch(left, right) => Tree.Branch(map(left)(f), map(right)(f))
  }
}

// Using functors
val numbers = List(1, 2, 3, 4, 5)
val doubled = summon[Functor[List]].map(numbers)(_ * 2)

val tree = Tree.Branch(Tree.Leaf(1), Tree.Branch(Tree.Leaf(2), Tree.Leaf(3)))
val mappedTree = summon[Functor[Tree]].map(tree)(_ * 10)

// Functor composition
def liftF2[F[_]: Functor, A, B, C](f: (A, B) => C): (F[A], F[B]) => F[C] = {
  (fa, fb) => summon[Functor[F]].map(fa)(a => 
    summon[Functor[F]].map(fb)(b => f(a, b)))
}

// This doesn't work well - we need Applicative for this pattern

Applicative Functors: Independent Computations

Applicative functors extend functors to allow functions of multiple arguments to be applied to wrapped values.

// Applicative trait definition
trait Applicative[F[_]] extends Functor[F] {
  def pure[A](a: A): F[A]
  def ap[A, B](ff: F[A => B])(fa: F[A]): F[B]

  // Derived methods
  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)

  // Applicative laws:
  // 1. Identity: ap(pure(identity))(fa) = fa
  // 2. Composition: ap(ap(ap(pure(compose))(fab))(fbc))(fa) = ap(fab)(ap(fbc)(fa))
  // 3. Homomorphism: ap(pure(f))(pure(a)) = pure(f(a))
  // 4. Interchange: ap(fab)(pure(a)) = ap(pure(f => f(a)))(fab)
}

// Option Applicative instance
given Applicative[Option] with {
  def pure[A](a: A): Option[A] = Some(a)

  def ap[A, B](ff: Option[A => B])(fa: Option[A]): Option[B] = 
    (ff, fa) match {
      case (Some(f), Some(a)) => Some(f(a))
      case _ => None
    }

  def map[A, B](fa: Option[A])(f: A => B): Option[B] = fa.map(f)
}

// List Applicative instance
given Applicative[List] with {
  def pure[A](a: A): List[A] = List(a)

  def ap[A, B](ff: List[A => B])(fa: List[A]): List[B] = 
    for {
      f <- ff
      a <- fa
    } yield f(a)

  def map[A, B](fa: List[A])(f: A => B): List[B] = fa.map(f)
}

// Either Applicative instance (accumulating errors)
given [L: Semigroup]: Applicative[Either[L, *]] with {
  def pure[A](a: A): Either[L, A] = Right(a)

  def ap[A, B](ff: Either[L, A => B])(fa: Either[L, A]): Either[L, B] = 
    (ff, fa) match {
      case (Right(f), Right(a)) => Right(f(a))
      case (Left(e1), Left(e2)) => Left(summon[Semigroup[L]].combine(e1, e2))
      case (Left(e), _) => Left(e)
      case (_, Left(e)) => Left(e)
    }

  def map[A, B](fa: Either[L, A])(f: A => B): Either[L, B] = fa.map(f)
}

// Using Applicative for validation
case class User(name: String, email: String, age: Int)

def validateName(name: String): Either[List[String], String] =
  if (name.nonEmpty) Right(name)
  else Left(List("Name cannot be empty"))

def validateEmail(email: String): Either[List[String], String] =
  if (email.contains("@")) Right(email)
  else Left(List("Invalid email format"))

def validateAge(age: Int): Either[List[String], Int] =
  if (age >= 0 && age <= 150) Right(age)
  else Left(List("Age must be between 0 and 150"))

// Semigroup for List to combine errors
given Semigroup[List[String]] with {
  def combine(a: List[String], b: List[String]): List[String] = a ++ b
}

def validateUser(name: String, email: String, age: Int): Either[List[String], User] = {
  val applicative = summon[Applicative[Either[List[String], *]]]
  applicative.map3(
    validateName(name),
    validateEmail(email),
    validateAge(age)
  )(User.apply)
}

// Test validation
val validUser = validateUser("Alice", "alice@example.com", 30)
// Right(User("Alice", "alice@example.com", 30))

val invalidUser = validateUser("", "invalid-email", -5)
// Left(List("Name cannot be empty", "Invalid email format", "Age must be between 0 and 150"))

Monads: Sequential Computations

Monads represent computations that can be sequenced, handling context and effects in a composable way.

// Monad trait definition
trait Monad[F[_]] extends Applicative[F] {
  def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]

  // Derived methods
  def flatten[A](ffa: F[F[A]]): F[A] = flatMap(ffa)(identity)

  override def ap[A, B](ff: F[A => B])(fa: F[A]): F[B] =
    flatMap(ff)(f => map(fa)(f))

  override def map[A, B](fa: F[A])(f: A => B): F[B] =
    flatMap(fa)(a => pure(f(a)))

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

// Option Monad instance
given Monad[Option] with {
  def pure[A](a: A): Option[A] = Some(a)

  def flatMap[A, B](fa: Option[A])(f: A => Option[B]): Option[B] = 
    fa.flatMap(f)
}

// List Monad instance
given Monad[List] with {
  def pure[A](a: A): List[A] = List(a)

  def flatMap[A, B](fa: List[A])(f: A => List[B]): List[B] = 
    fa.flatMap(f)
}

// Either Monad instance (right-biased, short-circuiting)
given [L]: Monad[Either[L, *]] with {
  def pure[A](a: A): Either[L, A] = Right(a)

  def flatMap[A, B](fa: Either[L, A])(f: A => Either[L, B]): Either[L, B] = 
    fa.flatMap(f)
}

// 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 (newState, a) = run(s)
      f(a).run(newState)
    })
}

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 set[S](newState: S): State[S, Unit] = State(_ => (newState, ()))

  def modify[S](f: S => S): State[S, Unit] = State(s => (f(s), ()))
}

given [S]: Monad[State[S, *]] with {
  def pure[A](a: A): State[S, A] = State.pure(a)

  def flatMap[A, B](fa: State[S, A])(f: A => State[S, B]): State[S, B] = 
    fa.flatMap(f)
}

// Using State monad for a simple counter
def increment: State[Int, Int] = 
  State(counter => (counter + 1, counter + 1))

def decrement: State[Int, Int] = 
  State(counter => (counter - 1, counter - 1))

def reset: State[Int, Unit] = 
  State(_ => (0, ()))

val statefulComputation = for {
  _ <- increment
  _ <- increment
  current <- increment
  _ <- decrement
  final <- State.get[Int]
} yield (current, final)

val (finalState, result) = statefulComputation.run(0)
// finalState = 2, result = (3, 2)

// IO Monad for handling side 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)
}

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](io: IO[A], f: A => B) extends IO[B]
  case class FlatMap[A, B](io: IO[A], f: A => IO[B]) extends IO[B]

  def pure[A](a: A): IO[A] = Pure(a)

  def effect[A](eff: => A): IO[A] = Effect(() => eff)

  def run[A](io: IO[A]): A = io match {
    case Pure(value) => value
    case Effect(eff) => eff()
    case Map(source, f) => f(run(source))
    case FlatMap(source, f) => run(f(run(source)))
  }
}

given Monad[IO] with {
  def pure[A](a: A): IO[A] = IO.pure(a)

  def flatMap[A, B](fa: IO[A])(f: A => IO[B]): IO[B] = fa.flatMap(f)
}

// Using IO monad
def readLine: IO[String] = IO.effect(scala.io.StdIn.readLine())
def println(s: String): IO[Unit] = IO.effect(scala.Console.println(s))

val program = for {
  _ <- println("What's your name?")
  name <- readLine
  _ <- println(s"Hello, $name!")
} yield ()

// IO.run(program) // Executes the side effects

Algebraic Data Types

Sum Types (Coproducts)

Sum types represent a choice between different alternatives, implemented in Scala using sealed traits and case classes or enums.

// Basic sum type using sealed trait
sealed trait Shape
case class Circle(radius: Double) extends Shape
case class Rectangle(width: Double, height: Double) extends Shape
case class Triangle(base: Double, height: Double) extends Shape

def area(shape: Shape): Double = shape match {
  case Circle(radius) => math.Pi * radius * radius
  case Rectangle(width, height) => width * height
  case Triangle(base, height) => 0.5 * base * height
}

// Using Scala 3 enums for sum types
enum Color {
  case Red, Green, Blue
  case RGB(r: Int, g: Int, b: Int)
  case HSL(h: Double, s: Double, l: Double)
}

def toRGB(color: Color): Color.RGB = color match {
  case Color.Red => Color.RGB(255, 0, 0)
  case Color.Green => Color.RGB(0, 255, 0)
  case Color.Blue => Color.RGB(0, 0, 255)
  case rgb @ Color.RGB(_, _, _) => rgb
  case Color.HSL(h, s, l) => 
    // HSL to RGB conversion logic
    Color.RGB(0, 0, 0) // Simplified
}

// Result type for error handling
enum Result[+T, +E] {
  case Success(value: T)
  case Failure(error: E)

  def map[U](f: T => U): Result[U, E] = this match {
    case Success(value) => Success(f(value))
    case Failure(error) => Failure(error)
  }

  def flatMap[U](f: T => Result[U, E]): Result[U, E] = this match {
    case Success(value) => f(value)
    case Failure(error) => Failure(error)
  }

  def mapError[F](f: E => F): Result[T, F] = this match {
    case Success(value) => Success(value)
    case Failure(error) => Failure(f(error))
  }
}

// Maybe type (similar to Option)
enum Maybe[+A] {
  case Just(value: A)
  case Nothing

  def map[B](f: A => B): Maybe[B] = this match {
    case Just(value) => Just(f(value))
    case Nothing => Nothing
  }

  def flatMap[B](f: A => Maybe[B]): Maybe[B] = this match {
    case Just(value) => f(value)
    case Nothing => Nothing
  }

  def getOrElse[B >: A](default: => B): B = this match {
    case Just(value) => value
    case Nothing => default
  }
}

// Validation type that accumulates errors
enum Validation[+E, +A] {
  case Valid(value: A)
  case Invalid(errors: List[E])

  def map[B](f: A => B): Validation[E, B] = this match {
    case Valid(value) => Valid(f(value))
    case Invalid(errors) => Invalid(errors)
  }

  def flatMap[F >: E, B](f: A => Validation[F, B]): Validation[F, B] = this match {
    case Valid(value) => f(value)
    case Invalid(errors) => Invalid(errors)
  }
}

object Validation {
  def combine[E, A, B](va: Validation[E, A], vb: Validation[E, B]): Validation[E, (A, B)] = 
    (va, vb) match {
      case (Valid(a), Valid(b)) => Valid((a, b))
      case (Invalid(e1), Invalid(e2)) => Invalid(e1 ++ e2)
      case (Invalid(e), _) => Invalid(e)
      case (_, Invalid(e)) => Invalid(e)
    }

  def map2[E, A, B, C](va: Validation[E, A], vb: Validation[E, B])(f: (A, B) => C): Validation[E, C] =
    combine(va, vb).map(f.tupled)
}

Product Types

Product types combine multiple values together, implemented using case classes or tuples.

// Basic product types
case class Person(name: String, age: Int, email: String)
case class Address(street: String, city: String, zipCode: String)
case class Customer(person: Person, address: Address, loyaltyPoints: Int)

// Generic product types
case class Pair[A, B](first: A, second: B) {
  def map[C, D](f: A => C, g: B => D): Pair[C, D] = 
    Pair(f(first), g(second))

  def swap: Pair[B, A] = Pair(second, first)
}

case class Triple[A, B, C](first: A, second: B, third: C)

// Non-empty list (product of head and tail)
enum NonEmptyList[+A] {
  case Single(head: A)
  case Cons(head: A, tail: NonEmptyList[A])

  def map[B](f: A => B): NonEmptyList[B] = this match {
    case Single(head) => Single(f(head))
    case Cons(head, tail) => Cons(f(head), tail.map(f))
  }

  def flatMap[B](f: A => NonEmptyList[B]): NonEmptyList[B] = this match {
    case Single(head) => f(head)
    case Cons(head, tail) => concat(f(head), tail.flatMap(f))
  }

  def toList: List[A] = this match {
    case Single(head) => List(head)
    case Cons(head, tail) => head :: tail.toList
  }
}

object NonEmptyList {
  def apply[A](head: A, tail: A*): NonEmptyList[A] = 
    tail.foldRight(Single(head): NonEmptyList[A])((a, acc) => Cons(a, acc))

  def concat[A](nel1: NonEmptyList[A], nel2: NonEmptyList[A]): NonEmptyList[A] = 
    nel1 match {
      case Single(head) => Cons(head, nel2)
      case Cons(head, tail) => Cons(head, concat(tail, nel2))
    }
}

// Zipper for navigating data structures
case class ListZipper[A](left: List[A], focus: A, right: List[A]) {
  def moveLeft: Option[ListZipper[A]] = left match {
    case Nil => None
    case h :: t => Some(ListZipper(t, h, focus :: right))
  }

  def moveRight: Option[ListZipper[A]] = right match {
    case Nil => None
    case h :: t => Some(ListZipper(focus :: left, h, t))
  }

  def update(newFocus: A): ListZipper[A] = 
    copy(focus = newFocus)

  def toList: List[A] = left.reverse ++ (focus :: right)
}

object ListZipper {
  def fromList[A](list: List[A]): Option[ListZipper[A]] = list match {
    case Nil => None
    case h :: t => Some(ListZipper(Nil, h, t))
  }
}

Recursive Data Types

Recursive algebraic data types represent structures that reference themselves.

// Binary tree
enum BinaryTree[+A] {
  case Empty
  case Node(value: A, left: BinaryTree[A], right: BinaryTree[A])

  def size: Int = this match {
    case Empty => 0
    case Node(_, left, right) => 1 + left.size + right.size
  }

  def height: Int = this match {
    case Empty => 0
    case Node(_, left, right) => 1 + math.max(left.height, right.height)
  }

  def map[B](f: A => B): BinaryTree[B] = this match {
    case Empty => Empty
    case Node(value, left, right) => 
      Node(f(value), left.map(f), right.map(f))
  }

  def fold[B](empty: B)(node: (A, B, B) => B): B = this match {
    case Empty => empty
    case Node(value, left, right) => 
      node(value, left.fold(empty)(node), right.fold(empty)(node))
  }
}

// Rose tree (tree with variable number of children)
case class RoseTree[A](value: A, children: List[RoseTree[A]]) {
  def map[B](f: A => B): RoseTree[B] = 
    RoseTree(f(value), children.map(_.map(f)))

  def flatMap[B](f: A => RoseTree[B]): RoseTree[B] = {
    val newTree = f(value)
    val newChildren = children.map(_.flatMap(f)) ++ newTree.children
    newTree.copy(children = newChildren)
  }

  def fold[B](f: (A, List[B]) => B): B = 
    f(value, children.map(_.fold(f)))
}

// Stream (infinite list)
enum Stream[+A] {
  case Empty
  case Cons(head: () => A, tail: () => Stream[A])

  def headOption: Option[A] = this match {
    case Empty => None
    case Cons(head, _) => Some(head())
  }

  def tail: Stream[A] = this match {
    case Empty => Empty
    case Cons(_, tail) => tail()
  }

  def take(n: Int): List[A] = {
    def loop(stream: Stream[A], n: Int, acc: List[A]): List[A] = 
      if (n <= 0) acc.reverse
      else stream match {
        case Empty => acc.reverse
        case Cons(head, tail) => loop(tail(), n - 1, head() :: acc)
      }
    loop(this, n, Nil)
  }

  def map[B](f: A => B): Stream[B] = this match {
    case Empty => Empty
    case Cons(head, tail) => Stream.cons(f(head()), tail().map(f))
  }
}

object Stream {
  def cons[A](head: => A, tail: => Stream[A]): Stream[A] = 
    Cons(() => head, () => tail)

  def from(n: Int): Stream[Int] = 
    cons(n, from(n + 1))

  def repeat[A](a: A): Stream[A] = 
    cons(a, repeat(a))

  def fibonacci: Stream[Int] = {
    def fib(a: Int, b: Int): Stream[Int] = 
      cons(a, fib(b, a + b))
    fib(0, 1)
  }
}

// The fibonacci stream
val fibStream = Stream.fibonacci
val first10Fibs = fibStream.take(10)
// List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)

Advanced Monad Patterns

Monad Transformers

Monad transformers allow us to compose monads, combining their effects.

// Option transformer
case class OptionT[F[_]: Monad, A](value: F[Option[A]]) {
  def map[B](f: A => B): OptionT[F, B] = 
    OptionT(summon[Monad[F]].map(value)(_.map(f)))

  def flatMap[B](f: A => OptionT[F, B]): OptionT[F, B] = 
    OptionT(summon[Monad[F]].flatMap(value) {
      case Some(a) => f(a).value
      case None => summon[Monad[F]].pure(None)
    })

  def getOrElse[B >: A](default: => B): F[B] = 
    summon[Monad[F]].map(value)(_.getOrElse(default))
}

object OptionT {
  def pure[F[_]: Monad, A](a: A): OptionT[F, A] = 
    OptionT(summon[Monad[F]].pure(Some(a)))

  def none[F[_]: Monad, A]: OptionT[F, A] = 
    OptionT(summon[Monad[F]].pure(None))

  def liftF[F[_]: Monad, A](fa: F[A]): OptionT[F, A] = 
    OptionT(summon[Monad[F]].map(fa)(Some(_)))
}

// Either transformer
case class EitherT[F[_]: Monad, L, R](value: F[Either[L, R]]) {
  def map[S](f: R => S): EitherT[F, L, S] = 
    EitherT(summon[Monad[F]].map(value)(_.map(f)))

  def flatMap[S](f: R => EitherT[F, L, S]): EitherT[F, L, S] = 
    EitherT(summon[Monad[F]].flatMap(value) {
      case Right(r) => f(r).value
      case Left(l) => summon[Monad[F]].pure(Left(l))
    })

  def leftMap[M](f: L => M): EitherT[F, M, R] = 
    EitherT(summon[Monad[F]].map(value)(_.left.map(f)))
}

object EitherT {
  def pure[F[_]: Monad, L, R](r: R): EitherT[F, L, R] = 
    EitherT(summon[Monad[F]].pure(Right(r)))

  def left[F[_]: Monad, L, R](l: L): EitherT[F, L, R] = 
    EitherT(summon[Monad[F]].pure(Left(l)))

  def liftF[F[_]: Monad, L, R](fr: F[R]): EitherT[F, L, R] = 
    EitherT(summon[Monad[F]].map(fr)(Right(_)))
}

// Usage example: Combining IO and Either
type IOEither[L, R] = EitherT[IO, L, R]

def readConfig(path: String): IOEither[String, String] = 
  EitherT(IO.effect {
    try {
      Right(scala.io.Source.fromFile(path).mkString)
    } catch {
      case _: Exception => Left(s"Could not read file: $path")
    }
  })

def parseConfig(content: String): IOEither[String, Map[String, String]] = 
  EitherT(IO.pure {
    try {
      val pairs = content.lines().map(_.split("=", 2)).map(arr => arr(0) -> arr(1))
      Right(pairs.toMap)
    } catch {
      case _: Exception => Left("Invalid configuration format")
    }
  })

val program = for {
  content <- readConfig("config.properties")
  config <- parseConfig(content)
  _ <- EitherT.liftF(IO.effect(println(s"Loaded config: $config")))
} yield config

// IO.run(program.value) // Either executes and returns Either[String, Map[String, String]]

Free Monads

Free monads provide a way to build monads from functors, allowing for the separation of structure from interpretation.

// Free monad definition
enum Free[F[_], A] {
  case Pure(value: A)
  case Suspend(fa: F[Free[F, A]])

  def map[B](f: A => B): Free[F, B] = this match {
    case Pure(value) => Pure(f(value))
    case Suspend(fa) => Suspend(fa) // Note: This requires F to be a Functor
  }

  def flatMap[B](f: A => Free[F, B]): Free[F, B] = this match {
    case Pure(value) => f(value)
    case Suspend(fa) => Suspend(fa) // Note: This requires F to be a Functor
  }
}

object Free {
  def pure[F[_], A](a: A): Free[F, A] = Pure(a)

  def liftF[F[_], A](fa: F[A])(using F: Functor[F]): Free[F, A] = 
    Suspend(F.map(fa)(Pure(_)))

  def foldMap[F[_], G[_]: Monad, A](free: Free[F, A])(transform: F ~> G): G[A] = 
    free match {
      case Pure(value) => summon[Monad[G]].pure(value)
      case Suspend(fa) => 
        summon[Monad[G]].flatMap(transform(fa))(foldMap(_)(transform))
    }
}

// Natural transformation
trait ~>[F[_], G[_]] {
  def apply[A](fa: F[A]): G[A]
}

// Console DSL using Free monad
enum ConsoleOp[A] {
  case ReadLine() extends ConsoleOp[String]
  case WriteLine(line: String) extends ConsoleOp[Unit]
}

given Functor[ConsoleOp] with {
  def map[A, B](fa: ConsoleOp[A])(f: A => B): ConsoleOp[B] = fa match {
    case ConsoleOp.ReadLine() => ConsoleOp.ReadLine().asInstanceOf[ConsoleOp[B]]
    case ConsoleOp.WriteLine(line) => ConsoleOp.WriteLine(line).asInstanceOf[ConsoleOp[B]]
  }
}

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

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

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

// Interpreter for Console operations
val consoleToIO: ConsoleOp ~> IO = new (ConsoleOp ~> IO) {
  def apply[A](fa: ConsoleOp[A]): IO[A] = fa match {
    case ConsoleOp.ReadLine() => IO.effect(scala.io.StdIn.readLine())
    case ConsoleOp.WriteLine(line) => IO.effect(println(line))
  }
}

// Run the program
val ioProgram = Free.foldMap(program)(consoleToIO)
// IO.run(ioProgram)

// Alternative interpreter for testing
val testConsoleToState: ConsoleOp ~> State[List[String], *] = 
  new (ConsoleOp ~> State[List[String], *]) {
    def apply[A](fa: ConsoleOp[A]): State[List[String], A] = fa match {
      case ConsoleOp.ReadLine() => 
        State(inputs => inputs match {
          case head :: tail => (tail, head.asInstanceOf[A])
          case Nil => (Nil, "".asInstanceOf[A])
        })
      case ConsoleOp.WriteLine(line) => 
        State(inputs => (inputs, ().asInstanceOf[A])) // Simplified for testing
    }
  }

Real-World Applications

Building a Type-Safe Configuration System

// Configuration DSL using algebraic data types
enum ConfigValue {
  case StringValue(value: String)
  case IntValue(value: Int)
  case BooleanValue(value: Boolean)
  case ListValue(values: List[ConfigValue])
  case ObjectValue(fields: Map[String, ConfigValue])
}

case class ConfigPath(segments: List[String]) {
  def /(segment: String): ConfigPath = ConfigPath(segments :+ segment)
  def toString: String = segments.mkString(".")
}

enum ConfigError {
  case MissingKey(path: ConfigPath)
  case TypeError(path: ConfigPath, expected: String, actual: String)
  case ParseError(message: String)
}

// Configuration reader monad
case class ConfigReader[A](run: ConfigValue => Either[ConfigError, A]) {
  def map[B](f: A => B): ConfigReader[B] = 
    ConfigReader(config => run(config).map(f))

  def flatMap[B](f: A => ConfigReader[B]): ConfigReader[B] = 
    ConfigReader(config => run(config).flatMap(a => f(a).run(config)))
}

object ConfigReader {
  def pure[A](a: A): ConfigReader[A] = 
    ConfigReader(_ => Right(a))

  def fail[A](error: ConfigError): ConfigReader[A] = 
    ConfigReader(_ => Left(error))

  def getString(path: ConfigPath): ConfigReader[String] = 
    ConfigReader {
      case ConfigValue.StringValue(value) => Right(value)
      case other => Left(ConfigError.TypeError(path, "String", other.getClass.getSimpleName))
    }

  def getInt(path: ConfigPath): ConfigReader[Int] = 
    ConfigReader {
      case ConfigValue.IntValue(value) => Right(value)
      case other => Left(ConfigError.TypeError(path, "Int", other.getClass.getSimpleName))
    }

  def getBoolean(path: ConfigPath): ConfigReader[Boolean] = 
    ConfigReader {
      case ConfigValue.BooleanValue(value) => Right(value)
      case other => Left(ConfigError.TypeError(path, "Boolean", other.getClass.getSimpleName))
    }

  def getObject[A](path: ConfigPath)(reader: ConfigReader[A]): ConfigReader[A] = 
    ConfigReader {
      case ConfigValue.ObjectValue(fields) => 
        fields.get(path.segments.last) match {
          case Some(value) => reader.run(value)
          case None => Left(ConfigError.MissingKey(path))
        }
      case other => Left(ConfigError.TypeError(path, "Object", other.getClass.getSimpleName))
    }
}

// Usage example
case class DatabaseConfig(
  host: String,
  port: Int,
  database: String,
  ssl: Boolean
)

case class ApplicationConfig(
  appName: String,
  debug: Boolean,
  database: DatabaseConfig
)

val databaseConfigReader: ConfigReader[DatabaseConfig] = for {
  host <- ConfigReader.getString(ConfigPath(List("host")))
  port <- ConfigReader.getInt(ConfigPath(List("port")))
  database <- ConfigReader.getString(ConfigPath(List("database")))
  ssl <- ConfigReader.getBoolean(ConfigPath(List("ssl")))
} yield DatabaseConfig(host, port, database, ssl)

val applicationConfigReader: ConfigReader[ApplicationConfig] = for {
  appName <- ConfigReader.getString(ConfigPath(List("appName")))
  debug <- ConfigReader.getBoolean(ConfigPath(List("debug")))
  database <- ConfigReader.getObject(ConfigPath(List("database")))(databaseConfigReader)
} yield ApplicationConfig(appName, debug, database)

// Sample configuration
val sampleConfig = ConfigValue.ObjectValue(Map(
  "appName" -> ConfigValue.StringValue("MyApp"),
  "debug" -> ConfigValue.BooleanValue(true),
  "database" -> ConfigValue.ObjectValue(Map(
    "host" -> ConfigValue.StringValue("localhost"),
    "port" -> ConfigValue.IntValue(5432),
    "database" -> ConfigValue.StringValue("myapp"),
    "ssl" -> ConfigValue.BooleanValue(false)
  ))
))

val configResult = applicationConfigReader.run(sampleConfig)
// Right(ApplicationConfig("MyApp", true, DatabaseConfig("localhost", 5432, "myapp", false)))

Event Sourcing with Algebraic Data Types

// Event sourcing system using ADTs
enum UserEvent {
  case UserCreated(id: String, name: String, email: String, timestamp: Long)
  case EmailChanged(id: String, newEmail: String, timestamp: Long)
  case UserDeactivated(id: String, timestamp: Long)
  case UserReactivated(id: String, timestamp: Long)
}

enum UserState {
  case NonExistent
  case Active(id: String, name: String, email: String, createdAt: Long)
  case Inactive(id: String, name: String, email: String, createdAt: Long, deactivatedAt: Long)
}

// Event store monad
case class EventStore[A](run: List[UserEvent] => (List[UserEvent], A)) {
  def map[B](f: A => B): EventStore[B] = 
    EventStore(events => {
      val (newEvents, a) = run(events)
      (newEvents, f(a))
    })

  def flatMap[B](f: A => EventStore[B]): EventStore[B] = 
    EventStore(events => {
      val (newEvents1, a) = run(events)
      val (newEvents2, b) = f(a).run(newEvents1)
      (newEvents2, b)
    })
}

object EventStore {
  def pure[A](a: A): EventStore[A] = 
    EventStore(events => (events, a))

  def appendEvent(event: UserEvent): EventStore[Unit] = 
    EventStore(events => (events :+ event, ()))

  def getEvents: EventStore[List[UserEvent]] = 
    EventStore(events => (events, events))

  def getCurrentState(userId: String): EventStore[UserState] = 
    getEvents.map(events => 
      events.filter {
        case UserEvent.UserCreated(id, _, _, _) => id == userId
        case UserEvent.EmailChanged(id, _, _) => id == userId
        case UserEvent.UserDeactivated(id, _) => id == userId
        case UserEvent.UserReactivated(id, _) => id == userId
      }.foldLeft(UserState.NonExistent: UserState) { (state, event) =>
        applyEvent(state, event)
      }
    )
}

def applyEvent(state: UserState, event: UserEvent): UserState = (state, event) match {
  case (UserState.NonExistent, UserEvent.UserCreated(id, name, email, timestamp)) =>
    UserState.Active(id, name, email, timestamp)

  case (UserState.Active(id, name, _, createdAt), UserEvent.EmailChanged(_, newEmail, _)) =>
    UserState.Active(id, name, newEmail, createdAt)

  case (UserState.Active(id, name, email, createdAt), UserEvent.UserDeactivated(_, timestamp)) =>
    UserState.Inactive(id, name, email, createdAt, timestamp)

  case (UserState.Inactive(id, name, email, createdAt, _), UserEvent.UserReactivated(_, _)) =>
    UserState.Active(id, name, email, createdAt)

  case _ => state // Invalid transitions are ignored
}

// Business logic using the event store
def createUser(id: String, name: String, email: String): EventStore[UserState] = for {
  currentState <- EventStore.getCurrentState(id)
  result <- currentState match {
    case UserState.NonExistent =>
      val timestamp = System.currentTimeMillis()
      for {
        _ <- EventStore.appendEvent(UserEvent.UserCreated(id, name, email, timestamp))
        newState <- EventStore.getCurrentState(id)
      } yield newState
    case _ => 
      EventStore.pure(currentState) // User already exists
  }
} yield result

def changeEmail(id: String, newEmail: String): EventStore[UserState] = for {
  currentState <- EventStore.getCurrentState(id)
  result <- currentState match {
    case UserState.Active(_, _, currentEmail, _) if currentEmail != newEmail =>
      val timestamp = System.currentTimeMillis()
      for {
        _ <- EventStore.appendEvent(UserEvent.EmailChanged(id, newEmail, timestamp))
        newState <- EventStore.getCurrentState(id)
      } yield newState
    case state => 
      EventStore.pure(state) // No change needed or user not active
  }
} yield result

// Usage
val userOperations = for {
  _ <- createUser("user1", "Alice", "alice@example.com")
  _ <- changeEmail("user1", "alice.smith@example.com")
  _ <- EventStore.appendEvent(UserEvent.UserDeactivated("user1", System.currentTimeMillis()))
  finalState <- EventStore.getCurrentState("user1")
} yield finalState

val (finalEvents, result) = userOperations.run(List.empty)
// result: UserState.Inactive
// finalEvents: List of all events that occurred

Performance Considerations and Best Practices

Optimizing Monadic Code

// Avoid deeply nested flatMaps
// Bad
def processUser(id: String): Option[String] = 
  findUser(id).flatMap { user =>
    validateUser(user).flatMap { validUser =>
      enrichUser(validUser).flatMap { enrichedUser =>
        formatUser(enrichedUser)
      }
    }
  }

// Good - use for-comprehension
def processUser(id: String): Option[String] = for {
  user <- findUser(id)
  validUser <- validateUser(user)
  enrichedUser <- enrichUser(validUser)
  result <- formatUser(enrichedUser)
} yield result

// Or use function composition
def processUser(id: String): Option[String] = 
  findUser(id)
    .flatMap(validateUser)
    .flatMap(enrichUser)
    .flatMap(formatUser)

// Efficient error accumulation with Validated
import cats.data.Validated
import cats.implicits._

case class ValidationError(message: String)

type ValidationResult[A] = Validated[List[ValidationError], A]

def validateName(name: String): ValidationResult[String] = 
  if (name.nonEmpty) name.valid
  else List(ValidationError("Name is required")).invalid

def validateEmail(email: String): ValidationResult[String] = 
  if (email.contains("@")) email.valid
  else List(ValidationError("Invalid email")).invalid

def validateAge(age: Int): ValidationResult[Int] = 
  if (age >= 0 && age <= 150) age.valid
  else List(ValidationError("Invalid age")).invalid

// Parallel validation (accumulates all errors)
def validateUserData(name: String, email: String, age: Int): ValidationResult[User] = 
  (validateName(name), validateEmail(email), validateAge(age)).mapN(User.apply)

// Stack-safe recursive operations
@annotation.tailrec
def foldLeft[A, B](list: List[A], acc: B)(f: (B, A) => B): B = list match {
  case Nil => acc
  case head :: tail => foldLeft(tail, f(acc, head))(f)
}

// Trampolined recursion for stack safety
enum Trampoline[A] {
  case Done(value: A)
  case More(thunk: () => Trampoline[A])

  def flatMap[B](f: A => Trampoline[B]): Trampoline[B] = this match {
    case Done(value) => f(value)
    case More(thunk) => More(() => thunk().flatMap(f))
  }

  @annotation.tailrec
  final def run: A = this match {
    case Done(value) => value
    case More(thunk) => thunk().run
  }
}

object Trampoline {
  def pure[A](a: A): Trampoline[A] = Done(a)

  def suspend[A](thunk: => Trampoline[A]): Trampoline[A] = More(() => thunk)
}

// Stack-safe factorial using Trampoline
def factorial(n: Int): Trampoline[BigInt] = {
  def loop(n: Int, acc: BigInt): Trampoline[BigInt] = 
    if (n <= 1) Trampoline.pure(acc)
    else Trampoline.suspend(loop(n - 1, acc * n))

  loop(n, 1)
}

val result = factorial(10000).run // Stack-safe even for large numbers

Memory-Efficient Functional Programming

// Use lazy evaluation for infinite or large data structures
lazy val fibonacciLazy: LazyList[BigInt] = {
  def fib(a: BigInt, b: BigInt): LazyList[BigInt] = 
    a #:: fib(b, a + b)
  fib(0, 1)
}

// Take only what you need
val first100Fibs = fibonacciLazy.take(100).toList

// Use views for memory-efficient transformations
val largeRange = (1 to 1000000).view
val processed = largeRange
  .filter(_ % 2 == 0)
  .map(_ * 2)
  .take(10)
  .toList // Only materializes the final 10 elements

// Efficient string building with Builder pattern
def buildLargeString(items: List[String]): String = {
  val builder = new StringBuilder
  items.foreach(builder.append)
  builder.toString
}

// Use tail recursion for list processing
@annotation.tailrec
def reverseList[A](list: List[A], acc: List[A] = Nil): List[A] = list match {
  case Nil => acc
  case head :: tail => reverseList(tail, head :: acc)
}

// Streaming data processing with iterators
def processLargeFile(filename: String): Iterator[String] = 
  scala.io.Source.fromFile(filename)
    .getLines()
    .filter(_.nonEmpty)
    .map(_.toUpperCase)

// Only process data as needed
val results = processLargeFile("large-file.txt").take(100).toList

Conclusion

Advanced functional programming in Scala provides powerful abstractions for building robust, composable software systems. Key takeaways include:

Category Theory Foundations:

• Functors preserve structure while allowing transformation
• Applicative functors enable independent parallel computations
• Monads sequence computations with context and effects
• Understanding laws ensures correct and predictable behavior

Algebraic Data Types:

• Sum types (sealed traits/enums) model choice and alternatives
• Product types (case classes) combine multiple values
• Recursive types represent self-referential structures
• Proper modeling leads to exhaustive pattern matching and type safety

Advanced Patterns:

• Monad transformers compose effects from multiple monads
• Free monads separate structure from interpretation
• Natural transformations provide abstraction over effect types
• Type classes enable ad-hoc polymorphism and extensibility

Real-World Applications:

• Configuration systems with type-safe parsing and validation
• Event sourcing with immutable event streams
• Domain modeling with precise types and constraints
• Error handling with accumulating validation

Performance Best Practices:

• Use for-comprehensions for readable monadic composition
• Leverage lazy evaluation for efficiency
• Implement stack-safe recursion with trampolines
• Choose appropriate data structures for memory efficiency

Design Principles:

• Make illegal states unrepresentable with types
• Compose small, focused abstractions
• Separate pure and effectful computations
• Use immutable data structures by default

These advanced functional programming concepts enable the creation of more reliable, maintainable, and reasoning-friendly software systems, making complex business logic more tractable and reducing the likelihood of runtime errors through compile-time guarantees.