# Functional Programming
## Paradigms — The Codex Coding
**URL:** https://thecodex.expert/coding/paradigms/functional/
**Type:** paradigm | **Confidence:** high | **Last verified:** 2026-06-01

---
## CANONICAL DEFINITION
Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions, emphasising pure functions that produce no side effects, immutable data that cannot be modified after creation, and function composition as the primary mechanism for building programs, rooted in Alonzo Church's lambda calculus (1936).

---
## CONCEPT RELATIONSHIP MAP
**Requires first:** Functions · Type Systems
**Enables:** Closures · Immutability · Side Effects (explicit management) · Haskell
**Commonly confused with:** Using map/filter (these are functional-style tools, not the paradigm)

---
## CURIOUS LEVEL
Pure functions: same input → always same output, no side effects. Immutability: data cannot be changed after creation; produce new values instead. Higher-order functions: functions that take or return functions. map/filter/reduce are the canonical three. Function composition: build complex behaviour from small pure functions. Languages: Haskell (pure), Erlang, Clojure, F#, Elm. Multi-paradigm with FP: Python, JavaScript, Rust, Kotlin, Scala.

## EXPLORING LEVEL
Referential transparency: any expression can be replaced by its value — enables equational reasoning, memoisation, parallelisation. Closures: functions that capture variables from enclosing scope. Currying (Haskell Curry): f(x,y) → f(x)(y) — enables partial application. Persistent data structures share unchanged subtrees; Clojure's vectors use 32-branch trees for O(log₃₂ n) updates. Java 8+ streams, Kotlin collections, JavaScript array methods: map/filter/reduce. React: UI components as pure functions of state.

## COMMONLY CONFUSED
- FP ≠ using map/filter. The paradigm is about purity and referential transparency.
- FP does not mean no side effects — it makes effects explicit (Haskell: IO monad).
- `const arr = [1,2,3]; arr.push(4)` is NOT immutable — `const` prevents reassignment, not mutation.

## DEEP DIVE LEVEL
Lambda calculus (Church, 1936): variables, abstraction (λx.M), application (M N). β-reduction: (λx.M)N → M[x:=N]. Turing-complete — functions alone suffice for any computation. Monad: type constructor M with return :: a → M a and bind :: M a → (a → M b) → M b satisfying left identity, right identity, associativity. Haskell IO monad: IO a is a pure description of an I/O action; the runtime executes it. Curry-Howard correspondence: types = propositions, programs = proofs, type checking = proof verification.

## SOURCES
1. Church, A. (1936). An unsolvable problem of elementary number theory. American Journal of Mathematics 58(2).
2. Hughes, J. (1989). Why functional programming matters. The Computer Journal 32(2).
3. Wadler, P. (1992). The essence of functional programming. POPL '92. ACM.
4. Marlow, S. (ed.) (2010). Haskell 2010 Language Report. haskell.org.
5. Bird, R. & Wadler, P. (1988). Introduction to Functional Programming. Prentice Hall.

*The Codex Coding — thecodex.expert/coding/ — Free forever — Mumbai, India*