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, expressive 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 more capable 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

This small example keeps the primitives grounded. Given student exam results, the pipeline finds the student with the lowest passing score: the “luckiest” one in the narrow sense of just making it.

The data and helper functions are:

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

The same primitives can express a few related queries:

  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

The useful properties are concrete:

  • 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: No shared mutable state removes one common source of coordination bugs, although real parallel execution still depends on the runtime and data representation.
  • Readability: The pipeline exposes the transformation steps directly.

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

Conclusion

Cons lists give a compact way to see the functional habit: data is immutable, behaviour is built by function composition, and recursion can be expressed without mutable loop state. Starting from tiny combinators such as I and K, we can build recursive structures and then use generics to keep those structures typed as they grow.