Functional Programming

This deck walks you through the core ideas behind functional programming, starting with the basics like pure functions, side effects, and immutability, and then building up to more intermediate concepts such as closures, currying, partial application, and higher-order functions. You'll also get hands-on practice with the classic trio of array operations—map, filter, and reduce—which are the workhorses of any functional codebase.

It's a great fit if you're a developer who mostly writes object-oriented or imperative code and wants to understand the functional style, whether you're preparing for interviews, picking up a language like Haskell or Elixir, or just trying to write cleaner JavaScript, Python, or Kotlin. Beginners will appreciate that the cards start from first principles, while more experienced programmers can use the deck to fill in gaps or refresh terminology they've heard but never fully nailed down.

Because these concepts build on each other—closures make sense once you know about lexical scoping, and currying clicks after you've seen partial application—try studying the cards in order on your first pass so the foundation is solid. After that, lean on spaced repetition rather than cramming, and try writing a tiny example for each idea (even a one-liner in your favorite language) to make the abstract definitions feel concrete.

Functional programming is a declarative paradigm that treats computation as the evaluation of mathematical functions. Rather than describing step-by-step procedures that mutate state, functional programs describe what the result should be, letting the runtime determine how to compute it. Languages such as Haskell, Erlang, Clojure, and F# are primarily functional, while many mainstream languages now incorporate functional features. The paradigm emphasizes immutability, pure functions, and the avoidance of side effects, standing in contrast to imperative programming, which uses loops, mutations, and explicit control flow to describe how a task is performed.

A pure function always returns the same output for the same input and has no observable side effects. The simple addition function \( a + b \) is pure: given the same arguments, it always yields the same result, and it does not modify any external state. By contrast, a function like \( \text{Math.random}() \) is impure because its output varies and because the act of calling it interacts with a global random state. Purity gives rise to referential transparency, the property that any expression can be replaced by its value without changing the program's behavior, which enables equational reasoning, aggressive compiler optimizations, and dramatically simpler testing — there is no need to set up or tear down external state, no mocking of dependencies, and tests are independent and can run in parallel.

Side effects are any observable changes a function makes beyond returning a value: modifying global or external variables, writing to files or databases, printing to the console, making network requests, or mutating input arguments. Functional programming aims to isolate side effects from core logic rather than eliminate them entirely, since real programs must eventually interact with the outside world. Immutability complements this goal by ensuring that once a data structure is created, it cannot be changed; instead of mutating data, programs create new copies with the desired modifications. This combination of purity, isolation of effects, and immutability is the cornerstone of functional design and brings benefits such as easier reasoning about code, thread safety without locks, and simpler debugging.

Functional programming treats functions as first-class values: they can be assigned to variables, passed as arguments, returned from other functions, and stored in data structures. A function that takes one or more functions as arguments, or that returns a function as its result, is called a higher-order function. The familiar array methods \( \text{map} \), \( \text{filter} \), and \( \text{reduce} \) are all higher-order functions, and they form the backbone of functional data processing. Closures and lexical scoping are intimately connected with this style: a closure is a function that captures and remembers variables from its enclosing lexical scope, even after that scope has finished executing, and lexical scoping means a variable's scope is determined by its position in the source code rather than by the runtime call stack.

Currying and partial application are two related techniques for working with multi-argument functions. Currying transforms a function of \( n \) arguments into a sequence of \( n \) single-argument functions, so that \( \text{add}(a, b) \) becomes \( a \mapsto b \mapsto a + b \); in Haskell every function is automatically curried. Partial application, by contrast, fixes some arguments of a function to produce a new function with fewer parameters, and it can fix multiple arguments at once. Currying enables partial application, but the two are distinct: currying is a structural transformation of a function's shape, while partial application is about pre-filling specific values.

Closely related are function composition, which combines functions so the output of one becomes the input of the next, and piping, which provides a more readable left-to-right data flow. Elixir and F# use the pipe operator \( \rvert \), while Haskell composes functions right-to-left with the dot operator. Together with point-free style — defining functions without explicitly naming their arguments, so that \( s \mapsto s.\text{toUpperCase}() \) becomes \( \text{map}(\text{prop}('\text{name}')) \) — these techniques let programmers build expressive transformation pipelines out of small, reusable pieces. Eta reduction is the corresponding simplification that removes redundant parameter passing when a function merely forwards its argument to another function, while eta expansion is its inverse, wrapping a function to make its type explicit.

Functional programming favors immutable data structures that, when modified, produce new versions while preserving the old. Persistent data structures achieve this efficiently through structural sharing: instead of copying the whole structure, they reuse unchanged subtrees from the original. Libraries like Immutable.js and languages like Clojure provide persistent vectors, maps, and sets that achieve roughly \( O(\log n) \) updates this way. The underlying implementation often uses a trie with a branching factor of 32, so updating element \( i \) requires copying only \( O(\log_{32} n) \) nodes along the path to \( i \) — effectively constant time for vectors up to billions of elements.

Several classical structures remain useful in functional settings. The cons list, built from a constructor that prepends an element to another list, gives \( O(1) \) prepend but \( O(n) \) random access and forms the basis of Lisp, Scheme, and Clojure. A difference list represents a list as a function from a list to a list, turning append into function composition and achieving \( O(1) \) append, which is useful in logic programming and in Haskell's Show instance. Rose trees, with a value and a list of child subtrees, model abstract syntax trees and other hierarchical data, while finger trees are general-purpose persistent sequences that support amortized \( O(1) \) cons and snoc, \( O(\log n) \) append, and \( O(\log n) \) search, parameterizable as sequences, priority queues, or ordered sets.

Algebraic data types, or ADTs, are composite types built by combining other types. Sum types (also called tagged unions or discriminated unions) represent values that are one of several variants, such as \( \text{Either}\langle A, B \rangle \), and they correspond to logical OR. Product types combine multiple values into one — tuples, structs, and records — and correspond to logical AND. Pattern matching is a destructuring mechanism that inspects a value against these patterns, going beyond simple switch/case to allow nested matching, guards, and exhaustive handling of all cases. Records in Haskell provide named field accessors and convenient update syntax, while the newtype declaration introduces a zero-cost wrapper that is distinct at the type level but identical at runtime, letting programmers add semantic meaning to existing types without performance overhead. Generalized algebraic data types, or GADTs, extend ADTs with type-equality constraints in their constructors, enabling type-indexed data structures and embedded domain-specific languages. Phantom types add type-level information that does not appear in the constructor, giving a way to encode distinctions like user tokens versus admin tokens at zero runtime cost.

Since loops rely on mutable state, functional programming replaces them with recursion, in which a function calls itself on smaller subproblems until it reaches a base case. Deep recursion, however, can overflow the call stack. Tail call optimization solves this by reusing the current stack frame when a function call is in tail position, the last operation before returning. Languages like Haskell, Scheme, and Erlang perform TCO automatically, and trampolining achieves the same effect in strict languages by returning thunks that a loop repeatedly invokes until a final value is reached.

Folds are the workhorses of functional iteration. The reduce, or fold, operation combines all elements of a collection into a single value using an accumulator function and an initial value. There are two main variants: a left fold processes elements from left to right and is naturally tail-recursive, while a right fold processes from right to left, builds a chain of thunks, and can be lazy on infinite lists. The strict left fold \( \text{foldl}' \) forces the accumulator at each step to prevent the buildup of unevaluated thunks that \( \text{foldl} \) would otherwise accumulate, which is essential for constant-space numerical sums. The most general fold is \( \text{foldMap} \): it maps each element to a monoid value and combines them, so that \( \text{sum} \) is \( \text{foldMap Sum} \) and \( \text{length} \) is \( \text{foldMap}(\_ \mapsto \text{Sum } 1) \). Unfold, the dual of fold, builds a data structure from a seed by repeatedly producing a new element and the next seed, enabling the generation of sequences and streams without explicit mutation. A stream is a lazy, possibly infinite sequence that supports bounded-memory processing of unbounded data through take, map, and filter; this contrasts with iterators, which pull values on demand and signal termination explicitly, while streams push values through a composable pipeline.

Evaluation strategies determine when expressions are actually computed. Eager, or strict, evaluation, used by languages like JavaScript, Python, and Java, evaluates expressions as soon as they are bound to a variable, which is predictable but may compute values that are never used. Lazy, or non-strict, evaluation, used by Haskell by default, delays computation until the value is actually needed, enabling infinite data structures, avoiding unnecessary work, and improving performance when only part of a result is required. Thunks are zero-argument functions that wrap an unevaluated expression; they are the mechanism behind lazy evaluation in strict languages and are used in Redux middleware. Thunk leaks occur when unevaluated thunks accumulate in memory because the surrounding structure is referenced, requiring profiling tools to diagnose. Memoization caches the results of expensive pure function calls so that repeated calls with the same arguments return instantly, and the monoid laws — associativity of the binary operation and the existence of an identity element — guarantee that folds and aggregations behave predictably and can be parallelized safely.

The functor–applicative–monad hierarchy is a layered abstraction for sequencing computations on wrapped values. A functor is any type that implements a map operation, letting you apply a function to its wrapped value without unwrapping it; arrays, \( \text{Maybe} \), and \( \text{Either} \) are all functors. Functors must satisfy the identity law \( \text{map}(\text{id}) \equiv \text{id} \) and the composition law \( \text{map}(f \circ g) \equiv \text{map}(f) \circ \text{map}(g) \). An applicative functor extends a functor by allowing the application of a wrapped function to a wrapped value through the ap operator, with operations \( \text{pure} \) and \( \text{ap} \); its laws include the homomorphism, interchange, identity, and composition laws. Every monad is an applicative, and every applicative is a functor, so power increases as one moves up the chain. The key distinction is that in an applicative the choice of function cannot depend on previous values, while in a monad it can.

A monad is a design pattern for composing functions that return wrapped values. It consists of a type constructor, a unit operation that wraps a value, and a bind operation, also called flatMap or \( \gg= \), that chains operations while flattening one level. The three monad laws — left identity \( \text{return}\,a \gg= f \equiv f\,a \), right identity \( m \gg= \text{return} \equiv m \), and associativity \( (m \gg= f) \gg= g \equiv m \gg= (\lambda x.\, f\,x \gg= g) \) — ensure that monadic computations behave consistently across refactorings. Specific monads address recurring patterns: the Maybe monad, called Optional in Java and Swift, handles possibly absent values with a Just/Some branch and a Nothing/None branch that short-circuits subsequent operations so that \( \text{Maybe.map}(f, \text{Nothing}) \) returns \( \text{Nothing} \) without ever applying \( f \). The Either monad represents success with Right and failure with Left, providing a functional alternative to exceptions where errors propagate through the chain. The IO monad encapsulates side effects in Haskell, keeping the type system honest so that a function's type alone reveals whether it performs effects, and the State, Reader, Writer, List, and Continuation monads respectively thread pure state, read from a shared environment, accumulate logs, represent non-deterministic computation, and encode the rest of a computation as a callback.

Monad transformers stack monadic effects. \( \text{MaybeT}\,m\,a \) adds Maybe short-circuiting to an underlying monad \( m \); \( \text{EitherT}\,e\,m\,a \) lifts error handling into effectful code; and \( \text{ReaderT}\,r\,m\,a \) combines a read-only environment with any monad, forming the basis of mtl-style effects such as \( \text{AppM} = \text{ReaderT Config IO} \). Free monads separate the description of a computation from its interpretation: \( \text{Free}\,f\,a = \text{Pure}\,a \mid \text{Free}(f(\text{Free}\,f\,a)) \) lifts any functor into a monad, allowing the same program to be given different interpreters for testing and production. The Coyoneda lemma ensures that any functor can be made a Functor automatically, which simplifies Free monad construction, while join flattens one level of monadic structure and is the primitive from which bind is derived. Bifunctors are functorial in two arguments, contravariant functors apply functions in the opposite direction, and contravariant applicatives use contramap in place of \( \text{ap} \) for structures like predicates and comparisons. The ApplicativeDo extension in Haskell lets do-notation desugar through \( \text{ap} \) instead of bind when bound names are not reused, enabling concurrent rather than sequential execution of independent effects.

Haskell's type classes provide a mechanism for ad-hoc polymorphism, defining behavior that works across many types. Common examples include \( \text{Eq} \) for equality comparison, \( \text{Ord} \) for total ordering, \( \text{Show} \) for conversion to a human-readable string, and \( \text{Semigroup} \) and \( \text{Monoid} \) for associative operations with and without identity. Type classes are not classes in the object-oriented sense; they are interfaces with no inheritance, and instances provide implementations per type. Functions under composition form a monoid with the identity function as the empty element, and endomorphisms — functions from a type to itself — are central to Endomorphism-based aggregation strategies that compose many small transformations into one efficient pass.

Type inference is the compiler's ability to deduce the types of expressions without explicit annotations. The Hindley-Milner algorithm can find the most general type of an expression using unification, and it underpins Haskell, ML, and OCaml, though it cannot infer higher-rank types. Kinds are the types of types: \( \text{Int} \) has kind \( * \), \( \text{Maybe} \) has kind \( * \to * \), and a higher-kinded type like \( \text{MaybeT} \) has kind \( (* \to *) \to * \to * \). The kind system prevents nonsense like \( \text{Maybe Int Int} \). Parametric polymorphism means a function works uniformly across all types without inspecting them, as in \( \text{id} : a \to a \), while ad-hoc polymorphism allows different implementations per type, as with Haskell's type classes. Type variables, written in lowercase like \( a \) or \( b \), are placeholders that enable this parametric polymorphism. In Haskell, the arrow \( \to \) in a type signature is right-associative, so \( a \to b \to c \) parses as \( a \to (b \to c) \), mirroring currying at the type level.

Beyond ordinary type classes, Haskell supports advanced type-level programming. Type families are type-level functions mapping a container type to its element type, and DataKinds promotes ordinary data constructors to the kind level, enabling type-level naturals and length-indexed vectors. Singleton types bridge the value level and the type level, with exactly one inhabitant per type-level tag, allowing runtime reflection of compile-time information. These features culminate in dependently typed programming, where types can depend on values: a vector of length \( n \) carries \( n \) as both a runtime parameter and a type-level index, enabling proofs-as-programs and refined types. Idris is a dependently typed functional language with Haskell-like syntax, totality checking, and compilation to native code, JavaScript, and C. The \( \text{MonadFail} \) class restricts pattern-match failures in do-notation to monads like Maybe and lists, keeping IO pure.

Lambda calculus, invented by Alonzo Church in the 1930s, is the theoretical foundation of functional programming. It has only three constructs: variables, abstraction \( \lambda x.\text{body} \), and application \( f\,x \), yet it is Turing complete. Alpha equivalence states that bound variable names do not matter, so \( \lambda x.\,x \) and \( \lambda y.\,y \) are the same function. Beta reduction is the evaluation rule for function application, replacing \( (\lambda x.\,\text{body})\,\text{arg} \) with the body in which \( x \) is replaced by arg. Eta reduction removes redundant parameter passing when a function merely forwards its argument, while eta expansion is the inverse, wrapping a function to make its type check or delay its evaluation. The Church-Rosser theorem guarantees confluence: any two reduction sequences can be extended to meet at a common result, so a term's normal form is unique when it exists. A term is in weak head normal form when its outermost structure is not a redex, even if subexpressions remain unevaluated.

Lambda calculus can be reformulated without variables using combinators. The K combinator returns its first argument and ignores the second; the S combinator implements generalized application as \( S\,x\,y\,z = x\,z\,(y\,z) \); together with the identity combinator I, they form SKI calculus, a Turing-complete basis. A combinator is a function whose only free variables are its arguments, making combinator-heavy code highly portable and easy to test. Fixed-point combinators enable anonymous recursion: the Y combinator \( Y\,f = f\,(Y\,f) \) computes the least fixed point of \( f \) and works in lazy languages, while the Z combinator adapts the same idea for strict languages by wrapping recursive calls in thunks. Church encoding represents data as higher-order functions — Church Booleans and Church numerals are constructed purely from lambdas — while the Scott encoding represents data as functions that case-analyze themselves, supporting strict pattern matching in strict languages. Recursion schemes generalize these patterns: a catamorphism tears down a structure according to its type's shape, an anamorphism builds a structure from a seed by unfolding, and a hylomorphism fuses an unfold and a fold without materializing the intermediate structure, enabling streaming divide-and-conquer algorithms.

Category theory provides further structure. A natural transformation is a mapping between functors that commutes with fmap; the Yoneda lemma says \( \forall b.\, (a \to b) \to f\,b \) is isomorphic to \( f\,a \), meaning a functor is determined entirely by its action on morphisms, and the dual Coyoneda lemma gives a free construction that makes any functor a Functor automatically. A comonad is the categorical dual of a monad, providing extract and duplicate operations, and the zipper data structure — pairing a focused element with its surrounding context for O(1) navigation in an otherwise immutable structure — is a comonad satisfying left and right identity laws. The cofree comonad of a functor represents a value with a branching tree of future values, dual to the free monad, and underpins functional reactive programming. Profunctors are contravariant in one argument and covariant in the other, and they form the foundation of optics: lenses for read/write focus on substructures, prisms for focusing on a single constructor of a sum type, traversals for zero-or-more elements, isos for bijective type conversions, and getters and setters as their read- and write-only specializations. The Bifunctor class captures functors of two arguments, the Contravariant class applies functions in the opposite direction, and the natural number object with morphisms \( 1 \to N \) and \( N \to N \) embodies the Peano axioms category-theoretically.

Different functional languages emphasize different aspects of the paradigm. Haskell is pure and lazy by default, with monadic IO and a powerful type system. OCaml is strict by default, supports mutability directly through ref cells and mutable fields, and uses modules rather than type classes as its primary abstraction; both share algebraic data types and pattern matching. F# offers computation expressions, a syntax for defining custom workflows using let! and do! that generalizes monads, async, sequences, and queries, and its Async monad handles asynchronous, parallel, and background work. F#'s unit type, written (), is a type with exactly one value, used as the return type of computations that produce nothing of interest, in contrast to void in C-like languages.

Elixir and F# share the left-to-right pipe operator \( \rvert \) for data flow, where \( x \rvert f(y) \) is \( f(x, y) \), while Haskell's dot operator composes functions right-to-left: pipes are data-focused, whereas composition builds new functions. Clojure builds its entire standard library on persistent data structures — lists, vectors, maps, and sets — that are immutable and use structural sharing for cheap updates, with trie-based vectors giving roughly \( O(\log_{32} n) \) copy costs. Clojure also popularized transducers, composable algorithmic transformations decoupled from the input and output context, so that a single transducer like \( (\text{map inc}) \) can be reused across vectors, lazy sequences, channels, and core.async pipelines. The transduce function composes multiple transformations and applies them during a single fold, avoiding the intermediate collections that ordinary chaining with map and filter would create and dramatically improving performance.

Immutability has a profound effect on concurrency. Because immutable data cannot change, it is automatically thread-safe: no lock is needed to share it, and a whole class of bugs — data races, deadlocks, and stale reads — simply cannot occur. This is the central reason Erlang, Clojure, and Haskell scale to massive concurrency. Erlang's process model takes this further: lightweight isolated processes, each with its own heap and mailbox, communicate solely through message passing, with crash isolation built in. The let it crash philosophy holds that defensive error handling often hides bugs; instead, processes are allowed to fail and supervisors restart them, making failure observable, fast, and self-healing — aligning with FP's preference for isolating side effects. For cases that genuinely require shared mutable state, software transactional memory provides atomic, isolated access without explicit locks: transactions read and write to TVars or refs, and on conflict the runtime retries automatically, with the composable property that any function can run inside a transaction.