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

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

• To Mock a Mockingbird
• http://dkeenan.com/Lambda/
• https://gist.github.com/Avaq/1f0636ec5c8d6aed2e45
• https://en.wikipedia.org/wiki/Combinatory_logic
• https://github.com/sanctuary-js/sanctuary
• https://en.wikipedia.org/wiki/Lambda_calculus
• https://hackage.haskell.org/package/data-aviary-0.4.0/docs/src/Data-Aviary-BirdsInter.html
• https://github.com/fantasyland/fantasy-birds/blob/master/README.md
• https://www.cis.upenn.edu/~bcpierce/tapl/
• https://plato.stanford.edu/entries/lambda-calculus/
• https://github.com/glebec/lambda-talk
• https://www.youtube.com/watch?v=seVSlKazsNk

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
• Danny Willems

Authors

• Pol Dellaiera

Changelog

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

For more detailed changelogs, please check the release changelogs.