Functional Programming

## Learning Objectives - Understand functional programming principles - Master higher-order functions - Learn closures - Work with currying - Understand partial application ## Functional Programming Principles ### Pure Functions A pure function: - Returns the same result for the same inputs - Has no side effects (no I/O, no mutation) ```scala // Pure function def add(a: Int, b: Int): Int = a + b // Impure function (has side effect) var counter = 0 def nextInt(): Int = { counter += 1 counter } ``` ### Immutability Prefer immutable data structures: ```scala // Immutable approach val original = List(1, 2, 3) val added = 0 :: original // New list: List(0, 1, 2, 3) // Mutable approach (avoid when possible) import scala.collection.mutable val buffer = mutable.ListBuffer(1, 2, 3) buffer.prepend(0) // Mutates buffer ``` ## Higher-Order Functions Functions that take functions as parameters or return functions: ```scala def applyTwice(f: Int => Int, x: Int): Int = f(f(x)) def double(x: Int): Int = x * 2 def increment(x: Int): Int = x + 1 applyTwice(double, 3) // 12 (3 * 2 * 2) applyTwice(increment, 3) // 5 (3 + 1 + 1) ``` ### Common Higher-Order Functions ```scala val numbers = List(1, 2, 3, 4, 5) // map - transform each element numbers.map(_ * 2) // List(2, 4, 6, 8, 10) // filter - keep elements satisfying predicate numbers.filter(_ % 2 == 0) // List(2, 4) // flatMap - map then flatten numbers.flatMap(x => List(x, -x)) // List(1, -1, 2, -2, 3, -3, 4, -4, 5, -5) // fold/reduce - combine elements numbers.fold(0)(_ + _) // 15 (sum) numbers.reduce(_ * _) // 120 (product) // collect - pattern match and transform numbers.collect { case x if x % 2 == 0 => x * 2 } // List(4, 8) ``` ## Closures A closure captures variables from its environment: ```scala def multiplier(factor: Int): Int => Int = { (x: Int) => x * factor // factor is captured } val triple = multiplier(3) triple(5) // 15 val double = multiplier(2) double(5) // 10 ``` ### Mutable Capture ```scala var factor = 1 val incrementAndMultiply: Int => Int = (x: Int) => { factor += 1 x * factor } incrementAndMultiply(5) // 6 (factor becomes 2) incrementAndMultiply(5) // 15 (factor becomes 3) ``` ## Currying Converting a function with multiple parameters into a chain of functions: ```scala def add(a: Int)(b: Int): Int = a + b add(3)(5) // 8 val addFive = add(5) _ addFive(3) // 8 addFive(10) // 15 ``` ### Currying Benefits ```scala // Without currying def withLogging(f: () => Unit): () => Unit = { () => { println("Before") f() println("After") } } // With currying def withLogging(f: => Unit): Unit = { println("Before") f println("After") } def greet(): Unit = println("Hello!") withLogging(greet) ``` ## Partial Application Providing some arguments, leaving others for later: ```scala def multiply(a: Int, b: Int, c: Int): Int = a * b * c val multiplyBy2 = multiply(2, _, 3) // Partially applied multiplyBy2(5) // 30 (2 * 5 * 3) val multiplyBy6 = multiply(2, 3, _) // Partially applied multiplyBy6(5) // 30 (2 * 3 * 5) ``` ## Function Composition ### Compose ```scala val double = (x: Int) => x * 2 val addOne = (x: Int) => x + 1 val doubleAddOne = double compose addOne // (x + 1) * 2 doubleAddOne(5) // 12 ``` ### AndThen ```scala val double = (x: Int) => x * 2 val addOne = (x: Int) => x + 1 val doubleThenAddOne = double andThen addOne // (x * 2) + 1 doubleThenAddOne(5) // 11 ``` ### Using with for-expressions ```scala case class Person(name: String, age: Int, city: String) val people = List( Person("Alice", 30, "NYC"), Person("Bob", 25, "LA"), Person("Charlie", 35, "NYC") ) val nycNames = for { p <- people if p.city == "NYC" } yield p.name // List("Alice", "Charlie") ``` ## Pure Functional Data Structures ### Persistent Lists ```scala sealed trait List[+A] case object Nil extends List[Nothing] case class Cons[A](head: A, tail: List[A]) extends List[A] object List { def apply[A](as: A*): List[A] = if (as.isEmpty) Nil else Cons(as.head, apply(as.tail: _*)) def foldRight[A, B](as: List[A], z: B)(f: (A, B) => B): B = as match { case Nil => z case Cons(x, xs) => f(x, foldRight(xs, z)(f)) } } ``` ## Lazy Evaluation ### Lazy Evaluation with `lazy` ```scala lazy val expensive = { println("Computing...") 42 } println("Before") println(expensive) // Computing... then 42 println(expensive) // Just 42 ``` ### Lazy Lists (Streams) ```scala import scala.collection.immutable.LazyList def fibonacci: LazyList[Int] = { def go(a: Int, b: Int): LazyList[Int] = a #:: go(b, a + b) go(0, 1) } fibonacci.take(10).toList // List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34) ``` ## Function Types | Type | Description | |------|-------------| | `Int => Int` | Function from Int to Int | | `(Int, Int) => Int` | Function with two Int params | | `() => Unit` | Function with no params | | `Int => Boolean` | Predicate on Int | | `(Int, Int) => Boolean` | Binary predicate | ## Methods vs Functions ```scala class Calculator { def add(a: Int, b: Int): Int = a + b } val calc = new Calculator() // Method - eta expansion converts to function val addFunction: (Int, Int) => Int = calc.add _ // Direct function val add = (a: Int, b: Int) => a + b ``` ## Tail Recursion Optimization ```scala def factorial(n: Int): BigInt = { @annotation.tailrec def loop(acc: BigInt, n: Int): BigInt = { if (n <= 1) acc else loop(acc * n, n - 1) } loop(1, n) } ``` ## Summary - Functional programming emphasizes pure functions and immutability - Higher-order functions take or return functions - Closures capture environment variables - Currying splits multi-parameter functions into chains - Partial application fixes some arguments for later - Function composition creates new functions from existing ones - Lazy evaluation defers computation until needed - Tail recursion is optimized to avoid stack overflow - Prefer val over var, immutable over mutable