## loophp /combinator

A curated list of combinators

##### Details

Source

Issues

Fund package maintenance!
drupol
Paypal

1 137

0

39

8

1

2.0.2 2021-08-04 20:13 UTC

This package is auto-updated.

Last update: 2021-10-04 20:38:20 UTC

# 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 Haskel 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 Trush `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);

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;

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```

## Contributing

Feel free to contribute by sending Github pull requests. I'm quite responsive :-)

If you can't contribute to the code, you can also sponsor me on Github or Paypal.

## Changelog

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

For more detailed changelogs, please check the release changelogs.