Skip to content
/ combinator Public

A curated list of combinators

# loophp/combinator

Switch branches/tags
Could not load branches
Nothing to show

# Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

## Latest commit

`78f2313`

## Files

Failed to load latest commit information.
Type
Name
Commit time

# Combinator

## Description

This package provides a list of well known Combinators.

A combinator is a higher-order function that uses only function application and earlier defined combinators to define a result from its arguments. It was introduced in 1920 by Moses Schönfinkel and Haskell Curry, and has more recently been used in computer science as a theoretical model of computation and also as a basis for the design of functional programming languages. Combinators which were introduced by Schönfinkel in 1920 with the idea of providing an analogous way to build up functions - and to remove any mention of variables - particularly in predicate logic.

• PHP >= 8

## Installation

`composer require loophp/combinator`

## Available combinators

Name Alias Composition Composition using S and K Haskell Lambda calculus Term definition (JS like) Type # Arguments
A Apply `SK(SK)`
`(S(K))(S(K))`
`\$` `λab.ab` `a => b => a(b)` `(a -> b) -> a -> b` 2
B Bluebird `S(KS)K`
`S(KS)K`
`.` `λabc.a(bc)` `a => b => c => a(b(c))` `(a -> b) -> (c -> a) -> c -> b` 3
Blackbird Blackbird `BBB`
`(S(K(S(KS)K)))(S(KS)K)`
`...` `λabcd.a(bcd)` `a => b => c => => d => a(b(c)(d))` `(c -> d) -> (a -> b -> c) -> a -> b -> d` 4
C Cardinal `S(BBS)(KK)`
`((S((S(K(S(KS)K)))S))(KK))`
`flip` `λabc.acb` `a => b => c => a(c)(b)` `(a -> b -> c) -> b -> a -> c` 3
D Dove `BB`
`(S(K(S(KS)K)))`
`λabcd.ab(cd)` `a => b => c => d => a(b)(c(d))` `(a -> c -> d) -> a -> (b -> c) -> b -> d` 4
E Eagle `B(BBB)`
`(S(K((S(K(S(KS)K)))((S(KS))K))))`
`λabcde.ab(cde)` `a => b => c => d => e => a(b)(c(d)(e))` `(a -> d -> e) -> a -> (b -> c -> d) -> b -> c -> e` 5
F Finch `ETTET`
`((S(K((S((SK)K))(K((S(K(S((SK)K))))K)))))((S(K((S(K(S(KS)K)))((S(KS))K))))((S(K(S((SK)K))))K)))`
`λabc.cba` `a => b => c => c(b)(a)` `a -> b -> (b -> a -> c) -> c` 3
G Goldfinch `BBC`
`((S(K(S(KS)K)))((S((S(K(S(KS)K)))S))(KK)))`
`λabcd.ad(bc)` `a => b => c => d => a(d)(b(c))` `(a -> b -> c) -> (d -> b) -> d -> a -> c` 4
H Hummingbird `BW(BC)`
`((S(K((S(K(S((S(K((S((SK)K))((SK)K))))((S(K(S(KS)K)))((S(K(S((SK)K))))K))))))K)))(S(K((S((S(K(S(KS)K)))S))(KK)))))`
`λabc.abcb` `a => b => c => a(b)(c)(b)` `(a -> b -> a -> c) -> a -> b -> c` 3
I Idiot `SKK`
`((SK)K)`
`id` `λa.a` `a => a` `a -> a` 1
J Jay `B(BC)(W(BC(E)))`
`((S(K(S(K((S((S(K(S(KS)K)))S))(KK))))))((S((S(K((S((SK)K))((SK)K))))((S(K(S(KS)K)))((S(K(S((SK)K))))K))))(K((S(K((S((S(K(S(KS)K)))S))(KK))))(S(K((S(K(S(KS)K)))((S(KS))K))))))))`
`λabcd.ab(adc)` `a => b => c => d => a(b)(a(d)(c))` `(a -> b -> b) -> a -> b -> a -> b` 4
K Kestrel `K`
`K`
`const` `λab.a` `a => b => a` `a -> b -> a` 2
Ki Kite `KI`
`(K((SK)K))`
`λab.b` `a => b => b` `a -> b -> b` 2
L Lark `CBM`
`((S((S(KS))K))(K((S((SK)K))((SK)K))))`
`λab.a(bb)` `a => b => a(b(b))` 2
M Mockingbird `SII`
`((S((SK)K))((SK)K))`
`λa.aa` `a => a(a)` 1
O Owl `SI`
`(S((SK)K))`
`λab.b(ab)` `a => b => b(a(b))` `((a -> b) -> a) -> (a -> b) -> b` 2
Omega Ω `MM`
`(((S((SK)K))((SK)K))((S((SK)K))((SK)K)))`
`λa.(aa)(aa)` `a => (a(a))(a(a))` 1
Phoenix `λabcd.a(bd)(cd)` `a => b => c => d => a(b(d))(c(d))` `(a -> b -> c) -> (d -> a) -> (d -> b) -> d -> c` 4
Psi `on` `λabcd.a(bc)(bd)` `a => b => c => d => a(b(c))(b(d))` `(a -> a -> b) -> (c -> a) -> c -> c -> b` 4
Q Queer `CB`
`((S(K(S((S(KS))K))))K)`
`(##)` `λabc.b(ac)` `a => b => c => b(a(c))` `(a -> b) -> (b -> c) -> a -> c` 3
R Robin `BBT`
`((S(K(S(KS)K)))((S(K(S((SK)K))))K))`
`λabc.bca` `a => b => c => b(c)(a)` `a -> (b -> a -> c) -> b -> c` 3
S Starling `S`
`S`
`<*>` `λabc.ac(bc)` `a => b => c => a(c)(b(c))` `(a -> b -> c) -> (a -> b) -> a -> c` 3
S_ `<*>` `λabc.a(bc)c` `a => b => c => a(b(c))(c)` `(a -> b -> c) -> (b -> a) -> b -> c` 3
S2 `<*>` `λabcd.a((bd)(cd))` `a => b => c => d => a(b(d))(c(d))` `(b -> c -> d) -> (a -> b) -> (a -> c) -> a -> d` 4
T Thrush `CI`
`((S(K(S((SK)K))))K)`
`(&)` `λab.ba` `a => b => b(a)` `a -> (a -> b) -> b` 2
U Turing `LO`
`((S(K(S((SK)K))))((S((SK)K))((SK)K)))`
`λab.b(aab)` `a => b => b(a(a)(b))` 2
V Vireo `BCT`
`((S(K((S((S(K(S(KS)K)))S))(KK))))((S(K(S((SK)K))))K))`
`λabc.cab` `a => b => c => c(a)(b)` `a -> b -> (a -> b -> c) -> c` 3
W Warbler `C(BMR)`
`((S(K(S((S(K((S((SK)K))((SK)K))))((S(K(S(KS)K)))((S(K(S((SK)K))))K))))))K)`
`λab.abb` `a => b => a(b)(b)` `(a -> a -> b) -> a -> b` 2
Y Y-Fixed point `λa.(λb(a(bb))(λb(a(bb))))` `a => (b => b(b))(b => a(c => b(b)(c)))` 1
Z Z-Fixed point `λa.M(λb(a(Mb)))` 1

## Usage

### Simple combinators

```<?php

declare(strict_types=1);

include 'vendor/autoload.php';

use loophp\combinator\Combinators;

// Lambda calculus: I combinator correspond to λa.a
Combinators::I()('a'); // a

// Lambda calculus: K combinator correspond to λa.λb.a (or λab.a)
Combinators::K()('a')('b'); // a

// Lambda calculus: C combinator correspond to λf(λa(λb(fba)))
// and thus: C K a b = b
Combinators::C()(Combinators::K())('a')('b'); // b

// Lambda calculus: Ki combinator correspond to λa.λb.b (or λab.b)
Combinators::Ki()('a')('b'); // b```

### Y combinator

```<?php

declare(strict_types=1);

namespace Test;

include __DIR__ . '/vendor/autoload.php';

use Closure;
use loophp\combinator\Combinators;

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

\$factorial = Combinators::Y()(\$factorialGenerator);

var_dump(\$factorial(6)); // 720

// Example 2
\$fibonacciGenerator = static fn (Closure \$fibo): Closure =>
static fn (int \$number): int => (1 >= \$number) ? \$number : \$fibo(\$number - 1) + \$fibo(\$number - 2);

\$fibonacci = Combinators::Y()(\$fibonacciGenerator);

var_dump(\$fibonacci(10)); // 55```

More on the wikipedia page.

## 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.

## Changelog

See CHANGELOG.md for a changelog based on git commits.

For more detailed changelogs, please check the release changelogs.

## About

A curated list of combinators

2.0.2 Latest
Aug 4, 2021

## Packages 0

No packages published