Functional Programming
Overview
Functional Programming (FP), also called the functional paradigm, treats computation as the evaluation of mathematical functions and favors immutable data over state changes.
Functional programming is widely used alongside object-oriented programming, though its theoretical foundation goes back further: lambda calculus grew out of mathematical logic in the 1930s, before object-oriented programming took shape. That history is why it is sometimes called "the old new paradigm."
Object-Oriented:
Object-oriented programming bundles data and the behaviors that manipulate that data together into discrete units called objects.
Functional:
Functional programming constructs programs through the composition of pure functions that transform data.
Core Definitions
Functional programming emphasizes the following properties.
1.Functions are first-class citizens.
2.Functions are close to mathematical functions (same input → same output).
3.Avoid mutation and side effects.
4.Prefer recursion and higher-order functions over loops.
5.Data is immutable – instead of modifying existing data, new data is created.
Languages enforce these properties in different ways and to different degrees, and functional techniques also appear in languages that were not designed specifically for functional programming.
History
The history of functional programming begins not in industry but in mathematical logic. This starting point is what makes the culture and vocabulary of functional programming distinct from that of object-oriented programming.
Lambda Calculus (1930s)
Alonzo Church developed lambda calculus in the 1930s to describe computation through function abstraction and application. Untyped lambda calculus and Turing machines are provably equivalent in the computable functions they express. The Church-Turing thesis links these formal models to the intuitive notion of effective calculability, a different claim from the equivalence theorem.1
Basic operations of lambda calculus:
-Variable: x
-Abstraction: λx. M (a function that takes x and returns M)
-Application: M N (applies function M to argument N)
Lambda application can be written as the following reduction. M is the body and N is the argument; M[x := N] substitutes N for the free occurrences of x in M. Bound variables are renamed when necessary so the substitution does not accidentally capture a variable in the argument.
The Haskell expression (\x -> x + 1) 2 is an executable example of the same application and evaluates to 3.
The Haskell 2010 Report defines the syntax of lambda abstractions and function application.2
These three forms can encode natural numbers, Booleans, data structures, and recursion in untyped lambda calculus. Modern functional languages build on that foundation while also drawing on type theory, algebraic data types, modules, and approaches to effects, so their concepts do not all descend directly from lambda calculus.
Lisp (1958)
Lisp (LISt Processor) began with John McCarthy's design work in 1958. Lisp adopted lambda notation and became an important starting point for functional programming. McCarthy's 1960 paper "Recursive Functions of Symbolic Expressions and Their Computation by Machine" is a foundational reference.3
Lisp introduced core elements of the functional mindset (first-class functions, a recursion-centric approach, and homoiconicity), but it freely permitted mutable variables and side effects. Lisp is the starting point of functional programming, not a purely functional language.
ISWIM and Theoretical Foundations (1960s)
Peter Landin introduced ISWIM (If you See What I Mean) in his 1966 paper "The Next 700 Programming Languages." Although presented as a hypothetical language, the paper also describes an experimental prototype; its influence on later languages came mainly through the design framework rather than widespread production use. The let/where constructs, expression-oriented design, and the offside-rule style of thinking belong to this lineage.45
Backus's Turing Award lecture (1977 award, 1978 publication)
In his Turing Award lecture, published in 1978 following his 1977 award, "Can Programming Be Liberated from the Von Neumann Style?", John Backus criticized imperative programming for being too tightly bound to Von Neumann architecture and proposed function-level programming instead.6 This lecture is frequently cited as the industrial legitimization of the functional programming movement.
Backus designed FORTRAN, an archetypal imperative language, which gives his criticism of that paradigm particular weight.
The ML Family (1973)
ML (Meta Language), created by Robin Milner around 1973 for the LCF (Logic for Computable Functions) theorem prover, is the landmark example of combining static type inference with a functional language.7 The Hindley-Milner type system became widely known through the ML family and went on to serve as the foundation for statically typed functional languages.
ML family descendants:
Standard ML (design work began in 1983; Definition published in 1990, revised in 1997)8
Caml (1985) / OCaml (1996)
F# (2005) - Microsoft, OCaml-based
Influenced: the type systems of Rust, Swift, and Scala
Miranda and Lazy Evaluation (1985)
Miranda, released by David Turner in 1985, was a commercially supported pure functional language combining lazy evaluation, pure functions, and algebraic data types.9 Trademark issues made Miranda difficult to use as a shared research language in academia, and the need for an open standard to unify the various lazy functional languages became one of the driving motivations behind the creation of Haskell.
Haskell (1990)
Haskell began in 1987 as a committee effort to establish a common standard for lazy-evaluation-based functional languages, and published its first standard (Haskell 1.0) in 1990.10 The name comes from Haskell Curry, a researcher in lambda calculus.
Haskell's defining contributions:
Adopted lazy evaluation as the default
Separated I/O through the IO monad; standard monadic I/O arrived in Haskell 1.3 (1996), not Haskell 1.0 (1990)11
Introduced type classes (Wadler & Blott, 1989)
Became the standard reference point for functional thinking in both academia and industry
Personal note: There is a joke that "programming in Haskell means no bugs, but also no finished programs." I like that joke.
Concurrency-first functional programming (Erlang, 1986)
Erlang, created in 1986 by Joe Armstrong and colleagues at Ericsson, is a functional language designed for concurrency and reliability in telecommunications systems. Lightweight processes, asynchronous messages, and the "let it crash" philosophy made it well known in high-availability systems. Its process model is often described as actor-based, though its designers did not set out to implement the actor model. Elixir (2011) is a separate language that runs on the same Erlang VM.12
The resurgence of modern functional programming (2000s onward)
Factors that brought functional programming back into the spotlight in industry:
The arrival of the multicore era, as the concurrency cost of mutable state grew significantly
The emergence of JVM/CLR functional languages such as Scala (first public release in 2004; the specification also dates an early 1.0 release to 2003), Clojure (2007), and F# (2005)1314
Rust (2010 onward), a systems language with strong functional influences
React + Redux (2015 onward), introducing unidirectional data flow and immutability to the JavaScript frontend
TypeScript (2012 onward), with discriminated unions and type-level expressiveness
Many functional techniques are now available in mainstream multi-paradigm languages.
Core Concepts
First-class Function
This means functions are treated as equal to any other value.
-Functions can be assigned to variables.
-Functions can be passed as arguments to other functions.
-Functions can be returned as values from other functions.
-Functions can be stored in data structures.First-class functions make higher-order programming convenient, although a language can accept function arguments while still restricting how functions are stored or returned. Full first-class status is therefore not a logical prerequisite.
Pure Function
A function that satisfies both of the following conditions:
In the mathematical model f : A → B, A is the set of inputs and B the set of results. Using a model of terminating computations on defined inputs, equal inputs lead to equal results as follows.
The equation describes the input-result relationship; purity also requires the absence of observable side effects. A Haskell function arrow by itself does not prove that the function terminates on every input.
1. The same input has the same result independently of external state.
2. Evaluation does not mutate external state or perform observable side effects.Typical side effects include global mutation, console output, file writes, and network communication, while observing and handling exceptions can also be treated as an effect. Haskell's error and nontermination can occur in pure expressions as bottom (⊥), so purity does not guarantee a normal result.
A pure function has referential transparency: replacing an expression with its resulting value leaves the program's meaning unchanged, which provides a basis for functional reasoning and optimization.
Immutability
Once created, a value stays as it is; a change produces a new value instead.
xs, ys :: [Int]
xs = [1, 2, 3]
ys = 0 : xs
main :: IO ()
main = print (xs, ys)
An immutable update allocates memory for new data, but persistent data structures can share the unchanged parts instead of copying the whole structure. How much memory and time this takes depends on the structure and the operation.
Higher-order Function
A function that takes other functions as arguments or returns a function as its result. It is the unit of abstraction in functional programming.
-- List-specialized signatures of Prelude functions:
-- map :: (a -> b) -> [a] -> [b]
-- filter :: (a -> Bool) -> [a] -> [a]
-- foldr :: (a -> b -> b) -> b -> [a] -> b
main :: IO ()
main = do
let xs = [1, 2, 3, 4] :: [Int]
print (map (* 2) xs)
print (filter even xs)
print (foldr (+) 0 xs)
In the example, map takes a function and applies it to each list element, while foldr takes a function combining an element with an accumulated result. Expanding these operations on a finite list gives the following equations.
For foldr (+) 0 [1,2,3], read the expression as 1 + (2 + (3 + 0)). It describes the nesting structure; lazy evaluation determines which intermediate values actually need to be evaluated.
Just as polymorphism and inheritance serve as abstraction tools in object-oriented programming, higher-order functions fill that role in functional programming.
Function Composition
An operation that chains two functions together into a single function.
Two functions compose when the result of f can be passed to g. The notation g ∘ f applies f first and then g; Haskell writes that order as g . f.
Passing 3 to negate . double sends the 6 produced by double 3 into negate, giving -6.
double :: Int -> Int
double x = x * 2
doubleNegate :: Int -> Int
doubleNegate = negate . double
main :: IO ()
main = print (doubleNegate 3)
Function composition is the unit of modularity in functional programming. If object-oriented programming assembles objects, functional programming composes functions.
Currying and Partial Application
Currying converts a function such as (a, b) -> c into a chain a -> b -> c, with each function accepting one argument. The name comes from Haskell Curry, whereas partial application means supplying some arguments now to obtain a function for those that remain.
Currying relates a function accepting a pair of arguments to a function that accepts the first argument and returns a function waiting for the second. For mathematical functions on defined values, the relationship is written as follows.
In Haskell, add 1 is a function with its first argument fixed to 1. Currying describes the argument structure; supplying only some arguments is partial application.
add :: Int -> Int -> Int
add x y = x + y
addOne :: Int -> Int
addOne = add 1
addPair :: (Int, Int) -> Int
addPair = uncurry add
main :: IO ()
main = print (addOne 4, addPair (2, 3), curry addPair 2 3)
Haskell and OCaml naturally support curried definitions such as f x y, but they also allow a single tuple argument, as in f (x, y). It is therefore misleading to say that every function is automatically curried. JavaScript and Python can express the same structure by returning functions.
Lazy Evaluation
An evaluation strategy that defers computation until the value is actually needed. Haskell is the canonical example.
naturals :: [Integer]
naturals = [1..]
main :: IO ()
main = print (take 5 naturals)
Lazy evaluation helps with composition and abstraction, but deferred work can also lead to space leaks and make debugging harder. Those pitfalls appear again in the anti-patterns section.
Recursion and Tail Call Optimization
Functional code expresses iteration through higher-order functions such as map, fold, and traverse as well as recursion. With explicit recursion, space usage can depend on whether work remains after the recursive call and whether the call is in tail position; tail call optimization (TCO) lets a tail call reuse its caller's stack frame.
import Data.List (foldl')
sumNonTail :: [Int] -> Int
sumNonTail [] = 0
sumNonTail (x:xs) = x + sumNonTail xs
-- Tail position alone does not force acc + x.
sumTailLazy :: Int -> [Int] -> Int
sumTailLazy acc [] = acc
sumTailLazy acc (x:xs) = sumTailLazy (acc + x) xs
sumStrict :: [Int] -> Int
sumStrict = foldl' (+) 0
main :: IO ()
main = do
let xs = [1..100] :: [Int]
print (sumNonTail xs, sumTailLazy 0 xs, sumStrict xs)
Scheme and Erlang treat the space behavior of tail calls as an important language/runtime guarantee, and OCaml supports tail recursion too. In Haskell, a tail call does not make its accumulator strict. Deferred acc + x computations in sumTailLazy can grow on the heap; evaluating that chain later can also overflow the stack. To reduce this kind of space leak, use strictness controls such as seq, bang patterns, and foldl'.15
Functional Concepts Combined with the Type System
Algebraic Data Types (ADT)
Data is expressed as a combination of product types (AND) and sum types (OR).
data Point = Point Double Double deriving Show
data Shape = Circle Point Double
| Rectangle Point Point
| Triangle Point Point Point
deriving Show
main :: IO ()
main = mapM_ print
[ Circle (Point 0 0) 2
, Rectangle (Point 0 0) (Point 3 4)
, Triangle (Point 0 0) (Point 4 0) (Point 0 3)
]
Point is a product type because it needs both an x coordinate and a y coordinate, whereas Shape is a sum type because a value selects one of Circle, Rectangle, or Triangle. The selected constructor groups the coordinates or radius that its shape needs.
The Result type, Option type, trees, and lists are all expressed as algebraic data types.
Pattern Matching
A construct that branches by destructuring algebraic data types.
data Point = Point Double Double
data Shape = Circle Point Double
| Rectangle Point Point
| Triangle Point Point Point
area :: Shape -> Double
area (Circle _ r) = pi * r * r
area (Rectangle (Point x1 y1) (Point x2 y2)) =
abs (x2 - x1) * abs (y2 - y1)
area (Triangle (Point x1 y1) (Point x2 y2) (Point x3 y3)) =
abs ((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)) / 2
main :: IO ()
main = do
print (area (Circle (Point 0 0) 1) == pi)
print (area (Rectangle (Point 0 0) (Point 3 4)))
print (area (Triangle (Point 0 0) (Point 4 0) (Point 0 3)))
An exhaustiveness check can find missing patterns at compile time in a statically typed language, while the choice of branch generally happens at runtime, once the actual constructor is known. In GHC, -Werror=incomplete-patterns turns incomplete matches into errors.16
Type Class
An ad-hoc polymorphism mechanism introduced by Haskell. Philip Wadler and Stephen Blott proposed it in their 1989 paper How to Make Ad-Hoc Polymorphism Less Ad Hoc.17
-- Eq already exists in Prelude. Define an instance for our own type.
newtype UserId = UserId Int
instance Eq UserId where
UserId x == UserId y = x == y
main :: IO ()
main = print (UserId 7 == UserId 7, UserId 7 == UserId 8)
Rust's traits, Scala type class patterns built with implicit/given, and Swift's protocols are used to abstract sets of operations over types. Rust traits and Scala type class patterns are often compared with Haskell type classes. These mechanisms differ in their module systems, object systems, and compiler constraints.
Parametric Polymorphism
Parametric polymorphism uses a type variable such as a to apply one implementation across types without fixing their concrete representation. An identity function has no need to inspect the structure of its input type. Java generics offer a useful comparison, while C++ templates differ because instantiation can select type-specific operations.
identity :: a -> a
identity x = x
listLength :: [a] -> Int
listLength [] = 0
listLength (_:xs) = 1 + listLength xs
main :: IO ()
main = do
print (identity True, identity "hello")
print (listLength [False, True], listLength "hello")
A type variable a can be instantiated to any type.
Handling Side Effects
A state transition can be written as a pure function of type s -> (a, s), and failure can be represented by Maybe or Either. Haskell's IO a is also an action value that composes within pure code; the runtime performs its interaction with the outside world.
Monad
A monad provides operations and laws for placing values in a computational context and sequencing computations whose next step can depend on an earlier result. Handling effects is one use of this structure, but not its only purpose. Eugenio Moggi developed the approach in a 1988 technical report and a 1989 LICS paper, then treated it in computational semantics in the 1991 paper Notions of Computation and Monads; Philip Wadler and others brought it into functional programming and Haskell.181920
main :: IO ()
main = do
name <- getLine
putStrLn ("Hello, " ++ name)
That getLine returns IO String means it is "an IO action that produces a string," not "a string itself." This distinction in types is what separates pure functions from side effects.
In this code, name <- getLine binds the string produced by the input action to name for the following action. The do notation sequences these computations; this example can also be written with >>=:21
main :: IO ()
main = getLine >>= \name -> putStrLn ("Hello, " ++ name)
Write the sequencing operation as bind in the equations, corresponding to Haskell’s (>>=), and use pure to put a value in the computation context. A lawful monad preserves meaning when pure is added on either side and when the grouping of these sequencing operations changes.
These are left identity, right identity, and associativity. The compiler checks types; the instance author must also implement the laws. The equations compare computational meaning rather than execution time or allocation.
The Haskell 2010 Report describes Monad operations and the three laws.22
Both versions read one line and print the same greeting, using name as the string in the following output action. Having obtained that string does not change the type of the complete computation: it is still IO ().
A common misconception to correct:
Monad = a form borrowed from category theory, but using it does not require knowledge of category theory
A monad is simply a programming tool, like if/then/else, not a mystical concept.
Personal note: The most dangerous moment when encountering monads for the first time is when you say, "Ah, I finally get it." That's usually when you stop understanding them again.
Effect System
An effect system tracks the effects an expression may perform alongside its value type and can coexist with monads. Algebraic effects and handlers separate the declaration of effect operations from their interpretation, an approach explored in languages such as Eff, Koka, and Unison.23
Monad: an interface for sequencing computations; IO can include many kinds of external action.
Monad transformers: combine contexts such as ReaderT, StateT, and ExceptT; order can change semantics.
Effect system: tracks which effects may occur at the type level.
Algebraic effects and handlers: separate effect operations from their interpretation.
Functional Programming vs Object-Oriented Programming
The two paradigms decompose the same problem along different axes.
Feature | Object-Oriented | Functional |
|---|---|---|
State | Encapsulated inside objects | Immutable, explicit outside functions |
Polymorphism | Subtyping + parametric polymorphism | Parametric polymorphism + type classes |
Reuse | Inheritance, composition, delegation | Function composition, higher-order functions |
Time / Flow | State changes of objects over time | Transformation flow of values |
Error handling | Exceptions + try/catch | Result / Either, monads |
Modularity | Classes, packages | Modules, functions, types |
- Feature
State
- Object-Oriented
Encapsulated inside objects
- Functional
Immutable, explicit outside functions
- Feature
Polymorphism
- Object-Oriented
Subtyping + parametric polymorphism
- Functional
Parametric polymorphism + type classes
- Feature
Reuse
- Object-Oriented
Inheritance, composition, delegation
- Functional
Function composition, higher-order functions
- Feature
Time / Flow
- Object-Oriented
State changes of objects over time
- Functional
Transformation flow of values
- Feature
Error handling
- Object-Oriented
Exceptions + try/catch
- Functional
Result / Either, monads
- Feature
Modularity
- Object-Oriented
Classes, packages
- Functional
Modules, functions, types
Same problem, different decomposition:
"Track the order status"
Object-Oriented: An Order object has a status field, and its state is changed via methods.
Functional: Order is immutable. A state transition is a function that creates a new Order (Order -> Order).
The two approaches are compatible, and most modern languages support both paradigms together (Scala, Rust, C#, TypeScript).
The Purity Spectrum
Not all functional languages enforce the same level of purity.
[Stronger enforcement of external I/O boundaries]
Haskell, Idris, Agda, Elm
- Ordinary I/O goes through explicit boundaries such as IO, Cmd, or Sub.
[Weaker enforcement of external I/O boundaries]
Ordinary functions may perform external I/O.
- ML family: Standard ML, OCaml, F#
- Lisp family: Clojure, Common Lisp, Scheme, Racket
- Multi-paradigm: Scala, Rust, Swift
- Imperative-based languages: C#, JavaScript/TypeScript, Python, Java
This compares how strongly ordinary code and standard APIs enforce separation between pure computation and external I/O. The families within each group are not ranked.
Evaluation strategy, termination checking, static or dynamic typing, and immutable data structures are separate properties. Haskell is lazy by default; the ML family uses strict evaluation and permits mutable references and exceptions. The Lisp family is predominantly dynamically typed, with differing mutability policies; Clojure defaults to immutable data structures. Multi-paradigm languages differ in their support for function values, higher-order functions, and effect-control tools, combining functional techniques with object-oriented and imperative code.
Representative Techniques
map / filter / fold
The three fundamental operations for list transformation.
main :: IO ()
main = do
let xs = [1, 2, 3, 4] :: [Int]
print (map (* 2) xs)
print (filter (> 2) xs)
print (foldr (+) 0 xs)
Operations that would require a for loop, an accumulator, and conditionals in imperative style can be compressed into a single-line expression.
Function Composition and Pipelines
This example keeps strings that parse as numbers, removes negative values, and doubles what remains, with mapMaybe readMaybe explicitly discarding strings that fail to parse.
import Data.Maybe (mapMaybe)
import Text.Read (readMaybe)
-- Invalid strings are intentionally omitted; negative numbers are filtered out.
processData :: [String] -> [Int]
processData = map (* 2) . filter (>= 0) . mapMaybe readMaybe
main :: IO ()
main = print (processData ["3", "bad", "-1", "0"])
Read the composition operator (.) from right to left: mapMaybe readMaybe, then filter (>= 0), then map (* 2). Follow the changing data from top to bottom below.
// F#: left to right (|> pipe operator)
let processData rawData =
rawData
|> List.map parse
|> List.filter isValid
|> List.map normalize
Point-Free Style
Point-free style defines a function by combining existing functions rather than naming its input arguments. Here sum . map square omits xs, connecting map square on the input list to sum on the result.
square :: Int -> Int
square x = x * x
sumOfSquaresExplicit :: [Int] -> Int
sumOfSquaresExplicit xs = sum (map square xs)
sumOfSquaresPointFree :: [Int] -> Int
sumOfSquaresPointFree = sum . map square
main :: IO ()
main = print (sumOfSquaresExplicit [1, 2, 3], sumOfSquaresPointFree [1, 2, 3])
It should be used only where it genuinely improves readability; taken too far, it becomes an anti-pattern.
Persistent Data Structures
A persistent data structure leaves the existing value unchanged during an update, so retaining a reference to it lets you use the old and new values together. Persistence does not mean that every change is automatically recorded as history. Structural sharing and path copying are common ways to implement it efficiently, with costs that depend on the operation: list prepend (:) is O(1), list append (++) is linear in the left list, and insertion into the balanced-tree Data.Map is O(log n).24
Representative examples:
- Hash Array Mapped Trie (HAMT)
- Finger Tree
- Persistent Red-Black Tree
- Clojure's PersistentVector / PersistentHashMap
- Haskell's Data.Map (balanced binary tree)Chris Okasaki's 1998 book Purely Functional Data Structures is the standard reference in this field.25
How Immutability Is Actually Implemented
Many functional implementations allocate new nodes on the heap while sharing existing nodes, leaving the old value unchanged from the program's point of view.
Imperative update:
Overwrite the same location in an array/object.
Functional (persistent) update:
Only create new nodes along the changed path, and share the rest of the substructure with the existing nodes.
Structural Sharing in Lists
A Haskell list's cons cell holds an element and a reference to the rest of the list; in the finite list below, these cells form a chain that ends in the empty list [].
xs, ys :: [Int]
xs = [1, 2, 3]
ys = 0 : xs
main :: IO ()
main = print (xs, ys, tail ys == xs)
From a memory perspective, it looks roughly like this.
Constructing ys creates one cons cell containing 0 and a reference to the next node, rather than copying all of [1, 2, 3]. That is the cell labeled [0] in the diagram, and its tail shares the existing list that xs points to, so prepending with (:) needs only this one new node. Appending with (++) instead rebuilds the nodes of the left list. The example prints True because the lists have equal values, not because it compared their memory addresses.
Structural Sharing in Trees and Maps
Balanced-tree-based maps and sets work similarly. Changing a single key creates only the nodes along the path from the root to that key; all untouched subtrees are shared.
Original tree:
A
/ \
B C
/ \
D E
New tree with only E changed:
A'
/ \
B' C <- shared
/ \
D E' <- D also sharedA is the original root in the diagram, and A' is the root after E changes. Retaining the reference to A keeps both trees available: A', B', and E' are new, while C and D belong to both trees.
Stack vs. Heap Perspective
The following diagram describes common implementation choices, not a language guarantee. Inlining or tail calls can eliminate frames, and local values may occupy registers, the stack, or the heap. List and tree nodes, closures, and thunks commonly use the heap, but their actual placement depends on the compiler and its optimizations.
Stack:
- Function call frames
- Short-lived local bindings
- Temporary state during evaluation
Heap:
- Nodes of data structures such as lists, trees, and records
- Environments captured by closures
- Thunks for lazy evaluation (in Haskell)
- Nodes of shared persistent data structures
In these implementations, structural sharing and compiler optimizations reduce the cost of heap allocation and garbage collection.
Personal note: Immutability is not a free lunch. The idea is that you are billed not for "copying everything" but only for "the changed path." Personally, I have nothing but a growing tab.
Haskell's Thunks and Space Leaks
Haskell can defer a computation until its value is needed, keeping the deferred work in a thunk.
sumBad :: Integer
sumBad = foldl (+) 0 [1..1000000]
main :: IO ()
main = print sumBad
The code above intuitively looks like it keeps adding to an accumulator, but under lazy evaluation, unevaluated work can accumulate like this.
((((0 + 1) + 2) + 3) + ...)
A thunk chain can increase heap usage and can also overflow the stack when forced. Diagnosing Haskell space usage therefore requires checking which computations are retained and when they are evaluated, rather than treating stack and heap failures as mutually exclusive.
import Data.List (foldl')
sumGood :: Integer
sumGood = foldl' (+) 0 [1..1000000]
main :: IO ()
main = print sumGood
foldl' evaluates the accumulator at each step to weak head normal form (WHNF), exposing its outermost form. For the Integer sum above, this reduces the buildup of deferred additions. For a tuple accumulator, however, reaching WHNF can reveal the tuple while leaving its elements unevaluated. If those internal values also need evaluating at each step, use strict fields or deepseq to force them as the accumulator requires.26
Immutability in Practical Languages
JavaScript/TypeScript, C#, and Java also implement immutable updates through copying or immutable collections, with JavaScript/TypeScript using shallow object or array copies or libraries such as Immutable.js and Immer. Clojure-style persistent collections are another implementation choice.
// Shallow-copy-based immutable updates
const next = {
...prev,
status: "paid",
};
The update leaves prev itself alone, but it shares any nested object references, so changing one of those objects also changes what the previous object observes.
Immutability implementation approaches:
- Haskell / Clojure: Structural sharing is the default at the language / standard data structure level.
- Scala / F# / OCaml: Immutable and mutable collections are offered as separate choices.
- JS / TS / React: Immutable updates are maintained via convention and libraries.
- Rust: Ownership / borrowing rules control aliasing and mutation.Functional Programming Examples by Language
Haskell
-- This teaching example is not balanced: insertion is O(height).
data Tree a = Leaf | Node a (Tree a) (Tree a) deriving (Eq, Show)
insert :: Ord a => a -> Tree a -> Tree a
insert x Leaf = Node x Leaf Leaf
insert x (Node y left right)
| x < y = Node y (insert x left) right
| x > y = Node y left (insert x right)
| otherwise = Node y left right
toAscList :: Tree a -> [a]
toAscList Leaf = []
toAscList (Node x left right) = toAscList left ++ [x] ++ toAscList right
main :: IO ()
main = do
let oldTree = foldr insert Leaf [2, 1, 3] :: Tree Int
newTree = insert 4 oldTree
print (toAscList oldTree, toAscList newTree, insert 2 oldTree == oldTree)
OCaml
(* Option type and pattern matching *)
let rec find_first pred = function
| [] -> None
| x :: rest when pred x -> Some x
| _ :: rest -> find_first pred rest
F#
// Pipeline-Oriented
let processOrders orders =
orders
|> List.filter (fun o -> o.Status = Active)
|> List.map (fun o -> { o with Total = computeTotal o })
|> List.sortByDescending (fun o -> o.Total)
Clojure
;; Data Transformation Pipeline
(->> orders
(filter active?)
(map compute-total)
(sort-by :total >))
Scala
// for-comprehension (monad abstraction)
val result = for {
user <- findUser(id)
account <- findAccount(user)
balance <- getBalance(account)
} yield balance
JavaScript / TypeScript
// Higher-Order Functions and Composition
const processOrders = (orders: Order[]): Result[] =>
orders
.filter(o => o.status === "active")
.map(o => ({ ...o, total: computeTotal(o) }))
.sort((a, b) => b.total - a.total);
C#
// Assumes Order is a record with a Total property supported by a with expression.
// Domain declarations, orders, and ComputeTotal are defined outside this excerpt.
// LINQ is essentially a functional query language
var result = orders
.Where(o => o.Status == OrderStatus.Active)
.Select(o => o with { Total = ComputeTotal(o) })
.OrderByDescending(o => o.Total)
.ToList();
Rust
// Assumes Order: Clone, comparable Status values, and separately defined orders/compute_total(&Order).
// Iterator chaining + closures
let result: Vec<_> = orders
.iter()
.filter(|o| o.status == Status::Active)
.map(|o| Order { total: compute_total(o), ..o.clone() })
.collect();
Concurrency and Distribution
The primary reason functional programming has experienced a resurgence in the multicore era is that immutability reduces the cost of concurrency.
Concurrency costs of mutable state:
- Lock management
- Race conditions
- Deadlocks
- Memory consistency models
Concurrency benefits of immutable state:
- No locks needed (read-only)
- Side effects are explicit and thus easier to reason about
- Naturally pairs with actor model and message passing
The claim above that no locks are needed applies to reading the same immutable value. Updating a shared reference to point to a new value still needs synchronization. Notable examples:
Erlang / Elixir: well known for the actor model, lightweight processes, and high-availability telecommunications systems
Akka (Scala/Java): an actor-based framework for distributed systems
Hadoop / Spark: the map/reduce interface draws on functional languages; distribution, retries, and storage belong to the runtime.27
React + Redux: unidirectional data flow, immutable state, changes through reducer functions
Elm: enforces pure functional programming on the frontend
Common Misconceptions and Corrections
Misconception 1: "Functional programming has no mutability whatsoever"
Inaccurate. Even purely functional languages have mechanisms for handling side effects (Haskell's IO monad, ST monad). Multi-paradigm functional languages (OCaml, F#, Scala) explicitly allow mutable references. The essence of functional programming is not "no mutation" but rather "immutable by default, mutation made explicit."
Misconception 2: "Functional programming doesn't use objects"
Inaccurate. F#, OCaml, and Scala all have object systems. Haskell also builds object-like abstractions through records and type classes. Functional programming is not a negation of OOP but a paradigm with different priorities.
Misconception 3: "Recursion is always better than iteration"
Inaccurate. JavaScript's specification includes proper tail calls, but engine support differs: JavaScriptCore supports them in strict mode, whereas code cannot rely on them across engines.28 Deep recursion is not a substitute for iteration in CPython either. When clarity is equal, use the form the target runtime supports naturally.
Misconception 4: "You need to know category theory to understand monads"
Inaccurate. Category theory is not a prerequisite for using monads. Start with sequencing computations within a context. The box metaphor can help initially, but it does not explain every case, especially IO actions. In practice, learn the operation types and the monad laws.
Personal note: That said, say this out loud in a functional programming community and brace for people to throw a fit. Every programming community eventually optimizes for memes and turns dogmatic.
Misconception 5: "Functional programming is not practical in industry"
Inaccurate. Published industry examples include WhatsApp's Erlang/FreeBSD infrastructure, Jane Street's OCaml, Meta/Facebook's Haskell-based Sigma, Twitter's Scala, and Klarna's Erlang. The sources cover different periods and do not confirm every system's current architecture.2930313233 They do refute the claim that functional languages have no industrial use.
Personal note: I labeled this a misconception, but honestly I'm not sure it actually is one. I learned functional programming because people said it would bump up the leading digit of your salary, and it did change things. Just in the direction of a decrease.
Functional Anti-Patterns
1. Side effects inside map
Here, the only goal is to record names, but map creates a new array that the caller discards.
const items = ["Ada", "Grace"];
const sent = [];
items.map(name => { sent.push(name); });
console.log(sent.join(","));
Use forEach when recording the names is all that is needed. For asynchronous work, await each item in a for...of loop or pass the Promise array produced by map to Promise.all to wait for them together; in the latter case, the new array is actually used.
// Use forEach when only synchronous effects are needed.
// Await asynchronous work with for...of or Promise.all, as shown below.
const items = ["Ada", "Grace"];
const sent = [];
function recordName(name) { sent.push(name); }
items.forEach(recordName);
// This example returns a result string instead of sending real email.
async function sendEmail(name) {
return "sent: " + name;
}
async function sendSequentially() {
const results = [];
for (const item of items) {
results.push(await sendEmail(item));
}
return results;
}
async function sendConcurrently() {
return Promise.all(items.map(sendEmail));
}
async function main() {
console.log(sent.join(","));
console.log((await sendSequentially()).join(","));
console.log((await sendConcurrently()).join(","));
}
main().catch(error => { console.error(error); process.exitCode = 1; });
Personal note: When I see
map, I read it as "this turns each value into something new and builds a new array." If the callback also changes outside variables and even sends email, I have to open every callback to find out what actually happens. If the new array is thrown away and the callback only does this kind of work, the code has not become functional. It has hidden side effects behind something that looks like a transformation.
2. Excessive point-free style
-- Valid Haskell, but unnecessarily difficult to read.
processAll :: ((a, b) -> c -> d) -> (a, b) -> (d -> e) -> c -> e
processAll = ((.) . (.)) (flip (.)) (uncurry . curry)
processAllReadable :: ((a, b) -> c -> d) -> (a, b) -> (d -> e) -> c -> e
processAllReadable f pair after x = after (f pair x)
main :: IO ()
main = do
let f (x, y) z = x + y + z :: Int
print (processAll f (1, 2) (* 2) 3, processAllReadable f (1, 2) (* 2) 3)
Point-free style should only be used when it improves readability.
Personal note: Point-free code at this level is closer to submitting a cipher than transferring knowledge to your colleagues.
3. Premature monad abstraction
import Control.Monad.Trans.Class (lift)
import Control.Monad.Trans.Except (ExceptT, runExceptT, throwE)
import Control.Monad.Trans.Reader (ReaderT, ask, runReaderT)
import Control.Monad.Trans.State.Strict (StateT, get, modify', runStateT)
newtype Config = Config Int
newtype World = World Int deriving Show
data AppError = NegativeStep deriving Show
type App a = ReaderT Config (StateT World (ExceptT AppError IO)) a
advance :: App Int
advance = do
Config step <- ask
if step < 0
then lift (lift (throwE NegativeStep))
else do
lift (modify' (\(World n) -> World (n + step)))
World n <- lift get
pure n
runApp :: Int -> IO (Either AppError (Int, World))
runApp step = runExceptT (runStateT (runReaderT advance (Config step)) (World 0))
main :: IO ()
main = do
runApp 3 >>= print
runApp (-1) >>= print
A three-level stacked monad is almost always overkill. Start with a single IO or a single Either, then raise the level of abstraction only when necessary.
4. Space leaks caused by lazy evaluation
The classic Haskell pitfall.
import Data.List (foldl')
sumBad, sumGood :: Integer
sumBad = foldl (+) 0 [1..1000000]
sumGood = foldl' (+) 0 [1..1000000]
main :: IO ()
main = print (sumBad, sumGood)
If you don't know the difference between foldl and foldl', memory usage will explode on large lists. This is the trap that lazy evaluation sets.
5. Using type class hierarchies like OOP class hierarchies
-- Anti-pattern: reproducing a deep taxonomy with type classes.
class Animal a where
sound :: a -> String
class Animal a => Mammal a where
warmBlooded :: a -> Bool
class Mammal a => Dog a where
fetch :: a -> String
data PetDog = PetDog
instance Animal PetDog where
sound _ = "woof"
instance Mammal PetDog where
warmBlooded _ = True
instance Dog PetDog where
fetch _ = "ball"
main :: IO ()
main = print (sound PetDog, warmBlooded PetDog, fetch PetDog)
Type classes are not a substitute for OOP inheritance hierarchies. They are a different tool entirely.
6. Accumulating intermediate lists
import Data.List (foldl')
-- Source-level stages; allocation depends on laziness and GHC list fusion.
resultPipeline :: [Int] -> Int
resultPipeline = sum . map (* 2) . filter even . map (+ 1)
resultFold :: [Int] -> Int
resultFold = foldl' step 0
where
step acc x = let y = x + 1
in if even y then acc + y * 2 else acc
main :: IO ()
main = print (resultPipeline [1..10], resultFold [1..10])
List fusion often optimizes this automatically, but it is safer to explicitly consolidate using streams or folds.
The following mistakes concern JavaScript and TypeScript uses of map, filter, and reduce. Their syntax is valid, which makes them easy to miss in review, including when reviewing code produced by AI coding tools.
7. Passing an async callback to map without awaiting
An async callback makes map return an array of promises. Unless the caller waits for them, the next line can run before the saves finish and save failures do not reach it through an awaited result. An async callback does not make forEach wait either.
const saved = [];
const save = async (id) => { await new Promise((r) => setTimeout(r, 10)); saved.push(id); return id; };
const ids = [1, 2, 3];
const results = ids.map(async (id) => save(id));
console.log(results); // [ Promise { <pending> }, Promise { <pending> }, Promise { <pending> } ]
console.log("saved:", saved.length); // saved: 0
Wait for the promises with Promise.all. The calls made by the map callback have already started the work, so a large input may require batching or a concurrency limit; use await inside a for...of loop when each item must finish before the next begins.
// saved, save and ids are the same as above.
const results = await Promise.all(ids.map((id) => save(id)));
console.log(results); // [ 1, 2, 3 ]
console.log("saved:", saved.length); // saved: 3
8. Mutating the original objects inside map
map creates a new array, but it does not create new objects for the elements. Changing a property of the object the callback receives changes the object in the original array, and both arrays end up pointing at the same objects.
const users = [{ name: "Ada", active: false }];
const activated = users.map((u) => { u.active = true; return u; });
console.log(users[0].active, activated[0] === users[0]); // true true
const users2 = [{ name: "Ada", active: false }];
const activated2 = users2.map((u) => ({ ...u, active: true }));
console.log(users2[0].active, activated2[0] === users2[0]); // false false
Build the changed object with spread syntax. Spread copies only one level, so if a nested object must change, create that level anew as well.
9. map(parseInt)
map passes the index and the array to the callback along with the value. parseInt treats its second argument as a radix, so indexes 1 and 2 become radixes and produce NaN. Passing a function that takes several parameters straight to map causes this kind of bug.
console.log(["1", "2", "3"].map(parseInt)); // [ 1, NaN, NaN ]
console.log(["1", "2", "3"].map((s) => Number.parseInt(s, 10))); // [ 1, 2, 3 ]
10. Dropping empty values with filter(Boolean)
Using filter(Boolean) to remove only null and undefined also removes valid values such as 0, the empty string and false. A meaningful value like a stock count of 0 disappears without any warning.
const stock = [0, 3, null, 5, undefined];
console.log(stock.filter(Boolean)); // [ 3, 5 ]
console.log(stock.filter((n) => n != null)); // [ 0, 3, 5 ]
n != null removes only null and undefined. In TypeScript, writing it as a type guard such as (n): n is number => n != null also narrows the result array to number[].
11. Copying the accumulator with spread on every reduce step
If reduce builds an object by spreading { ...acc } at every step, each step copies the properties collected so far. With a growing set of distinct keys, that adds up to quadratic work and becomes much slower as the input grows.
const users = [{ id: "a", name: "Ada" }, { id: "g", name: "Grace" }];
const byIdSlow = users.reduce((acc, u) => ({ ...acc, [u.id]: u }), {}); // copies everything at each step
const byId = Object.fromEntries(users.map((u) => [u.id, u])); // builds it once
console.log(Object.keys(byIdSlow), Object.keys(byId)); // [ 'a', 'g' ] [ 'a', 'g' ]
Use Object.fromEntries or a Map, or add to a single accumulator object inside reduce. That accumulator is a local value created inside reduce and is never observed from outside, so this kind of mutation does not conflict with functional principles.
12. A sort in the middle of a chain mutating the original
sort and reverse look as if they return a new array, but they change the original array and return it. Placed between map and filter calls, the change to the original is easy to miss.
const scores = [40, 90, 70];
const top = scores.sort((a, b) => b - a).slice(0, 2);
console.log(top, scores); // [ 90, 70 ] [ 90, 70, 40 ]
const scores2 = [40, 90, 70];
const top2 = scores2.toSorted((a, b) => b - a).slice(0, 2);
console.log(top2, scores2); // [ 90, 70 ] [ 40, 90, 70 ]
ES2023 toSorted, toReversed and toSpliced return copies (Node.js 20 or later). In older environments, copy first, as in [...scores].sort(...).
Criticisms of Functional Programming
Learning Curve
Mathematical terms such as monad, functor, and applicative and the abstract thinking involved raise the barrier to entry; developers accustomed to imperative or object-oriented programming go through "re-learning."
Complexity of the I/O Model
Monad transformers can compose effects, but learning the stack and its ordering takes work.
Memory Allocation Overhead
Immutability causes frequent allocation of new objects. Persistent data structures and compiler optimizations help mitigate this, but it remains a burden in latency-critical systems.
The Readability Debate
Point-free style, monadic do-notation, and type classes are powerful once familiar, but newcomers can find them cryptic and code reviews can take more work.
Why It Matters Now
Several changes have driven renewed interest in functional programming since the 2010s:
- Multi-core era: The cost of concurrent mutable state is growing.
- Distributed systems: Immutability and message passing are a natural fit.
- Data pipelines: map/reduce interfaces draw on functional languages.
- Front-end state management: One-way flow in React/Redux.
- Type system evolution: TypeScript and Rust have absorbed influences from the ML family.John Hughes's Why Functional Programming Matters is a classic paper that frames the core value of functional programming as the modularity afforded by higher-order functions and lazy evaluation.34 Paul Hudak's survey is a representative overview that traces the history and technical characteristics of functional languages from lambda calculus through Lisp, ISWIM, FP, ML, Miranda, and Haskell.35
Today, being a functional programmer is less about specializing in Haskell than about applying functional thinking in the language you use.
Learning Path
Getting started with functional thinking is more about shifting your mindset than choosing a language.36
1. Start with familiar languages
- map, filter, reduce in JavaScript
- List comprehensions and functools in Python
- LINQ in C#
- Reduce mutability and consciously use function composition
2. Expand to multi-paradigm functional languages
- One of F#, OCaml, or Scala
- Get comfortable with their type systems and pattern matching
3. Take on the challenge of pure functional programming
- Haskell or Elm
- For Haskell: learn monads, type classes, and lazy evaluation
4. Strengthen theoretical foundations
- Lambda calculus
- Introduction to type theory (Pierce's "Types and Programming Languages")
- Category theory (optional)Key questions:
-Can this problem be expressed as a flow of data transformations?
-Can this state change be replaced with the creation of a new value?
-Can this side effect be made explicit in the type system?
-Can this loop be expressed as a higher-order function?Summary
Functional Programming is a paradigm rooted in lambda calculus from the 1930s, evolving through Lisp (1958), ML (1973), and Haskell (1990) into the modern era. Its five core principles are as follows.
1. Functions are first-class citizens.
2. Functions are close to mathematical functions (purity).
3. Data is immutable.
4. Side effects are made explicit.
5. The units of abstraction are higher-order functions and function composition.Functional Programming is not a replacement for object-oriented programming, but a complement to it. Immutability and pure computation have grown even more practical across multi-core and distributed systems, and core functional techniques have been widely absorbed into modern mainstream languages. A "functional programmer" is less a user of a specific language and more a developer who knows how to apply functional thinking.
See Also
Programming Paradigms
Design Patterns
Lambda Calculus
Monad
Type Systems
Algebraic Data Type
Result Type
Option Type
Persistent Data Structures
Referential Transparency
Higher-Order Functions
Function Composition
Lazy Evaluation
Tail Call Optimization
Hindley-Milner Type System
Actor Model
References
Hughes, John (1989). "Why Functional Programming Matters". The Computer Journal. 32 (2): 98–107.
Hudak, Paul (1989). "Conception, Evolution, and Application of Functional Programming Languages". ACM Computing Surveys. 21 (3): 359–411.
Moggi, Eugenio (1991). "Notions of computation and monads". Information and Computation. 93 (1): 55–92.
Pierce, Benjamin C. (2002). Types and Programming Languages. MIT Press.
External Links
Official Documentation / Language Sites
Key Papers / Historical Sources
Overview
Category: Programming | Programming Paradigms | Programming Languages | Software Engineering | WIKI
Footnotes
- Turing (1936), appendix: equivalence of formal models ↩
- Haskell 2010 Report ↩
- McCarthy, John (1960). "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I". Communications of the ACM. 3 (4): 184–195. ↩
- Landin, Peter J. (1966). "The Next 700 Programming Languages". Communications of the ACM. 9 (3): 157–166. ↩
- Landin (1966), experimental prototype, p. 160 ↩
- Backus, John (1978). "Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs". Communications of the ACM. 21 (8): 613–641. doi:10.1145/359576.359579. ↩
- Milner, Robin; Tofte, Mads; Harper, Robert; MacQueen, David (1997). *The Definition of Standard ML (Revised)*. MIT Press. ML's historical background connects to the LCF theorem prover. ↩
- MacQueen, Harper and Reppy, The History of Standard ML ↩
- Turner, David. The Miranda Programming Language. Miranda is a lazy/pure functional language with commercial support from Research Software Ltd. and directly influenced Haskell. ↩
- Hudak, Paul; Hughes, John; Peyton Jones, Simon; Wadler, Philip (2007). "A History of Haskell: Being Lazy With Class". HOPL III. ↩
- Changes from Haskell 1.2 to Haskell 1.3 ↩
- Virding, Erlang design and the actor model (2012) ↩
- Odersky, 10 Years of Scala (2014) ↩
- Scala 2.12 specification, historical preface ↩
- GHC User's Guide. "Bang patterns and Strict Haskell". GHC notes that lazy evaluation is the default, and thunk elimination and strictness control are critical in performance-sensitive code. ↩
- Haskell 2010 Report, expressions and pattern matching ↩
- Wadler, Philip; Blott, Stephen (1989). "How to Make Ad-Hoc Polymorphism Less Ad Hoc". POPL '89: Proceedings of the 16th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. pp. 60–76. doi:10.1145/75277.75283. ↩
- Wadler, Philip (1995). "Monads for functional programming". Advanced Functional Programming. Lecture Notes in Computer Science. Vol. 925. pp. 24–52. doi:10.1007/3-540-59451-5_2. Moggi's theoretical starting point should also be consulted in "Notions of Computation and Monads". ↩
- Moggi, Eugenio (1991). "Notions of computation and monads". Information and Computation. 93 (1): 55–92. doi:10.1016/0890-5401(91)90052-4. ↩
- Moggi, author publication list (1988, 1989, 1991) ↩
- Haskell 2010 Language Report, §7.2 Sequencing I/O Operations. Passing the result of one IO action to the next with >>= and do notation. ↩
- Haskell 2010 Report ↩
- Koka book, effect types and handlers ↩
- containers, Data.Map.Strict operation complexities ↩
- Okasaki, Chris (1998). *Purely Functional Data Structures*. Cambridge University Press. ISBN 0-521-66350-4. ↩
- base 4.18.3.0, Data.Foldable (also in verified GHC bindist) ↩
- Dean and Ghemawat (2004), MapReduce ↩
- WebKit, ECMAScript 6 Proper Tail Calls ↩
- Reed, Rick. "That's 'Billion' with a 'B': Scaling to the Next Level at WhatsApp". InfoQ / Erlang Factory SF Bay, 2014. WhatsApp's scaling case study based on Erlang and FreeBSD. ↩
- Jane Street. "Technology at Jane Street". Jane Street writes as many systems as possible in OCaml. ↩
- Meta Engineering. "Fighting spam with Haskell". Facebook/Meta's application of Haskell in the Sigma rule engine. ↩
- Twitter. "Effective Scala". Twitter's internal guide to Scala usage and functional/expression-oriented style. ↩
- Erlang Solutions. "Klarna case study". Klarna's high-availability payment system built on Erlang. ↩
- Hughes, John (1989). "Why Functional Programming Matters". The Computer Journal. 32 (2): 98–107. doi:10.1093/comjnl/32.2.98. Author's public version: Chalmers mirror. ↩
- Hudak, Paul (1989). "Conception, Evolution, and Application of Functional Programming Languages". ACM Computing Surveys. 21 (3): 359–411. doi:10.1145/72551.72554. ↩
- Pierce, Benjamin C. (2002). *Types and Programming Languages*. MIT Press. ISBN 978-0-262-16209-8. ↩