Functional programming basics

In short

Functional programming (FP) builds a program out of functions that compute values instead of statements that change state: no reassignment, no hidden side effects, and functions themselves are ordinary data that can be passed and returned. Its theoretical base is lambda calculus, which is also a model of computation equivalent in power to a Turing machine. In Indian university syllabi it appears in *Principles of Programming Languages / Programming Paradigms* papers (lambda calculus, evaluation order, higher-order functions) and inside Python, Java and JavaScript courses as lambdas, streams and map/filter/reduce; the exact coverage of lambda calculus varies by university and GATE syllabus revision, so check your own scheme. In placements it is examined constantly: TCS, Infosys, Wipro, Accenture, Cognizant and Capgemini interviews ask pure vs impure functions, Stream pipelines and recursion, while product and data companies (Flipkart, Swiggy, Zomato, Jio, PhonePe, Freshworks, Standard Chartered GBS) use Scala/Spark, Kotlin and React reducers where immutability is the working rule.

Explained

What makes a program "functional"

• Pure function: output depends only on its arguments, and it changes nothing outside itself. f(x) = x*x is pure; a function that prints, writes a file, reads a global or mutates its argument is impure.
• Side effect: any observable change other than returning a value - mutation, I/O, exception, time, random numbers, DB writes.
• Referential transparency: an expression can be replaced by its value anywhere without changing program meaning. It is the property that makes substitution, memoisation and compiler optimisation safe.
• Immutability: data is never modified in place; an "update" returns a new value sharing most of the old structure (persistent data structure). s = s + "x" in Java/Python creates a new string - strings are already immutable there.
• Declarative style: you state *what* the result is (sum of squares of even numbers) rather than *how* to loop and accumulate.
• Expressions over statements: if, case/match and even loops are expressions returning values; there is no need for a mutable temporary.
• No assignment, so no aliasing bugs, no data races: two threads cannot see a half-updated immutable value. This is FP's main industrial selling point.
• Degrees of purity: Haskell is pure (effects are typed and isolated); Scala, F#, Clojure, Erlang, Elixir, OCaml are *functional-first* but allow effects; Java, Python, JavaScript, C++, Kotlin and C# are multi-paradigm with FP features bolted on.

Functions as first-class values

• First-class function: a function can be stored in a variable, put in a list, passed as an argument and returned as a result - like an int.
• Higher-order function (HOF): takes a function as an argument and/or returns a function. map, filter, sorted(key=...), Collections.sort(list, cmp), setTimeout(cb) are HOFs.
• Lambda (anonymous function): a function written inline without a name - lambda x: x*2 (Python), x -> x*2 (Java), x => x*2 (JS/Scala), \x -> x*2 (Haskell), [](int x){return x*2;} (C++).
• Closure: a lambda plus the bindings of the free variables it captured from the enclosing scope; the captured environment outlives the enclosing call. Java captures *effectively final* variables by value; Python and JavaScript capture the variable itself (late binding), which is a classic bug source.
• Currying: rewriting an n-argument function as a chain of one-argument functions. add(a,b) becomes add(a)(b). Formally A×B→C becomes A→(B→C).
• Partial application: fixing some arguments now and the rest later - functools.partial(pow, 2), add5 = add(5). Currying enables it; they are not the same thing.
• Function composition: (f ∘ g)(x) = f(g(x)); build pipelines from small functions instead of one big one.
• Point-free style: defining functions by composition without naming arguments - sumSquares = sum . map square.
• Pure HOF catalogue: map (transform), filter (select), reduce/fold (aggregate), flatMap/bind (transform-and-flatten), zipWith, takeWhile, groupBy, sortBy, all/any.

Recursion as the loop of FP

• With no mutable counter, repetition is recursion: a base case plus a smaller recursive case. Structural recursion walks a data structure (list head/tail, tree left/right).
• Tail recursion: the recursive call is the *last* operation, nothing is pending after it. The compiler can then reuse the same stack frame (tail-call optimisation, TCO), giving O(1) stack - a loop in disguise.
• Convert to tail form with an accumulator parameter carrying the partial result.
• TCO support: guaranteed in Scheme, Haskell, Scala (@tailrec for self-recursion), Erlang, OCaml; not in CPython (recursion limit ~1000, raises RecursionError), nor guaranteed in Java or JavaScript engines (ES6 specified it; engines largely did not implement it). So in Python/Java, deep recursion still overflows - a very common interview trap.
• Mutual recursion (even/odd calling each other), corecursion (producing an infinite stream), and tree recursion (two or more calls per level, e.g. naive Fibonacci) are the standard classifications.
• Memoisation: cache results of a pure function - legitimate only because of referential transparency. Turns exponential naive Fibonacci into linear.
• Trampolining / CPS: techniques to get unbounded recursion on runtimes without TCO.

map, filter, fold and the combinator toolkit

• map: map f [x1..xn] = [f x1 .. f xn] - same length, element-wise, order preserved, trivially parallel.
• filter: keeps elements where a predicate (function returning boolean) is true; length ≤ n.
• reduce / fold: collapses a collection to one value using a binary combining function and usually an initial value (identity/seed).
  • foldr (right fold) associates to the right, can work on infinite lists with a lazy operator, and matches the shape of list construction.
  • foldl (left fold) associates to the left, is tail-recursive and the natural choice for strict languages.
  • They agree only when the operator is associative and the seed is its identity (+ with 0, * with 1, max with −∞). They differ for −, /, string concatenation.
• flatMap / bind: map then concatenate - [[1,2],[3]] → [1,2,3]; the core of Optional, Stream, promises and list monads.
• Algebraic laws used in exams and by optimisers: map f . map g = map (f . g) (map fusion); filter p . filter q = filter (x -> p x && q x); length . map f = length.
• Why it matters industrially: a map/filter/reduce description has no loop order, so the runtime is free to fuse, vectorise or distribute it - exactly what Apache Spark, MapReduce and Java's parallelStream() exploit.
• Reduce must be associative for parallel execution; a non-associative reducer gives different answers on different thread counts.

Lambda calculus - the formal core

• Syntax (untyped λ-calculus): a term is a *variable* x, an *abstraction* λx.M (function), or an *application* M N. That is all - no numbers, booleans or loops are built in.
• Conventions: application is left-associative (M N P = (M N) P); the body of λ extends as far right as possible.
• Free and bound variables: in λx. x y, x is bound by the λ, y is free. A closed term (combinator) has no free variables.
• Three conversion rules:
  • α-conversion (renaming): λx.x ≡ λz.z - bound names are immaterial.
  • β-reduction (computation): (λx.M) N → M[x := N], substituting *capture-avoiding* (rename first if N's free variables would be captured).
  • η-reduction (extensionality): λx. f x → f when x is not free in f.
• Normal form: a term with no β-redex left; a term may have none (Ω = (λx. x x)(λx. x x) reduces to itself forever - non-termination, mirroring undecidability of the halting problem).
• Church–Rosser (confluence): if a term reduces to a normal form, that normal form is unique up to renaming - so the *answer* does not depend on reduction order, though *termination* does. Normal-order reduction (leftmost-outermost) finds a normal form whenever one exists; applicative order may diverge.
• Church encodings (data built from functions only):
  • Numerals: 0 = λf.λx. x, 1 = λf.λx. f x, n = λf.λx. fⁿ x.
  • SUCC = λn.λf.λx. f (n f x); PLUS = λm.λn.λf.λx. m f (n f x); MULT = λm.λn.λf. m (n f).
  • Booleans: TRUE = λx.λy.x, FALSE = λx.λy.y, IF = λb.λt.λe. b t e; pairs: PAIR = λa.λb.λf. f a b.
• Recursion without names - the Y combinator: Y = λf.(λx. f (x x))(λx. f (x x)) satisfies Y g = g (Y g), letting an anonymous function call itself.
• Expressive power: untyped λ-calculus is Turing-complete (Church–Turing thesis). Adding types gives the simply typed λ-calculus (strongly normalising, hence *not* Turing-complete) and then Hindley–Milner type inference, the basis of ML/Haskell/F# type systems and of generics.

Evaluation strategies and laziness

• Call by value (eager/applicative order): arguments evaluated before the call - C, Java, Python, Scala by default. Predictable cost; may compute unused arguments and may diverge where lazy would not.
• Call by name: argument expression substituted unevaluated, re-evaluated at each use.
• Call by need (lazy): call by name plus caching of the first evaluation (a thunk overwritten by its value) - Haskell's default; Scala's lazy val and => T by-name parameters.
• Benefits of laziness: infinite data structures ([1..], streams of primes), only-what-you-need computation, separating generation from selection, cheap if-like short circuiting.
• Costs: unpredictable memory (thunk build-up, "space leaks"), harder reasoning about when effects happen; hence seq/strictness annotations.
• **Short-circuit &&/|| (Python and/or) and the conditional operator are non-strict** even in Java/C/Python - the everyday example of non-strict evaluation.
• Streams in Java 8+, generators in Python, iterators in Rust are lazy pipelines: nothing runs until a terminal operation (collect, reduce, forEach) pulls values.

Handling effects, errors and state functionally

• Effects are pushed to the edges: a pure core computes values; a thin impure shell does I/O. This is the standard architecture advice ("functional core, imperative shell").
• Optional/Maybe replaces null for "absent"; Either/Result carries success or an error value instead of throwing; both are consumed with map/flatMap/getOrElse rather than if (x != null).
• Monad, informally: a type with a constructor (of/pure) and flatMap obeying identity and associativity laws, used to sequence computations that carry extra context - optionality, errors, lists, async, state. Optional, Stream, CompletableFuture and JS Promise all follow this shape.
• State is threaded, not mutated: newState = step(oldState, event) - precisely Redux reducers, Erlang/Elixir processes and event sourcing.
• Persistent data structures (Clojure vectors, Scala List/Vector, Vavr on the JVM) share unchanged sub-structure, so an "update" is O(1) or O(log n), not O(n) copying.
• Algebraic data types (ADTs) and pattern matching: sealed/enum sums of products plus exhaustive match (Scala match, Java sealed interfaces (17+) with record patterns (21+), Python match) - the FP alternative to a class hierarchy with virtual dispatch.

Key points

• Pure function - same input always gives same output, no side effects; the building block of FP.
• Referential transparency - an expression may be replaced by its value; enables memoisation and equational reasoning.
• Immutability - values never change; updates produce new values with structure sharing.
• First-class function - functions are values; higher-order function - a function taking or returning functions.
• Lambda - anonymous function literal; closure - lambda plus its captured free variables.
• Currying - n-ary function as a chain of unary functions; partial application - fixing some arguments early.
• Composition - (f ∘ g)(x) = f(g(x)); pipelines replace nested loops.
• Recursion replaces iteration; tail recursion + TCO gives O(1) stack, but CPython and the JVM do not provide TCO.
• map / filter / reduce - transform, select, aggregate; reduce needs an associative operator with an identity seed for safe parallelism.
• foldl vs foldr - left is tail-recursive and strict-friendly; right matches list structure and works lazily on infinite lists; equal only for associative operators with identity.
• Lambda calculus - variables, abstraction, application; α-conversion renames, β-reduction computes, η-reduction removes redundant wrapping.
• Church–Rosser - normal form is unique if it exists; normal order terminates whenever any order does.
• Church encodings express numbers, booleans and pairs as pure functions; the Y combinator gives recursion to anonymous functions.
• Untyped λ-calculus is Turing-complete; simply typed λ-calculus always terminates and so is strictly weaker.
• Lazy evaluation (call by need) - compute only when demanded, cache the result; enables infinite streams but risks space leaks.
• Maybe/Optional and Either/Result replace nulls and exceptions; flatMap sequences them (monadic style).
• FP's industrial payoff - testability (no setup/mocks for pure code), safe concurrency, and parallel data processing (Spark, streams).
• Trade-off - more allocation and GC pressure, stack depth limits, and a harder debugging story for lazy or deeply composed code.

Formulas and examples

Example 1 - β-reduction, step by step. Reduce (λx. λy. x + 2*y) 3 4.

1. Application is left-associative: ((λx. λy. x + 2*y) 3) 4.
2. β-reduce the inner application, x := 3 → (λy. 3 + 2*y) 4.
3. β-reduce again, y := 4 → 3 + 2*4 = 3 + 8 = **11**.
4. Note the intermediate λy. 3 + 2*y - a *closure* holding x = 3. This is currying in action: a 2-argument function applied one argument at a time.

Example 2 - Church numerals: PLUS 2 3 = 5.

• 2 = λf.λx. f (f x), 3 = λf.λx. f (f (f x)).
• PLUS 2 3 = λf.λx. 2 f (3 f x).
• Inner: 3 f x → f (f (f x)) - three applications.
• Outer: 2 f (f(f(f x))) → f (f (f (f (f x)))) - two more applications on top.
• Total 5 applications of f, i.e. λf.λx. f⁵ x = **5**. Addition is just composing the two "apply-f-n-times" functions.

Example 3 - foldl vs foldr with a non-associative operator. List [1, 2, 3], operator −, seed 0.

• foldr (−) 0 [1,2,3] = 1 − (2 − (3 − 0)) = 1 − (2 − 3) = 1 − (−1) = **2**.
• foldl (−) 0 [1,2,3] = ((0 − 1) − 2) − 3 = (−1 − 2) − 3 = −3 − 3 = **−6**.
• With + and seed 0 both give 6 - because + is associative and 0 is its identity. This is why a parallel reduce demands associativity.

Example 4 - map / filter / reduce on a placement data set. Six offers in ₹ lakh CTC: [3.6, 12.0, 4.8, 18.0, 7.2, 9.6]. Keep offers ≥ ₹6 lakh, apply a 10% revision, then find the total and mean.

1. filter (c -> c >= 6) → [12.0, 18.0, 7.2, 9.6] (4 of 6 retained).
2. map (c -> c * 1.10) → [13.20, 19.80, 7.92, 10.56].
3. reduce (+) 0 → 13.20 + 19.80 = 33.00; 33.00 + 7.92 = 40.92; 40.92 + 10.56 = ₹51.48 lakh.
4. Mean = 51.48 / 4 = ₹12.87 lakh.

double total = offers.stream()                 // Java 8+
        .filter(c -> c >= 6.0)
        .map(c -> c * 1.10)
        .reduce(0.0, Double::sum);             // 51.48

from functools import reduce
total = reduce(lambda a, b: a + b,
               map(lambda c: c * 1.10,
                   filter(lambda c: c >= 6.0, offers)), 0.0)   # 51.48

Example 5 - tail vs non-tail recursion. factorial(5).

• Non-tail: f(5) = 5*f(4) … multiplications are *pending*, so 6 frames (n = 5,4,3,2,1,0) live at the deepest point - O(n) stack. Result 5·4·3·2·1 = 120.
• Tail form fact(n, acc): fact(5,1) → fact(4,5) → fact(3,20) → fact(2,60) → fact(1,120) → fact(0,120) → 120. Nothing pending, so one frame suffices if the language does TCO (Scala/Scheme yes; Python and standard JVM no - in CPython factorial(5000) raises RecursionError at the ~1000 default limit).

Example 6 - memoisation and referential transparency. Naive fib(30) with fib(n)=fib(n−1)+fib(n−2):

• Calls C(30) = 2·F(31) − 1 = 2 × 1,346,269 − 1 = **2,692,537** calls.
• Memoised (cache keyed on n) each of fib(0) … fib(30) is computed once → 31 computations, O(n) time. The cache is valid only because fib is pure - an impure function could not be replaced by a stored value.

Where it is used

• Big-data and analytics engineering: Apache Spark's RDD/DataFrame API is map/filter/reduceByKey on immutable partitions, written in Scala or PySpark - used at Flipkart, Jio, Paytm, Swiggy, Zomato, Fractal, Mu Sigma and in bank data platforms; Spark/Scala is a named skill in many Indian data-engineer job posts.
• Enterprise Java services: Java 8+ lambdas, Stream, Optional and CompletableFuture are standard in TCS, Infosys, Wipro, HCLTech, LTIMindtree and Accenture codebases - and streams questions are near-certain in their interviews.
• Front-end and mobile: React function components with hooks, pure Redux reducers, RxJS/Kotlin Flow operators - immutability is enforced by the framework, so state.push(x) is a bug.
• Telecom, messaging and fintech backends: Erlang/Elixir (immutable processes, pattern matching) behind chat and payment switches; Scala in trading and risk systems at Standard Chartered GBS, Goldman Sachs Bengaluru and Morgan Stanley Mumbai.
• Infrastructure and config as code: Nix, Terraform/HCL and CI pipelines are declarative and idempotent - the same "describe the result, not the steps" idea.
• Testing, QA and compiler work: pure functions need no mocks, so they are the easiest to unit test; property-based testing (QuickCheck, Hypothesis) grew out of FP, and lambda calculus plus type inference underpin compiler and language-tooling roles.

Interview questions

• Q: What is a pure function? A: One whose return value depends only on its arguments and which causes no observable side effect - no mutation, I/O, globals or randomness.
• Q: What is referential transparency and why does it matter? A: An expression can be replaced by its value without changing the program's meaning; it makes caching, reordering, parallelising and equational reasoning safe.
• Q: Difference between a lambda and a closure? A: A lambda is an anonymous function literal; it becomes a closure when it captures free variables from its enclosing scope and keeps them alive after that scope returns.
• Q: Currying vs partial application? A: Currying transforms an n-argument function into a chain of single-argument functions; partial application supplies some arguments now and returns a function expecting the rest. Currying is one way to get partial application.
• Q: What is tail recursion and why is it preferred? A: The recursive call is the last operation, so no frame state is pending and the compiler can reuse the frame - O(1) stack instead of O(n). CPython and the JVM do not guarantee this optimisation.
• Q: How do foldl and foldr differ? A: foldl brackets to the left and is tail-recursive; foldr brackets to the right and can consume lazy or infinite lists. They give the same answer only for an associative operator with the seed as its identity.
• Q: Why must the function passed to a parallel reduce be associative? A: Parallel execution splits and combines partial results in an unspecified grouping, so a non-associative operator yields different answers on different runs or thread counts.
• Q: State β-reduction and reduce (λx. x x)(λy. y). A: (λx.M) N → M[x := N]. Substituting gives (λy.y)(λy.y) → λy.y, the identity function.
• Q: Is untyped lambda calculus Turing-complete? A: Yes - it can encode numbers, booleans, pairs and recursion (Y combinator), and equals Turing machines in power; the simply typed version always terminates and is therefore weaker.
• Q: What does the Church–Rosser theorem say? A: Reduction is confluent: if a term has a normal form it is unique up to renaming, so the result is order-independent even though termination is not.
• Q: What is lazy evaluation and one drawback? A: Arguments are evaluated only when demanded and the result cached (call by need); the drawback is unpredictable memory from accumulated thunks (space leaks) and harder reasoning about when effects run.
• Q: If data is immutable, is FP not wasteful of memory? A: Persistent data structures share the unchanged parts, so an update typically costs O(1) or O(log n) extra nodes, not a full copy - though allocation and GC pressure are genuinely higher than in-place mutation.
• Q: How does FP help concurrency? A: With no shared mutable state there are no data races on values, so immutable structures need no locks and pure functions can be run on any thread.

Common mistakes

• Calling a function pure when it logs, mutates its argument list, reads a global or depends on the clock or a random seed.
• Thinking map with a side-effecting lambda is functional - in Java a Stream with no terminal operation never even runs it.
• Mutating captured state inside a lambda (list.add(x) in a forEach, state.push() in a Redux reducer) and losing thread safety or triggering concurrent-modification errors.
• Assuming foldl and foldr are interchangeable, or omitting the identity seed, then getting a wrong sign or an empty-list error.
• Assuming the language does tail-call optimisation - deep recursion in Python hits the ~1000 recursion limit and in Java throws StackOverflowError.
• Forgetting capture-avoiding renaming in β-reduction, so a free variable gets accidentally bound and the answer is wrong.
• Confusing currying with partial application, or claiming lambda calculus has built-in numbers - numerals are *encodings*, not primitives.
• Writing x = x + 1 style accumulation inside a comprehension or stream instead of using reduce, losing both purity and parallelisability.

Related topics

Recursion and divide-and-conquer algorithms · Lambda calculus and theory of computation · Python essentials · Java essentials · JavaScript essentials · Object-oriented programming concepts