Scala 2 Closures and Higher-Order Functions

Explore comprehensive Scala 2 functional programming fundamentals grounded in mathematical theory. This guide covers pure functions that ensure determinism and referential transparency, enabling equational reasoning and safe parallelization. Discover higher-order functions like map, filter, and fold that accept or return functions as first-class values. Master function composition techniques using compose and andThen operators to build complex pipelines. Learn currying—the mathematical transformation of multi-argument functions into sequences of single-argument functions. Understand immutability principles, side-effect elimination, and how these concepts form the backbone of scalable, testable Scala applications through category theory and lambda calculus foundations.

---

• Pure Functions
  • Mathematical Definition
  • Formal Definition
  • Mathematical Properties
  • Substitution Model
  • Pure Functions in Mathematics
  • Key Benefits of Pure Functions
• Higher-Order Functions
  • HOF Mathematical Definition
  • Type Theory Foundation of HOF
    • Example 1: Map - The Functor HOF
    • Example 2: Filter - Predicate-Based Selection
    • Example 3: Fold - Reduction Operations
      • foldr - right-associative fold
      • foldl - left-associative fold
      • Comparing foldr vs foldl
      • Insights:
    • Example 4: Custom HOFs
    • Composition in Scala
  • HOF Mathematical Properties
  • For-Comprehensions and HOFs
  • Type Signatures of Common HOFs
• Currying
  • Lambda Calculus Foundation
  • Uncurrying
  • Code Examples
    • Example 1: Manual Currying
    • Example 2: Scala’s Built-in Currying
    • Example 3: Converting Between Curried and Uncurried

---

Functional Programming (FP) is a programming paradigm based on mathematical functions where computation is treated as the evaluation of mathematical functions avoiding changing state and mutable data. This guide explores five fundamental FP concepts in Scala 2 with their mathematical foundations.

Core Principles of Functional Programming

1. Functions are first-class values: Functions can be passed as arguments, returned from other functions, and assigned to variables
2. Immutability: Data structures don’t change after creation
3. No side effects: Pure functions don’t modify external state
4. Referential Transparency: Expressions can be replaced by their values without changing program behavior

Pure Functions

Mathematical Definition

A pure function is a mathematical function where:

\[f: A \rightarrow B\]

Such that:

1. Determinism: $\forall x \in A, f(x)$ always produces the same output $y \in B$
2. No Side Effects: $f$ doesn’t modify any state outside its scope
3. Referential Transparency: For any program $p$, all occurrences of $f(x)$ can be replaced by its result without changing $p$’s meaning

Formal Definition

Referential Transparency (RT): An expression $e$ is referentially transparent if, for all programs $p$, all occurrences of $e$ in $p$ can be replaced by the result of evaluating $e$ without affecting the meaning of $p$.¹

Purity: A function $f$ is pure if the expression $f(x)$ is referentially transparent for all referentially transparent $x$.¹

Mathematical Properties

---
config:
  look: neo
  theme: default
---
graph TB
    A[Pure Function Properties] --> B[Determinism]
    A --> C[No Side Effects]
    A --> D[Referential Transparency]
    B --> E["∀x: f(x) = constant"]
    C --> F["No I/O, mutations, or exceptions"]
    D --> G["Can substitute f(x) with its result"]
    style A fill:#e1f5ff
    style B fill:#fff4e1
    style C fill:#fff4e1
    style D fill:#fff4e1

Substitution Model

Pure functions enable equational reasoning through the substitution model:

\[\begin{align} \text{Given: } & f(x) = x^2 \\ \text{Then: } & f(3) + f(3) \\ & = 9 + f(3) \quad \text{(substitute first)} \\ & = 9 + 9 \quad \text{(substitute second)} \\ & = 18 \end{align}\]

for example,

// Pure Function - Always returns the same output for the same input
def square(x: Int): Int = x * x

// Test purity
val result1 = square(5)  // 25
val result2 = square(5)  // 25
// result1 == result2 always true

defined function square
result1: Int = 25
result2: Int = 25

Mathematical proof:

square(5) = 5 * 5 = 25

NOTE: Can always replace square(5) with 25

Pure function using internal mutable state (hidden from outside).

Pure Functions in Mathematics

Mathematical Concept	Scala Example	Property
$f(x) = x + 1$	def inc(x: Int) = x + 1	Successor function
$f(x, y) = x + y$	def add(x: Int, y: Int) = x + y	Addition
$f(x) = x^2$	def square(x: Int) = x * x	Quadratic
$f(s) = |s|$	def length(s: String) = s.length	String length
$f(x) = e^x$	def exp(x: Double) = math.exp(x)	Exponential

Key Benefits of Pure Functions

1. Testability: Easy to test - same input always produces the same output
2. Parallelisation: Can safely run in parallel (no shared mutable state)
3. Memoization: Results can be cached
4. Reasoning: Enable algebraic reasoning and equational substitution
5. Composition: Can combine pure functions to create complex behaviour

---
config:
  look: neo
  theme: default
---
mindmap
  root((Pure Functions))
    Benefits
      Easy Testing
        Predictable
        No Mocks Needed
      Parallelization
        Thread Safe
        No Race Conditions
      Caching
        Memoization
        Performance
    Properties
      Deterministic
      No Side Effects
      Referential Transparency
    Applications
      Mathematical Computations
      Data Transformations
      Functional Pipelines

---

Higher-Order Functions

Morphisms are simply arrows or mappings between objects in a category. Think of them as generalized functions. When we say “objects are types and morphisms are functions”:

• Objects = Types (Int, String, List[A], etc.)
• Morphisms = Functions between those types

def length: String => Int

This is a morphism from the object String to the object Int.

String —-length—-> Int (object) (morphism) (object)

A higher-order function like map is a morphism in a “higher” category:

def map[A, B](f: A => B): List[A] => List[B]
// or curried version
def map[A, B](f: A => B)(xs: List[A]): List[B]

Here:

• Objects are themselves function types: (A => B), (List[A] => List[B])
• Morphism is map, which maps between these function objects

(A => B) ----map----> (List[A] => List[B])

HOF Mathematical Definition

A higher-order function (HOF) is a function that:

1. Takes one or more functions as arguments, or
2. Returns a function as its result

\[\text{HOF}: (A \rightarrow B) \rightarrow C \text{ or } A \rightarrow (B \rightarrow C)\]

In category theory, HOFs are morphisms in the category of functions where objects are types and morphisms are functions.²

Type Theory Foundation of HOF

In the simply typed lambda calculus, if $\tau_1, \tau_2, \tau_3$ are types:

\[f: (\tau_1 \rightarrow \tau_2) \rightarrow \tau_3 \text{ is a HOF}\]

This means $f$ accepts a function of type $\tau_1 \rightarrow \tau_2$ and produces a value of type $\tau_3$.

Examples

1. Map operation (Functor)
2. Filter operation
3. Fold operation:

Example 1: Map - The Functor HOF³

Map operation (Functor):

\[\text{map}: (A \rightarrow B) \rightarrow [A] \rightarrow [B]\]

This reads as: “map takes a function from A to B, then takes a list of A’s, and returns a list of B’s”.

The arrows represent currying - map doesn’t take all arguments at once, but returns functions:

• Takes (A → B) - a function from type A to type B
• Returns a function that takes [A] - a list of A’s
• Which returns [B] - a list of B’s

Behaviour:

\[\text{map}\ f\ [x_1, x_2, ..., x_n] = [f(x_1), f(x_2), ..., f(x_n)]\]

Apply function f to each element in the list.

The map applies a function to each element

def map[A, B](f: A => B)(xs: List[A]): List[B] = xs match {
  case Nil => Nil
  case head :: tail => f(head) :: map(f)(tail)
}

Type Parameters: [A, B] - generic types matching the math notation

Curried Syntax: Two parameter lists (f: A => B)(xs: List[A]) implements the curried arrows:

• First takes function f: A => B (matching A → B)
• Then takes list xs: List[A] (matching [A])
• Returns List[B] (matching [B])

The recursive case implements the mathematical definition:

• f(head) - apply f to first element (like f(x₁))
• map(f)(tail) - recursively map over remaining elements (like [f(x₂), ..., f(xₙ)])
• :: - cons operator joins them together

Example execution is

map(x => x * 2)(List(1, 2, 3))

Traces to:

f(1) :: map(f)(List(2, 3))
2 :: f(2) :: map(f)(List(3))
2 :: 4 :: f(3) :: map(f)(Nil)
2 :: 4 :: 6 :: Nil
List(2, 4, 6)

This matches the math: map (*2) [1,2,3] = [2, 4, 6] ✓

// Using map
val numbers = List(1, 2, 3)
val squared = map((x: Int) => x * 2)(numbers)
// Result: List(1, 4, 9, 16, 25)

// Mathematical property (Functor law):
// map(id) == id
// map(f ∘ g) == map(f) ∘ map(g)

numbers: List[Int] = List(1, 2, 3)
squared: List[Int] = List(2, 4, 6)

Scala standard library usage

val nums = List(1, 2, 3)

// map with named function
def double(x: Int): Int = x * 2
nums.map(double)  // List(2, 4, 6, 8, 10)

nums: List[Int] = List(1, 2, 3)
defined function double
res14_2: List[Int] = List(2, 4, 6)

Example 2: Filter - Predicate-Based Selection³

filter keeps elements satisfying a predicate

\[\text{filter}: (A \rightarrow \text{Bool}) \rightarrow [A] \rightarrow [A]\]

This reads as: “filter takes a predicate function from A to Boolean, then takes a list of A’s, and returns a list of A’s”

Key difference from map: the input and output list types are the same ([A] → [A]) because we’re selecting elements, not transforming them.

The currying structure:

• Takes (A → Bool) - a predicate function that tests elements
• Returns a function that takes [A] - a list of A’s
• Which returns [A] - a filtered list of A’s

Behaviour (List Comprehension):

This is list comprehension notation meaning: “build a list containing all elements x drawn from xs where the predicate p(x) is true”

\[\text{filter}\ p\ xs = [x\ |\ x \leftarrow xs, p(x)]\]

def filter[A](p: A => Boolean)(xs: List[A]): List[A] = xs match {
  case Nil => Nil
  case head :: tail => 
    if (p(head)) head :: filter(p)(tail)
    else filter(p)(tail)
}

defined function filter

Type Parameter: [A] - single generic type (input and output are same type)

Curried Syntax: (p: A => Boolean)(xs: List[A]) implements:

• First takes predicate p: A => Boolean (matching A → Bool)
• Then takes list xs: List[A] (matching [A])
• Returns List[A] (matching [A])

Pattern Matching Implementation:

The recursive logic implements the list comprehension:

• Test: if (p(head)) - checks if predicate holds for current element
• Include: head :: filter(p)(tail) - keep element and continue
• Exclude: filter(p)(tail) - skip element and continue
• Eventually builds a list of only elements where p(x) was true

// Using filter
val numbers = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

// Keep even numbers
val evens = filter((x: Int) => x % 2 == 0)(numbers)
// Result: List(2, 4, 6, 8, 10)

// Mathematical definition as list comprehension:
// filter p xs = [x | x ← xs, p x]

numbers: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
evens: List[Int] = List(2, 4, 6, 8, 10)

Example Execution

filter(x => x > 2)(List(1, 2, 3, 4))

Traces to:

p(1) = false → filter(p)(List(2, 3, 4))
p(2) = false → filter(p)(List(3, 4))
p(3) = true  → 3 :: filter(p)(List(4))
p(4) = true  → 3 :: 4 :: filter(p)(Nil)
3 :: 4 :: Nil
List(3, 4)

Scala Standard library usage:

// Practical examples
val numbers = List(-3, -2, -1, 0, 1, 2, 3, 4, 5)

// Filter positive numbers
numbers.filter(_ > 0)  // List(1, 2, 3)

// Filter even numbers
numbers.filter(x => x % 2 == 0)  // List(-2, 0, 2, 4)

// Chain filter operations
numbers
  .filter(_ > 0)        // List(1, 2, 3, 4, 5)
  .filter(_ % 2 == 0)   // List(2, 4)

numbers: List[Int] = List(-3, -2, -1, 0, 1, 2, 3, 4, 5)
res18_1: List[Int] = List(1, 2, 3, 4, 5)
res18_2: List[Int] = List(-2, 0, 2, 4)
res18_3: List[Int] = List(2, 4)

This matches the math: \(\text{filter}\ (>2)\ [1,2,3,4] = [x\ |\ x \leftarrow [1,2,3,4], x > 2] = [3, 4]\)

Example 3: Fold - Reduction Operations³

foldr - right-associative fold

\[\text{foldr}: (A \rightarrow B \rightarrow B) \rightarrow B \rightarrow [A] \rightarrow B\]

This reads as: “foldr takes a combining function, then an initial value, then a list, and returns a single accumulated value”

The currying structure (three levels):

• Takes (A → B → B) - a combining function that takes an element of type A and an accumulator of type B, returning a new B
• Then takes B - an initial/accumulator value
• Then takes [A] - a list of A’s
• Returns B - a single folded result

Behaviour (Right-Associative):

\[\text{foldr}\ (\oplus)\ a\ [x_1, x_2, ..., x_n] = x_1 \oplus (x_2 \oplus ... (x_n \oplus a))\]

Works right-to-left, with parentheses showing association from the right. The rightmost element xₙ is combined with the initial value first, then that result is combined with xₙ₋₁, and so on.

def foldr[A, B](f: (A, B) => B)(z: B)(xs: List[A]): B = xs match {
  case Nil => z
  case head :: tail => f(head, foldr(f)(z)(tail))
}

// Mathematical notation:
// foldr (⊕) a [x₁, x₂, ..., xₙ] = x₁ ⊕ (x₂ ⊕ ... (xₙ ⊕ a))

defined function foldr

Type Parameters: [A, B] - two types (list elements and accumulator can differ)

Three Parameter Lists (Curried):

• (f: (A, B) => B) - combining function (matching A → B → B)
• (z: B) - initial/”zero” value (matching the B)
• (xs: List[A]) - input list (matching [A])
• Returns B - folded result

The recursive case implements right-associativity:

• foldr(f)(z)(tail) - first recursively fold the tail (processes right side)
• f(head, ...) - then combine head with that result (processes left side)
• This creates the structure: head ⊕ (recursive_result)

Example Execution

// Practical fold examples
val numbers = List(1, 2, 3, 4, 5)
// Product using foldRight
val product = numbers.foldRight(1)(_ * _)  // 120
// Evaluation: 1 * (2 * (3 * (4 * (5 * 1))))

numbers: List[Int] = List(1, 2, 3, 4, 5)
product: Int = 120

see the trace below for the following

foldr((x: Int, acc: Int) => x + acc)(0)(List(1, 2, 3))

res34: Int = 6

Traces to:

f(1, foldr(f)(0)(List(2, 3)))
f(1, f(2, foldr(f)(0)(List(3))))
f(1, f(2, f(3, foldr(f)(0)(Nil))))
f(1, f(2, f(3, 0)))
f(1, f(2, 3))
f(1, 5)
6

This matches the math: \(\text{foldr}\ (+)\ 0\ [1,2,3] = 1 + (2 + (3 + 0)) = 1 + (2 + 3) = 1 + 5 = 6\) ✓

Visualising Right Association

For foldr (⊕) a [x₁, x₂, x₃]:

    x₁ ⊕ (x₂ ⊕ (x₃ ⊕ a))
    │      │      │
    │      │      └─ combines first
    │      └──────── combines second  
    └─────────────── combines last

foldl - left-associative fold

\[\text{foldl}: (B \rightarrow A \rightarrow B) \rightarrow B \rightarrow [A] \rightarrow B\]

This reads as: “foldl takes a combining function, then an initial value, then a list, and returns a single accumulated value”

The currying structure (three levels):

• Takes (B → A → B) - a combining function that takes an accumulator of type B and an element of type A, returning a new B
  • Note: Arguments are reversed compared to foldr!
• Then takes B - an initial/accumulator value
• Then takes [A] - a list of A’s
• Returns B - a single folded result

Behaviour (Left-Associative):

\[\text{foldl}\ (\oplus)\ a\ [x_1, x_2, ..., x_n] = ((...((a \oplus x_1) \oplus x_2) ...) \oplus x_n)\]

Works left-to-right, with parentheses showing association from the left. The leftmost element x₁ is combined with the initial value a first, then that result is combined with x₂, and so on.

// foldl - left-associative fold
def foldl[A, B](f: (B, A) => B)(z: B)(xs: List[A]): B = xs match {
  case Nil => z
  case head :: tail => foldl(f)(f(z, head))(tail)
}

// Mathematical notation:
// foldl (⊕) a [x₁, x₂, ..., xₙ] = (((a ⊕ x₁) ⊕ x₂) ... ⊕ xₙ)

defined function foldl

Type Parameters: [A, B] - two types (list elements and accumulator can differ)

Three Parameter Lists (Curried):

• (f: (B, A) => B) - combining function with accumulator first (matching B → A → B)
• (z: B) - initial/”zero” value (matching the B)
• (xs: List[A]) - input list (matching [A])
• Returns B - folded result

Example Execution

The recursive case implements left-associativity:

• f(z, head) - first combine accumulator with head (processes left side)
• foldl(f)(...)(tail) - then recursively fold tail with new accumulator
• This creates the structure: (previous_result) ⊕ head

foldl((acc: Int, x: Int) => acc + x)(0)(List(1, 2, 3)) // traced

res36: Int = 6

Traces to:

foldl(f)(f(0, 1))(List(2, 3))
foldl(f)(1)(List(2, 3))
foldl(f)(f(1, 2))(List(3))
foldl(f)(3)(List(3))
foldl(f)(f(3, 3))(Nil)
foldl(f)(6)(Nil)
6

This matches the math: \(\text{foldl}\ (+)\ 0\ [1,2,3] = ((0 + 1) + 2) + 3 = (1 + 2) + 3 = 3 + 3 = 6\) ✓

Visualising Left Association

For foldl (⊕) a [x₁, x₂, x₃]:

    ((a ⊕ x₁) ⊕ x₂) ⊕ x₃
     │         │       │
     │         │       └─ combines last
     │         └──────── combines second  
     └─────────────────── combines first

For example, Building a reversed list with foldLeft

val reversed = numbers.foldLeft(List.empty[Int])((acc, x) => x :: acc)
// Result: List(5, 4, 3, 2, 1)

reversed: List[Int] = List(5, 4, 3, 2, 1)

Scala Standard library usage:

// Practical fold examples
val numbers = List(1, 2, 3, 4, 5)

// Sum using foldLeft
val sum = numbers.foldLeft(0)(_ + _)  // 15
// Evaluation: ((((0 + 1) + 2) + 3) + 4) + 5

// Product using foldRight
val product = numbers.foldRight(1)(_ * _)  // 120
// Evaluation: 1 * (2 * (3 * (4 * (5 * 1))))

// Building a reversed list with foldLeft
val reversed = numbers.foldLeft(List.empty[Int])((acc, x) => x :: acc)
// Result: List(5, 4, 3, 2, 1)

numbers: List[Int] = List(1, 2, 3, 4, 5)
sum: Int = 15
product: Int = 120
reversed: List[Int] = List(5, 4, 3, 2, 1)

Defining common operations with fold

def sum(xs: List[Int]): Int = xs.foldRight(0)(_ + _)

def product(xs: List[Int]): Int = xs.foldRight(1)(_ * _)

def length[A](xs: List[A]): Int = xs.foldRight(0)((_, acc) => acc + 1)

def concatenate[A](xss: List[List[A]]): List[A] = xss.foldRight(List.empty[A])(_ ++ _)

// Example usage
sum(List(1, 2, 3, 4, 5))           // 15
product(List(1, 2, 3, 4, 5))       // 120
length(List('a', 'b', 'c'))        // 3
concatenate(List(List(1,2), List(3,4)))  // List(1, 2, 3, 4)

defined function sum
defined function product
defined function length
defined function concatenate
res37_4: Int = 15
res37_5: Int = 120
res37_6: Int = 3
res37_7: List[Int] = List(1, 2, 3, 4)

Comparing foldr vs foldl

foldr: x₁ ⊕ (x₂ ⊕ (x₃ ⊕ a))

• Right-associative
• Processes right side first (via recursion)
• Function signature: (A, B) => B

foldl: ((a ⊕ x₁) ⊕ x₂) ⊕ x₃

• Left-associative
• Processes left side first (via accumulator)
• Function signature: (B, A) => B

Example Where Order Matters

// Division is NOT associative
foldr((x: Int, acc: Int) => x / acc)(1)(List(8, 4, 2))
// 8 / (4 / (2 / 1)) = 8 / (4 / 2) = 8 / 2 = 4

foldl((acc: Int, x: Int) => acc / x)(64)(List(4, 2, 2))
// ((64 / 4) / 2) / 2 = (16 / 2) / 2 = 8 / 2 = 4

res28_0: Int = 4
res28_1: Int = 4

Different structure, potentially different results!

Example: Building a Reversed List

foldl((acc: List[Int], x: Int) => x :: acc)(Nil)(List(1, 2, 3))

res29: List[Int] = List(3, 2, 1)

((Nil :: 1) :: 2) :: 3
(List(1) :: 2) :: 3
List(2, 1) :: 3
List(3, 2, 1)

This reverses the list! In fact, foldl (flip (::)) Nil xs = reverse xs

Insights:

• foldl is tail-recursive in this implementation - the recursive call is the last operation, making it more memory efficient
• Left-associative: processes list from left to right via accumulator
• Accumulator-first: the function takes (B, A) not (A, B) - accumulator is first argument
• For associative operations (like +, *), foldr and foldl produce the same result
• For non-associative operations (like -, /, ::) they produce different results
• In practice: foldl is often preferred for efficiency (tail-recursive), but foldr works on infinite lists

Example 4: Custom HOFs

A HOF that applies a function n times.

The applyNTimes function implements repeated function composition or function exponentiation:

\[f^n(x) = \underbrace{f \circ f \circ \cdots \circ f}_{n \text{ times}}(x)\]

More explicitly:

• $f^0(x) = x$ (identity - apply 0 times)
• $f^1(x) = f(x)$ (apply once)
• $f^2(x) = f(f(x))$ (apply twice)
• $f^3(x) = f(f(f(x)))$ (apply three times)
• $f^n(x) = f(f^{n-1}(x))$ (recursive definition)

in Mathematics

\[\text{applyNTimes}: (A \rightarrow A) \rightarrow \mathbb{N} \rightarrow (A \rightarrow A)\]

Reads as: “Takes an endomorphism (function from A to itself) and a natural number, returns another endomorphism”

Type Analysis

• Input 1: f: A => A - an endomorphism (function that maps type A to itself)
• Input 2: n: Int - number of times to compose f
• Output: A => A - a new function that applies f exactly n times

The loop helper function:

\[\text{loop}(x, k) = \begin{cases} x & \text{if } k \leq 0 \\ \text{loop}(f(x), k-1) & \text{if } k > 0 \end{cases}\]

This implements: $\text{loop}(x, n) = f^n(x)$

def applyNTimes[A](f: A => A, n: Int): A => A = {
  def loop(x: A, remaining: Int): A = {
    if (remaining <= 0) x
    else loop(f(x), remaining - 1)
  }
  (x: A) => loop(x, n)
}

defined function applyNTimes

Execution trace for loop(x, 3):

loop(x, 3)
→ loop(f(x), 2)
→ loop(f(f(x)), 1)
→ loop(f(f(f(x))), 0)
→ f(f(f(x)))

val increment: Int => Int = x => x + 1

val addFive = applyNTimes(increment, 5)
// addFive is equivalent to: x => x + 1 + 1 + 1 + 1 + 1

addFive(10)  // Output: 15

increment: Int => Int = ammonite.$sess.cmd40$Helper$$Lambda$2754/0x000000012c898bc8@7d57e5ae
addFive: Int => Int = ammonite.$sess.cmd38$Helper$$Lambda$2750/0x000000012c897908@612c3a59
res40_2: Int = 15

\[\begin{aligned} \text{addFive}(10) &= \text{increment}^5(10) \\ &=\text{increment}(\text{increment}(\text{increment}(\text{increment}(\text{increment}(10))))) \\ &=\text{increment}(\text{increment}(\text{increment}(\text{increment}(11)))) \\ &=\text{increment}(\text{increment}(\text{increment}(12))) \\ &=\text{increment}(\text{increment}(13)) \\ &=\text{increment}(14) \\ &= 15 \end{aligned}\]

Function design properties:

1: Identity Law

\(\text{applyNTimes}(f, 0) = \text{id}\) Where $\text{id}(x) = x$ for all $x$

val identityFunc = applyNTimes(increment, 0)
identityFunc(10)

identityFunc: Int => Int = ammonite.$sess.cmd38$Helper$$Lambda$2750/0x000000012c897908@6a7a462
res43_1: Int = 10

2: Composition Law

\[\text{applyNTimes}(f, m + n) = \text{applyNTimes}(f, m) \circ \text{applyNTimes}(f, n)\]

val add3 = applyNTimes(increment, 3)
val add5 = applyNTimes(increment, 5)
val add8 = applyNTimes(increment, 8)

// These are equivalent:
add8(10)           // 18
add5(add3(10))     // 18

add3: Int => Int = ammonite.$sess.cmd38$Helper$$Lambda$2750/0x000000012c897908@447f7c8f
add5: Int => Int = ammonite.$sess.cmd38$Helper$$Lambda$2750/0x000000012c897908@150f8d6c
add8: Int => Int = ammonite.$sess.cmd38$Helper$$Lambda$2750/0x000000012c897908@7ddc39a
res44_3: Int = 18
res44_4: Int = 18

3: Recursive Structure \(f^n = f \circ f^{n-1}\)

This is exactly what the loop function implements through tail recursion.

In category theory, applyNTimes works with endomorphisms in a category:

• Objects: Types (like Int, String, etc.)
• Morphisms: Functions between types
• Endomorphism: A morphism from an object to itself (A => A)

The function creates a monoid structure:

• Binary operation: Function composition $\circ$
• Identity element: $f^0 = \text{id}$
• Closure: $f^m \circ f^n = f^{m+n}$

Tail Recursion Optimisation

The loop function is tail-recursive because:

• The recursive call is the last operation
• No additional computation after the recursive call returns
• Scala compiler can optimise it to a loop (with @tailrec annotation)

import scala.annotation.tailrec

def applyNTimes[A](f: A => A, n: Int): A => A = {
  @tailrec
  def loop(x: A, remaining: Int): A = {
    if (remaining <= 0) x
    else loop(f(x), remaining - 1)
  }
  (x: A) => loop(x, n)
}

import scala.annotation.tailrec


defined function applyNTimes

Composition in Scala

Understanding Function Composition in Scala

Function composition forms a category:

Category of Types and Functions:

• Objects: Types (Int, String, Boolean, etc.)
• Morphisms: Functions between types
• Composition: Function composition operator
• Identity: Identity function for each type

Category Laws:

1. Associativity: $(f \circ g) \circ h = f \circ (g \circ h)$
2. Identity: $f \circ \text{id}_A = f = \text{id}_B \circ f$ for $f: A \to B$

This makes function composition a fundamental operation in functional programming.

In mathematics, function composition is denoted by the symbol $\circ$ (circle):

\[(f \circ g)(x) = f(g(x))\]

Read as: “f composed with g, applied to x, equals f of g of x”

Key points:

• Apply $g$ first to $x$
• Then apply $f$ to the result
• The right function ($g$) is applied first
• Composition flows right-to-left

x  →  [g]  →  g(x)  →  [f]  →  f(g(x))
      apply g first    then apply f

For composition $f \circ g$ to be valid: \(f: B \rightarrow C\) \(g: A \rightarrow B\) \(f \circ g: A \rightarrow C\)

The output type of $g$ must match the input type of $f$.

def compose[A, B, C](f: B => C, g: A => B): A => C = {
  (x: A) => f(g(x))
}

defined function compose

Type Analysis

Type signature: \(\text{compose}: (B \rightarrow C) \rightarrow (A \rightarrow B) \rightarrow (A \rightarrow C)\)

• Parameter 1: f: B => C - function that transforms B to C
• Parameter 2: g: A => B - function that transforms A to B
• Returns: A => C - a new function that transforms A to C

How It Works

The function returns a closure (lambda):

(x: A) => f(g(x))

This lambda:

1. Takes an argument x of type A
2. Applies g to get a value of type B
3. Applies f to get a final value of type C

Examples:

val addOne = (x: Int) => x + 1
val double = (x: Int) => x * 2
val addOneThenDouble = compose(double, addOne)
addOneThenDouble(5)

addOne: Int => Int = ammonite.$sess.cmd49$Helper$$Lambda$2790/0x000000012c8a4000@54d5fa77
double: Int => Int = ammonite.$sess.cmd49$Helper$$Lambda$2791/0x000000012c8a43e8@27a2a472
addOneThenDouble: Int => Int = ammonite.$sess.cmd47$Helper$$Lambda$2786/0x000000012c89ed08@7da32905
res49_3: Int = 12

Type flow:

• addOne: Int => Int (matches A => B where A=Int, B=Int)
• double: Int => Int (matches B => C where B=Int, C=Int)
• addOneThenDouble: Int => Int (resulting A => C)

Execution trace:

\[\begin{flalign*} \text{addOneThenDouble}(5) &= \text{double}(\text{addOne}(5)) \\ &= \text{double}(5 + 1) \\ &= \text{double}(6) \\ &= 6 \times 2 \\ &= 12 \end{flalign*}\]

Scala provides two composition methods in the standard library:

Concept	Mathematical	Scala compose	Scala andThen
Notation	$f \circ g$	f compose g	g andThen f
Meaning	$f(g(x))$	f(g(x))	f(x) then g
Flow	Right-to-left	Right-to-left	Left-to-right
Natural?	Math traditional	Math traditional	More intuitive

1: compose - Right-to-Left (Mathematical Order)

val f = addOne compose double
// Equivalent to: (x: Int) => addOne(double(x))

f: Int => Int = scala.Function1$$Lambda$2796/0x000000012c8a1118@28b3e02d

mathamatically

\(f = \text{addOne} \circ \text{double}\) \(f(x) = \text{addOne}(\text{double}(x))\)

Execution:

f(5)  // addOne(double(5))
      // = addOne(5 * 2)
      // = addOne(10)
      // = 10 + 1
      // = 11

Flow diagram:

5  →  [double]  →  10  →  [addOne]  →  11
      apply first       apply second

2: andThen - Left-to-Right (Pipeline Order)

val g = addOne andThen double
// Equivalent to: (x: Int) => double(addOne(x))

g: Int => Int = scala.Function1$$Lambda$766/0x000000012c5360b0@7d14a8aa

mathamatically

\(g = \text{double} \circ \text{addOne}\) \(g(x) = \text{double}(\text{addOne}(x))\)

Execution:

g(5)  // double(addOne(5))
      // = double(5 + 1)
      // = double(6)
      // = 6 * 2
      // = 12

Flow diagram:

5  →  [addOne]  →  6  →  [double]  →  12
      apply first      apply second

HOF Mathematical Properties

Property	Mathematical Form	Code Example
Map Composition	$\text{map}(f \circ g) = \text{map}(f) \circ \text{map}(g)$	xs.map(g).map(f) == xs.map(f compose g)
Map Identity	$\text{map}(\text{id}) = \text{id}$	xs.map(x => x) == xs
Filter Composition	$\text{filter}(p) \circ \text{filter}(q) = \text{filter}(q) \circ \text{filter}(p)$	xs.filter(p).filter(q) == xs.filter(q).filter(p)
Fold Fusion	$\text{map}(f) \circ \text{fold}(g)(z) = \text{fold}(g \circ f)(z)$	Optimization technique

For-Comprehensions and HOFs⁴

The for comprehension is syntactic sugar for HOF chains

for {
    x <- List(1,2,3)
    y <- List(10, 20)
    if x * y > 10 // Guard
} yield x * y

res53: List[Int] = List(20, 20, 40, 30, 60)

Desugars to:

List(1,2,3).flatMap(x => List(10,20).filter( y => x * y > 10).map( y => x * y))

res60: List[Int] = List(20, 20, 40, 30, 60)

Type Signatures of Common HOFs

Function	Type Signature	Description
map	[A, B](f: A => B): List[A] => List[B]	Apply function to each element
filter	[A](p: A => Boolean): List[A] => List[A]	Keep elements satisfying predicate
foldLeft	[A, B](z: B)(f: (B, A) => B): List[A] => B	Left-associative reduction
foldRight	[A, B](z: B)(f: (A, B) => B): List[A] => B	Right-associative reduction
flatMap	[A, B](f: A => List[B]): List[A] => List[B]	Map then flatten
find	[A](p: A => Boolean): List[A] => Option[A]	Find first matching element
exists	[A](p: A => Boolean): List[A] => Boolean	Check if any element matches
forall	[A](p: A => Boolean): List[A] => Boolean	Check if all elements match

Currying

Mathematically:

Currying is the transformation of a function with multiple arguments into a sequence of functions, each taking a single argument.⁵

Named after mathematician Haskell Curry, currying transforms:

\[f: A \times B \times C \rightarrow D\]

Into:

\[\text{curry}(f): A \rightarrow (B \rightarrow (C \rightarrow D))\]

This isomorphism is expressed as:

\[\text{Hom}(A \times B, C) \cong \text{Hom}(A, C^B)\]

Where $C^B$ denotes the exponential object (function type $B \rightarrow C$).

Lambda Calculus Foundation

In lambda calculus, currying is a natural consequence of functions only taking one argument:

\[\begin{align} \lambda xy.\ x + y &\equiv \lambda x.(\lambda y.\ x + y) \\ \text{apply to 3: } &(\lambda x.(\lambda y.\ x + y))\ 3 \\ &= \lambda y.\ 3 + y \end{align}\]

Uncurrying

The inverse transformation:

\[\text{uncurry}: (A \rightarrow (B \rightarrow C)) \rightarrow ((A \times B) \rightarrow C)\]

Code Examples

Example 1: Manual Currying⁵

// Regular multi-parameter function
def add(x: Int, y: Int, z: Int): Int = x + y + z

// Manually curried version
def addCurried(x: Int): Int => Int => Int = {
  (y: Int) => {
    (z: Int) => {
      x + y + z
    }
  }
}

// Using the curried version
val addFive = addCurried(5)        // Returns function: Int => Int => Int
val addFiveSeven = addFive(7)      // Returns function: Int => Int
val result = addFiveSeven(3)       // Returns: 15

// Or in one line:
addCurried(5)(7)(3)  // 15

// Mathematical evaluation:
// addCurried(5)(7)(3)
// = ((x => y => z => x+y+z)(5))(7)(3)
// = (y => z => 5+y+z)(7)(3)
// = (z => 5+7+z)(3)
// = 5+7+3 = 15

defined function add
defined function addCurried
addFive: Int => Int => Int = ammonite.$sess.cmd62$Helper$$Lambda$3713/0x000000012cb02650@6f83cc5f
addFiveSeven: Int => Int = ammonite.$sess.cmd62$Helper$$Lambda$3714/0x000000012cb02a18@21cb32c7
result: Int = 15
res62_5: Int = 15

Example 2: Scala’s Built-in Currying⁵

// Scala syntax for curried functions (multiple parameter lists)
def multiply(x: Int)(y: Int)(z: Int): Int = x * y * z

// Partial application at each level
val timesTen = multiply(10) _      // Int => Int => Int
val timesTenFive = timesTen(5)     // Int => Int
val result = timesTenFive(2)       // 100

// Can also apply all at once
multiply(10)(5)(2)  // 100

// Type signatures:
// multiply: (x: Int)(y: Int)(z: Int): Int
// multiply(10): Int => Int => Int
// multiply(10)(5): Int => Int
// multiply(10)(5)(2): Int

defined function multiply
timesTen: Int => Int => Int = ammonite.$sess.cmd63$Helper$$Lambda$3719/0x000000012cb03f68@48891e11
timesTenFive: Int => Int = ammonite.$sess.cmd63$Helper$$Lambda$3720/0x000000012cb04338@23033b53
result: Int = 100
res63_4: Int = 100

Example 3: Converting Between Curried and Uncurried¹

// Generic curry and uncurry functions

// Curry: Convert (A, B) => C to A => B => C
def curry[A, B, C](f: (A, B) => C): A => B => C = {
  (a: A) => (b: B) => f(a, b)
}

// Uncurry: Convert A => B => C to (A, B) => C
def uncurry[A, B, C](f: A => B => C): (A, B) => C = {
  (a: A, b: B) => f(a)(b)
}

// Example usage
val add: (Int, Int) => Int = (x, y) => x + y
val addCurried: Int => Int => Int = curry(add)
val addUncurried: (Int, Int) => Int = uncurry(addCurried)

// Test
add(3, 4)              // 7
addCurried(3)(4)       // 7
addUncurried(3, 4)     // 7

// Function1 has built-in curried method
val multiply = (x: Int, y: Int, z: Int) => x * y * z
val multiplyCurried = multiply.curried
// Type: Int => Int => Int => Int÷

1. Functional Programming in Scala, Ch. 1: “What is functional programming?” → “The benefits of FP: a simple example”, p. 3-12 ↩ ↩² ↩³

2. Category Theory, Ch. 9: “Functors and Natural Transformations” → p. 156-161 ↩

3. Bird & Wadler: Introduction to Functional Programming, Ch. 3: “Lists” → “Map and filter”, p. 61-65 ↩ ↩² ↩³

4. Programming in Scala Fourth Edition, Ch. 23: “For Expressions Revisited” → p. 528-545 ↩

5. Scala in Depth, Ch. 11: “Patterns in functional programming” → “Currying and applicative style”, p. 266-268 ↩ ↩² ↩³