@certes/combinator

Type-safe, pure functional combinators for TypeScript. A comprehensive collection of classical combinatory logic primitives for composable, point-free programming.

> [!CAUTION]
> ### ⚠️ Active Development & Alpha Status
> This repository is currently undergoing active development.
>
> Until 1.0.0 release:
> * Stability: APIs are subject to breaking changes without prior notice.
> * Releases: Current releases (tags/npm packages) are strictly for testing and integration feedback.
> * Production: Do not use this software in production environments where data integrity or high availability is required.

---

Installation

``bash
npm install @certes/combinator
`

Quick Start

`typescript
import { compose, pipe, fork, flip } from '@certes/combinator';

// Compose functions right-to-left
const addThenDouble = compose((x: number) => x * 2)((x: number) => x + 3);
addThenDouble(5); // 16 ((5 + 3) * 2)

// Pipe functions left-to-right
const doubleThenAdd = pipe((x: number) => x * 2)((x: number) => x + 3);
doubleThenAdd(5); // 13 ((5 * 2) + 3)

// Fork: apply one value to two functions, combine results
const average = fork((sum: number) => (length: number) => sum / length)
((nums: number[]) => nums.reduce((a, b) => a + b, 0))
((nums: number[]) => nums.length);

average([1, 2, 3, 4, 5]); // 3
`

Available Combinators

| Combinator | Name | Lambda | Signature | Description |
|------------|------|--------|-----------|-------------|
| A | Apply | $\lambda ab.ab$ | (a → b) → a → b | Apply function to argument |
| B | Bluebird | $\lambda abc.a(bc)$ | (a → b) → (c → a) → c → b | Function composition (right-to-left) |
| BL | Blackbird | $\lambda abcd.a(bcd)$ | (c → d) → (a → b → c) → a → b → d | Compose unary after binary |
| C | Cardinal | $\lambda abc.acb$ | (a → b → c) → b → a → c | Flip argument order |
| I | Idiot | $\lambda a.a$ | a → a | Identity function |
| K | Kestrel | $\lambda ab.a$ | a → b → a | Constant (returns first) |
| KI | Kite | $\lambda ab.b$ | a → b → b | Returns second argument |
| OR | — | $\lambda abc.(ac) \lor (bc)$ | (a → b) → (a → b) → a → Bool | Logical disjunction |
| Phi | Phoenix | $\lambda abcd.a(bd)(cd)$ | (a → b → c) → (d → a) → (d → b) → d → c | Fork combinator |
| Psi | — | $\lambda abcd.a(bc)(bd)$ | (b → b → c) → (a → b) → a → a → c | On combinator |
| Q | Queer bird | $\lambda abc.b(ac)$ | (a → b) → (b → c) → a → c | Pipe (left-to-right composition) |
| S | Starling | $\lambda abc.ac(bc)$ | (a → b → c) → (a → b) → a → c | Substitution |
| Th | Thrush | $\lambda ab.ba$ | a → (a → b) → b | Reverse application |
| V | Vireo | $\lambda abc.cab$ | a → b → (a → b → c) → c | Pairing |
| W | Warbler | $\lambda ab.abb$ | (a → a → b) → a → b | Duplication |

$3


`typescript
// Common functional programming names
import {
apply, // A
compose, // B
flip, // C
identity, // I
constant, // K
second, // KI
alternation, // OR
fork, // Phi
on, // Psi
pipe, // Q
substitution, // S
applyTo, // Th
pair, // V
duplication // W
} from '@certes/combinator';
`

Practical Examples

$3

`typescript
import { pipe } from '@certes/combinator';

// Transform data through multiple steps (left-to-right)
const processUser = pipe
((user: { name: string }) => user.name)
((name: string) => name.toUpperCase());

processUser({ name: 'alice' }); // 'ALICE'
`

$3


`typescript
import { flip } from '@certes/combinator';

const divide = (a: number) => (b: number) => a / b;
const divideBy10 = flip(divide)(10);

divideBy10(100); // 10 (100 / 10)
divideBy10(50); // 5 (50 / 10)
`

$3


`typescript
import { duplication } from '@certes/combinator';

const multiply = (a: number) => (b: number) => a * b;
const square = duplication(multiply);

square(7); // 49 (7 * 7)
square(12); // 144 (12 * 12)
`

$3


`typescript
import { fork } from '@certes/combinator';

// Calculate variance: E[X²] - E[X]²
const variance = fork
((sumSq: number) => (sum: number) => sumSq - sum * sum)
((nums: number[]) => nums.reduce((acc, x) => acc + x * x, 0) / nums.length)
((nums: number[]) => nums.reduce((acc, x) => acc + x, 0) / nums.length);

variance([1, 2, 3, 4, 5]); // 2
`

$3


`typescript
import { on } from '@certes/combinator';

// Compare two strings by length
const compareByLength = on
((a: number) => (b: number) => a - b)
((s: string) => s.length);

compareByLength('hello')('world'); // 0 (same length)
compareByLength('hi')('world'); // -3 (2 - 5)
`

$3


`typescript
import { substitution } from '@certes/combinator';

// Apply argument to function and transformed version
const addWithDouble = substitution
((a: number) => (b: number) => a + b)
((x: number) => x * 2);

addWithDouble(5); // 15 (5 + 10)
`

Compose vs Pipe


`typescript
import { compose, pipe } from '@certes/combinator';

const double = (x: number) => x * 2;
const addThree = (x: number) => x + 3;

// Compose: right-to-left (mathematical notation)
compose(addThree)(double)(5); // 13 (addThree(double(5)))

// Pipe: left-to-right (data flow)
pipe(double)(addThree)(5); // 13 (double(5) then addThree)
`

Theory

These combinators form the basis of combinatory logic, a notation for mathematical logic without variables. The SKI combinator calculus (using S, K, and I) is Turing complete, meaning any computable function can be expressed using only these three combinators.

Key Properties:

- Pure functions — No side effects, referentially transparent
- Point-free style — Function composition without explicit parameters
- Algebraic laws — Combinators satisfy formal algebraic properties

$3


`typescript
// Identity laws
I(x) ≡ x
K(x)(y) ≡ x
KI(x)(y) ≡ y

// Composition
B(f)(g)(x) ≡ f(g(x))
Q(f)(g)(x) ≡ g(f(x))

// Self-application
W(f)(x) ≡ f(x)(x)
V(x)(y)(f) ≡ f(x)(y)

// Distributive
S(f)(g)(x) ≡ f(x)(g(x))
Phi(f)(g)(h)(x) ≡ f(g(x))(h(x))
``

Further Reading

- To Mock a Mockingbird by Raymond Smullyan
- Combinatory Logic - Stanford Encyclopedia of Philosophy
- SKI Combinator Calculus
- Lambda Calculus
- Combinator Birds

License

MIT

Contributing

Part of the @certes monorepo. See main repository for contribution guidelines.