README

Combinator

This package provides a comprehensive collection of well-known combinators for PHP, enabling a more declarative, point-free programming style.

Description

A combinator is a higher-order function that uses only function application and previously defined combinators to define a result from its arguments. This concept was introduced by Moses Schönfinkel in 1920 and later developed by Haskell Curry.

In computer science, combinatory logic serves as a theoretical model of computation and is a cornerstone of functional programming language design. The core idea is to build complex functions without ever having to mention variables.

Why use Combinators?

Using combinators can help you:

Write cleaner, more declarative code: By abstracting away function composition and argument manipulation, your code can become more readable and expressive.
Avoid temporary variables: Combinators provide powerful ways to pipe data through a series of functions in a clean, fluent manner.
Explore functional programming: This library provides a practical way to learn about and experiment with fundamental concepts of functional programming and lambda calculus, right within PHP.

Requirements

PHP >= 8.0

Installation

You can install the package via Composer:

composer require loophp/combinator

Available Combinators

The following is a list of the combinators available in this package.

Name	Alias	Haskell	Lambda Calculus	Term Definition (JS-like)	Type
A	Applicator	`$`	`λab.ab`	`a => b => a(b)`	`(a -> b) -> a -> b`
B	Bluebird	`.`	`λabc.a(bc)`	`a => b => c => a(b(c))`	`(b -> c) -> (a -> b) -> a -> c`
B₁	Blackbird	`...`	`λabcd.a(bcd)`	`a => b => c => d => a(b(c)(d))`	`(c -> d) -> (a -> b -> c) -> a -> b -> d`
C	Cardinal	`flip`	`λabc.acb`	`a => b => c => a(c)(b)`	`(a -> b -> c) -> b -> a -> c`
D	Dove		`λabcd.ab(cd)`	`a => b => c => d => a(b)(c(d))`	`(b -> c -> d) -> b -> (a -> c) -> a -> d`
E	Eagle		`λabcde.ab(cde)`	`a => b => c => d => e => a(b)(c(d)(e))`	`(a -> d -> e) -> a -> (b -> c -> d) -> b -> c -> e`
F	Finch		`λabc.cba`	`a => b => c => c(b)(a)`	`a -> b -> (b -> a -> c) -> c`
G	Goldfinch		`λabcd.ad(bc)`	`a => b => c => d => a(d)(b(c))`	`(a -> b -> c) -> (d -> b) -> d -> a -> c`
H	Hummingbird		`λabc.abcb`	`a => b => c => a(b)(c)(b)`	`(a -> b -> a -> c) -> a -> b -> c`
I	Identity (Idiot)	`id`	`λa.a`	`a => a`	`a -> a`
J	Jay		`λabcd.ab(adc)`	`a => b => c => d => a(b)(a(d)(c))`	`(a -> b -> b) -> a -> b -> a -> b`
K	Kestrel	`const`	`λab.a`	`a => b => a`	`a -> b -> a`
Ki	Kite	`flip const`	`λab.b`	`a => b => b`	`a -> b -> b`
L	Lark		`λab.a(bb)`	`a => b => a(b(b))`	`*`
M	Mockingbird		`λa.aa`	`a => a(a)`	`*`
O	Owl		`λab.b(ab)`	`a => b => b(a(b))`	`((a -> b) -> a) -> (a -> b) -> b`
Omega	Ω		`λa.(aa)(aa)`	`a => (a(a))(a(a))`	`*`
Φ	Phoenix		`λabcd.a(bd)(cd)`	`a => b => c => d => a(b(d))(c(d))`	`(b -> c -> d) -> (a -> b) -> (a -> c) -> a -> d`
Ψ	Psi	`on`	`λabcd.a(bc)(bd)`	`a => b => c => d => a(b(c))(b(d))`	`(b -> b -> c) -> (a -> b) -> a -> a -> c`
Q	Queer	`flip (.)`	`λabc.b(ac)`	`a => b => c => b(a(c))`	`(a -> b) -> (b -> c) -> a -> c`
R	Robin		`λabc.bca`	`a => b => c => b(c)(a)`	`a -> (b -> a -> c) -> b -> c`
S	Starling	`<*>`	`λabc.ac(bc)`	`a => b => c => a(c)(b(c))`	`(a -> b -> c) -> (a -> b) -> a -> c`
S'	S Prime		`λabc.a(bc)c`	`a => b => c => a(b(c))(c)`	`(b -> a -> c) -> (a -> b) -> a -> c`
S₂	S-Two	`liftA2`	`λabcd.a(bd)(cd)`	`a => b => c => d => a(b(d))(c(d))`	`(b -> c -> d) -> (a -> b) -> (a -> c) -> a -> d`
T	Thrush	`(&)`	`λab.ba`	`a => b => b(a)`	`a -> (a -> b) -> b`
U	Turing		`λab.b(aab)`	`a => b => b(a(a)(b))`	`((a -> b) -> b) -> (a -> b) -> b`
V	Vireo		`λabc.cab`	`a => b => c => c(a)(b)`	`a -> b -> (a -> b -> c) -> c`
W	Warbler		`λab.abb`	`a => b => a(b)(b)`	`(a -> a -> b) -> a -> b`
Y	Y-Fixed point	`fix`	`λf.(λx.f(xx))(λx.f(xx))`	`f => (x => f(x(x)))(x => f(x(x)))`	`(a -> a) -> a`
Z	Z-Fixed point	`fix`	`λf.(λx.f(λv.xxv))(λx.f(λv.xxv))`	`f => (x => f(v => x(x)(v)))(x => f(v => x(x)(v)))`	`(a -> a) -> a`

* indicates a combinator that is not simply typed because it relies on self-application.

Combinator by Example

Click on any combinator below to see a practical usage example. All combinators are invokable classes, but the easiest way to access them is through the loophp\combinator\Combinators facade, which statically provides each one.

A (Applicator) Combinator

Lambda: λab.ab
Purpose: Applies a function a to an argument b. In Haskell, this is the $ operator. It can help reduce the number of parentheses in complex expressions.

use loophp\combinator\Combinators;

$a = Combinators::A();
$strlen = 'strlen';
$string = 'hello world';

// Instead of $strlen($string)
echo $a($strlen)($string); // Outputs: 11

B (Bluebird) Combinator

Lambda: λabc.a(bc)
Purpose: Function composition. It takes two functions, a and b, and a value c, and applies a to the result of b applied to c. This is . in Haskell.

use loophp\combinator\Combinators;

$b = Combinators::B();
$addOne = fn(int $x): int => $x + 1;
$multiplyByTwo = fn(int $x): int => $x * 2;

// Create a new function: multiply by two, then add one.
$composed = $b($addOne)($multiplyByTwo);

echo $composed(5); // Outputs: 11 (which is 1 + (2 * 5))

B₁ (Blackbird) Combinator

Lambda: λabcd.a(bcd)
Purpose: Extended function composition for three functions: a(b(c(d))).

use loophp\combinator\Combinators;

$blackbird = Combinators::Blackbird();
$wrapInP = fn(string $s): string => "<p>$s</p>";
$toUpper = 'strtoupper';
$addExclamation = fn(string $s): string => "$s!";

$format = $blackbird($wrapInP)($toUpper)($addExclamation);

echo $format('hello'); // Outputs: <p>HELLO!</p>

C (Cardinal) Combinator

Lambda: λabc.acb
Purpose: Flips arguments. It takes a function a and two arguments b and c, and applies a with c as the first argument and b as the second. This is flip in Haskell.

use loophp\combinator\Combinators;

$c = Combinators::C();
$divide = fn(int $x, int $y): float => $x / $y;

$flippedDivide = $c($divide);

echo $flippedDivide(2)(10); // Outputs: 5 (same as $divide(10, 2))

D (Dove) Combinator

Lambda: λabcd.ab(cd)
Purpose: Composes two functions and their arguments: a(b)(c(d)).

use loophp\combinator\Combinators;

$d = Combinators::D();
$add = fn(int $x): callable => fn(int $y): int => $x + $y;
$multiply = fn(int $x): callable => fn(int $y): int => $x * $y;

// Calculates ( (2 + 3) + (4 * 5) ) using curried functions
echo $d($add)($add(2)(3))($multiply(4))(5); // Outputs: 25

E (Eagle) Combinator

Lambda: λabcde.ab(cde)
Purpose: Five-argument composition, useful for deeply nested function calls: a(b)(c(d(e))).

use loophp\combinator\Combinators;

$e = Combinators::E();
$add = fn(int $x): callable => fn(int $y): int => $x + $y;
$multiplyByTwo = fn(int $x): int => $x * 2;
$addOne = fn(int $x): int => $x + 1;

// Equivalent to: $add(10)(($multiplyByTwo($addOne(5))))
echo $e($add)(10)($multiplyByTwo)($addOne)(5); // Outputs: 22

F (Finch) Combinator

Lambda: λabc.cba
Purpose: Reverses the application order. Applies c to b, and then to a.

use loophp\combinator\Combinators;

$f = Combinators::F();
$concat = fn(string $a): callable => fn(string $b): string => $a . $b;

// Instead of $concat(' world')('hello')
echo $f('hello')(' world')($concat); // Outputs: " worldhello"

G (Goldfinch) Combinator

Lambda: λabcd.ad(bc)
Purpose: Applies arguments in a unique order: a(d)(b(c)).

use loophp\combinator\Combinators;

$g = Combinators::G();
$merge = fn(array $a): callable => fn(array $b): array => array_merge($a, $b);
$mapToUpper = fn(array $a): array => array_map('strtoupper', $a);

// Equivalent to $merge(['d', 'e'])(($mapToUpper(['a', 'b', 'c'])))
$result = $g($merge)($mapToUpper)(['a', 'b', 'c'])(['d', 'e']);
print_r($result); // Outputs: Array ( [0] => d [1] => e [2] => A [3] => B [4] => C )

H (Hummingbird) Combinator

Lambda: λabc.abcb
Purpose: Applies a three-argument function, but uses the second argument twice: a(b)(c)(b).

use loophp\combinator\Combinators;

$h = Combinators::H();
$wrap = fn(string $tag): callable => fn(string $content): callable => fn(string $closingTag): string => "<$tag>$content</$closingTag>";

// Uses 'div' as both the opening and closing tag.
$wrapInDiv = $h($wrap)('div');

echo $wrapInDiv('Hello'); // Outputs: <div>Hello</div>

I (Identity / Idiot) Combinator

Lambda: λa.a
Purpose: The identity function. It returns whatever argument it receives. This is id in Haskell.

use loophp\combinator\Combinators;

$i = Combinators::I();

echo $i('Hello World'); // Outputs: Hello World
echo $i(42);            // Outputs: 42

J (Jay) Combinator

Lambda: λabcd.ab(adc)
Purpose: A complex combinator useful for specific recursive or state-passing scenarios: a(b)(a(d)(c)).

use loophp\combinator\Combinators;

$j = Combinators::J();
$log = fn(string $prefix): callable => fn(string $message): string => "[$prefix] $message";

// Creates a nested log message
// Equivalent to $log('INFO')($log('USER')('action'))
echo $j($log)('INFO')('action')('USER'); // Outputs: [INFO] [USER] action

K (Kestrel) Combinator

Lambda: λab.a
Purpose: The constant function. It takes two arguments and always returns the first. This is const in Haskell.

use loophp\combinator\Combinators;

$k = Combinators::K();
$alwaysReturns5 = $k(5);

echo $alwaysReturns5('foo'); // Outputs: 5
echo $alwaysReturns5(123);   // Outputs: 5

Ki (Kite) Combinator

Lambda: λab.b
Purpose: The opposite of the Kestrel. It takes two arguments and always returns the second.

use loophp\combinator\Combinators;

$ki = Combinators::Ki();
$getSecond = $ki('ignored');

echo $getSecond('hello'); // Outputs: hello
echo $getSecond(true);    // Outputs: 1 (for true)

L (Lark) Combinator

Lambda: λab.a(bb)
Purpose: Applies function a to the result of function b applied to itself. This requires b to be a function that can meaningfully accept itself as an argument.

use loophp\combinator\Combinators;

$l = Combinators::L();
$inspectType = fn(mixed $arg): string => "Argument is of type: " . gettype($arg);
$selfApplicable = fn(callable $c): string => "I am a function.";

// Equivalent to $inspectType($selfApplicable($selfApplicable))
echo $l($inspectType)($selfApplicable); // Outputs: Argument is of type: string

M (Mockingbird) Combinator

Lambda: λa.aa
Purpose: Self-application (also known as the ω combinator). It applies its single argument (which must be a function) to itself.

use loophp\combinator\Combinators;

$m = Combinators::M();
$describe = fn(callable $c): string => "This is a closure.";

// Applies the $describe function to itself.
echo $m($describe); // Outputs: This is a closure.

O (Owl) Combinator

Lambda: λab.b(ab)
Purpose: A peculiar form of composition, b(a(b)). Useful in specific recursive algorithms or data structure manipulations.

use loophp\combinator\Combinators;

$o = Combinators::O();
// A curried function to prepend to an array
$prepend = fn(mixed $item): callable => fn(array $list): array => [$item, ...$list];
$reverse = 'array_reverse';

// Equivalent to $reverse($prepend(3)([1, 2])) -> $reverse([3, 1, 2])
$result = $o($prepend)([1, 2])($reverse)(3);
print_r($result); // Outputs: Array ( [0] => 2 [1] => 1 [2] => 3 )

Omega (Ω) Combinator

Lambda: λa.(aa)(aa)
Purpose: The divergent combinator. It is constructed from the Mockingbird (M) as MM. When applied to any function, it creates an infinitely recursive call that will exhaust memory. Do not run this code.

// This will cause a fatal error due to infinite recursion.
// $omega = Combinators::Omega();
// $omega(fn($x) => $x);

Φ (Phoenix) Combinator

Lambda: λabcd.a(bd)(cd)
Purpose: Distributes an argument d across two functions b and c, then combines the results with function a.

use loophp\combinator\Combinators;

$phoenix = Combinators::Phoenix();
$add = fn(int $x): callable => fn(int $y): int => $x + $y;
$multiplyByTwo = fn(int $x): int => $x * 2;
$multiplyByThree = fn(int $x): int => $x * 3;

// Calculates (2 * 10) + (3 * 10)
$calculate = $phoenix($add)($multiplyByTwo)($multiplyByThree);

echo $calculate(10); // Outputs: 50

Ψ (Psi) Combinator

Lambda: λabcd.a(bc)(bd)
Purpose: Another distribution combinator, but this one distributes a function b over two arguments c and d.

use loophp\combinator\Combinators;

$psi = Combinators::Psi();
$makePair = fn(string $a): callable => fn(string $b): string => "($a, $b)";
$getName = fn(array $user): string => $user['name'];
$getEmail = fn(array $user): string => $user['email'];
$user = ['name' => 'John', 'email' => 'john@example.com'];

// Equivalent to $makePair($getName($user))($getEmail($user))
echo $psi($makePair)($getName)($getEmail)($user); // Outputs: (John, john@example.com)

Q (Queer) Combinator

Lambda: λabc.b(ac)
Purpose: A different form of composition, applying b to the result of a applied to c.

use loophp\combinator\Combinators;

$q = Combinators::Q();
$addOne = fn(int $x): int => $x + 1;
$multiplyByTwo = fn(int $x): int => $x * 2;

// Equivalent to $multiplyByTwo($addOne(5))
$composed = $q($addOne)($multiplyByTwo);

echo $composed(5); // Outputs: 12

R (Robin) Combinator

Lambda: λabc.bca
Purpose: Reorders arguments for a two-argument function b.

use loophp\combinator\Combinators;

$r = Combinators::R();
$divide = fn(int $x): callable => fn(int $y): float => $x / $y;

// Equivalent to $divide(10)(2)
echo $r(2)($divide)(10); // Outputs: 5

S (Starling) Combinator

Lambda: λabc.ac(bc)
Purpose: The substitution combinator. It applies a third argument c to both a and b, then applies the result of a(c) to the result of b(c). It is fundamental to combinatory logic.

use loophp\combinator\Combinators;

$s = Combinators::S();
$add = fn(int $x): callable => fn(int $y): int => $x + $y;
$square = fn(int $x): int => $x * $x;

// Equivalent to $add($x)($square($x)) where $x is 3. So 3 + (3*3)
echo $s($add)($square)(3); // Outputs: 12

S' (S Prime) Combinator

Lambda: λabc.a(bc)c
Purpose: A variation of the Starling that provides the final argument c to the outer function a as well. Useful for functions that need both the result of an operation and the original value, such as logging or debugging.

use loophp\combinator\Combinators;

$s_ = Combinators::S_();
$log = fn(string $result): callable => fn(string $original): string => "Input '$original' produced '$result'";
$transform = 'strtoupper';

// Equivalent to $log(strtoupper('hello'))('hello')
$logTransformation = $s_($log)($transform);

echo $logTransformation('hello'); // Outputs: Input 'hello' produced 'HELLO'

S₂ (S-Two) Combinator

Lambda: λabcd.a(bd)(cd)
Purpose: Applies two different functions b and c to the same data d, and then combines their results with a third function a. In Haskell, this is similar to liftA2.

use loophp\combinator\Combinators;

$s2 = Combinators::S2();

$applyAndFormat = fn(callable $operation): callable => fn(int $value): string => "Final result is: " . $operation($value);
$multiply = fn(int $x): callable => fn(int $y): int => $x * $y;
$addOne = fn(int $x): int => $x + 1;
$d = 5;

// Equivalent to $applyAndFormat($multiply(5))($addOne(5)) -> 5 * 6
echo $s2($applyAndFormat)($multiply)($addOne)($d); // Outputs: Final result is: 30

T (Thrush) Combinator

Lambda: λab.ba
Purpose: Reverse application. Applies function b to argument a. This is (&) in Haskell and is useful for data-last programming styles.

use loophp\combinator\Combinators;

$t = Combinators::T();
$multiplyByTwo = fn(int $x): int => $x * 2;

// Instead of $multiplyByTwo(5)
echo $t(5)($multiplyByTwo); // Outputs: 10

U (Turing) Combinator

Lambda: λab.b(aab)
Purpose: A fixed-point combinator. U(f)(g) = g(f(f)(g)). In strict (eager) PHP, recursion requires the step function to call $self($self) explicitly and a seed callable (here: I) as the second argument.

use loophp\combinator\Combinators;

$u = Combinators::U();

// The step function threads self-application to enable recursion.
// $self($self)($g) is evaluated lazily (inside the closure body).
$factStep = fn(callable $self) => fn(callable $g): callable =>
    fn(int $n): int => $n === 0 ? 1 : $n * $self($self)($g)($n - 1);

// Pass I (identity) as the seed: U(factStep)(I) = I(factStep(factStep)(I)) = factStep(factStep)(I)
$factorial = $u($factStep)(Combinators::I());

echo $factorial(5); // Outputs: 120

V (Vireo) Combinator

Lambda: λabc.cab
Purpose: Argument swapping. Given c, a, b, it calls c(a)(b).

use loophp\combinator\Combinators;

$v = Combinators::V();
$str_replace = 'str_replace';
$search = 'foo';
$replace = 'bar';

// Creates a function that replaces 'foo' with 'bar' in a given subject string.
$replaceFoo = $v($search)($replace)($str_replace);

echo $replaceFoo('this is foo'); // Outputs: this is bar

W (Warbler) Combinator

Lambda: λab.abb
Purpose: Duplicates an argument. It applies function a to argument b twice.

use loophp\combinator\Combinators;

$w = Combinators::W();
$add = fn(int $x): callable => fn(int $y): int => $x + $y;

// Equivalent to $add(5)(5)
echo $w($add)(5); // Outputs: 10

Y (Y-Fixed point) Combinator

Lambda: λf.(λx.f(xx))(λx.f(xx))
Purpose: Creates a recursive function from a generator function without naming the recursive function directly.

use loophp\combinator\Combinators;
use Closure;

$factorialGenerator = static fn (Closure $fact): Closure =>
    static fn (int $n): int => (1 >= $n) ? 1 : $n * $fact($n - 1);

$factorial = Combinators::Y()($factorialGenerator);
echo $factorial(6); // Outputs: 720

Z (Z-Fixed point) Combinator

Lambda: λf.(λx.f(λv.xxv))(λx.f(λv.xxv))
Purpose: Creates a recursive function from a generator function using an eta-expanded recursive callback, which is suitable for strict evaluation.

use loophp\combinator\Combinators;
use Closure;

$factorialGenerator = static fn (Closure $fact): Closure =>
    static fn (): Closure =>
        static fn (int $n): int => (1 >= $n) ? 1 : $n * $fact()()($n - 1);

$factorial = Combinators::Z()($factorialGenerator);
echo $factorial()(6); // Outputs: 720

Contributing

Feel free to contribute by sending pull requests. We are a usually very responsive team and we will help you going through your pull request from the beginning to the end.

For some reasons, if you can't contribute to the code and willing to help, sponsoring is a good, sound and safe way to show us some gratitude for the hours we invested in this package.

Sponsor me on Github and/or any of the contributors.

Thanks

Marco Pivetta

Authors

Pol Dellaiera

Changelog

See CHANGELOG.md for a changelog based on git commits. For more detailed changelogs, please check the release changelogs.

loophp / combinator

Maintainers

Package info

Fund package maintenance!

Statistics

Security