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.