loophp/combinator

A curated list of combinators

Fund package maintenance!
drupol
Paypal

2.0.2 2021-08-04 20:13 UTC

This package is auto-updated.

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


README

Latest Stable Version GitHub stars Total Downloads GitHub Workflow Status Scrutinizer code quality Type Coverage Code Coverage License Donate! Donate!

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.

Requirements

  • 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);

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.

Suggested reading and resources

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.

Thanks

Authors

Changelog

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

For more detailed changelogs, please check the release changelogs.