Introduction

Functional programming encourages building software from pure functions and immutable data. Instead of mutating state step by step, we model computations as the evaluation of expressions. In this post we sketch the core ideas with a small but powerful data structure: the cons list.

Lambda Calculus and Combinators

The lambda calculus models computation with nothing more than functions and application. Variables may be bound by lambdas or appear free, and evaluation proceeds by substituting arguments for parameters. Two of its most basic combinators are the identity I and the constant K:

I = \x. x
K = \x. \y. x

Evaluating K I demonstrates how these combinators work:

K I a = (\x. \y. x) I a
      -> (\y. I) a
      -> I
      -> \z. z

K discards its second argument, while I simply returns its input. These tiny building blocks are enough to express common operations on pairs.

Alpha, Beta, and Eta

Three rewrite rules define how lambda terms behave:

• Alpha conversion renames bound variables without changing meaning: \x. x ≡ \y. y.
• Beta reduction applies a function to an argument by substitution: (\x. x + 1) 2 -> 3.
• Eta conversion captures extensional equality: \x. f x ≡ f when x is not free in f.

These rules let us manipulate programs algebraically and reason about equivalence of expressions.

Cons Lists

A list can be represented as nested "cons" cells using only functions:

const NULL = undefined;
const I = x => x;
const K = x => y => x;
const cons = x => y => f => f(x)(y);

Using only K and I, we can recover the head and tail of a cons list:

const head = l => l(K);
const tail = l => l(K(I));

Because lists are just functions, constructing and deconstructing them is done through function application. There is no mutable state, and every new list is built from existing values.

Functors as Structured Loops

In category theory, a functor maps between categories while preserving identity and composition. In programming a functor is any data type that implements a lawful map function. Higher‑order helpers such as map or fold therefore lift ordinary functions to operate over structured data. Instead of explicit loops, we describe "what to do" with each element, and the functor takes care of the traversal.

const map = f => l => (l ? cons(f(head(l)))(map(f)(tail(l))) : NULL);
const fold = f => init => l => (l ? fold(f)(f(init)(head(l)))(tail(l)) : init);

fold captures the idea of iteration—every recursive call processes the next cell until the list is empty. Because functors compose, this approach scales to pipelines of transformations where control flow emerges from the structure of the data rather than explicit mutation.

Recursion via Combinators

To express general recursion in a world of anonymous functions we can use a fixed‑point combinator such as Y:

Y = \f. (\x. f (x x)) (\x. f (x x))

Y g expands to g (Y g), giving g a way to call itself without naming the function. Combined with cons and fold, this allows us to write algorithms like sorting or filtering purely in terms of functions.

Generic Types and Composition

Because every list constructor is just a function, TypeScript’s generics can model them with almost no additional syntax:

type List<T> = (f: (h: T) => (t: List<T>) => unknown) => unknown;
const map = <A, B>(f: (a: A) => B) => (l: List<A>): List<B> =>
    (l ? cons(f(head(l)))(map(f)(tail(l))) : NULL);

The type variable T threads through each definition, giving static guarantees without complicating the underlying lambda terms.

Building Complex Behaviour

With these primitives we can layer increasingly rich utilities:

const join = fold(concat)(NULL);              // flatten nested lists
const concatMap = f => l => join(map(f)(l));  // map then flatten
const zip = f => a => b =>                    // combine two lists
    (a && b ? cons(f(head(a))(head(b)))(zip(f)(tail(a))(tail(b))) : NULL);
const filter = f =>                           // filtering via fold
    compose(reverse)(fold(a => v => (f(v) ? cons(v)(a) : a))(NULL));
const sort = f => l => {                      // quicksort
    if (!l) return NULL;
    const h = head(l), t = tail(l);
    const l1 = filter(x => f(x)(h) <= 0)(t);
    const l2 = filter(x => f(x)(h) > 0)(t);
    return concat(sort(f)(l1))(cons(h)(sort(f)(l2)));
};

These abstractions reuse the same tiny cons, head, and tail definitions. Control flow emerges from function composition rather than special syntax.

Example: Finding the Luckiest Student

To illustrate the power of these functional primitives, let's consider a practical scenario: processing student exam results. We'll define some sample data and build a pipeline to find the student with the lowest passing score (the "luckiest" in terms of just making it).

First, let's define our data structures and helper functions:

const students = ["Alice", "Bob", "Charlie", "Diana"];
const marks = ["85", "92", "78", "88"];

const pass = score => score >= 80;
const compareMarks = (a, b) => a.score - b.score; // ascending order
const student = name => ({ name });
const name = obj => obj.name;

// Additional helper functions for more complex behaviors
const average = l => fold((sum, x) => sum + x)(0)(l) / length(l);
const maxBy = f => l => fold((max, x) => f(x) > f(max) ? x : max)(head(l))(l);
const length = fold(x => acc => acc + 1)(0);

The pipeline below zips students with their marks, filters those who pass, sorts them by score, and extracts the lowest passing mark:

const luckiestStudent = pipe(
    marks,
    fromArray,
    map(Number),
    zip(student)(fromArray(students)),
    filter(pass),
    sort(compareMarks),
    head,
    name,
);

More Complex Behavior Examples

Here are additional examples showcasing the versatility of functional composition:

1. Calculate Average Score: const avgScore = pipe(marks, fromArray, map(Number), average);

2. Find Top Performer: const topStudent = pipe(marks, fromArray, map(Number), zip(student)(fromArray(students)), maxBy(x => x.score), name);

3. Count Passing Students: const passingCount = pipe(marks, fromArray, map(Number), filter(pass), length);

4. Generate Honor Roll: const honorRoll = pipe(marks, fromArray, map(Number), zip(student)(fromArray(students)), filter(x => x.score >= 90), map(name));

Why These Patterns Are Useful

These functional patterns offer several advantages:

• Immutability: Data structures like cons lists cannot be modified after creation, preventing accidental side effects and making code more predictable.
• Composability: Functions can be easily combined using pipe or function composition, allowing complex behaviors to be built from simple parts.
• Testability: Pure functions with no side effects are easier to unit test and reason about.
• Parallelization: Since there's no shared mutable state, operations can be parallelized more easily.
• Expressiveness: Declarative code reads like the problem statement, making it self-documenting.

Such a complex workflow is assembled from small, pure functions—no mutable state or explicit loops required.

Conclusion

Cons lists illustrate the advantages of functional programming: data is immutable, behaviour is described declaratively, and even loops or recursion emerge from function application. Starting from tiny combinators such as I and K, we can build rich recursive structures and use generics to scale those ideas to large systems with strong static guarantees.