Skip to content

Instantly share code, notes, and snippets.

@mudroljub
Forked from lupuszr/combinators.js
Last active May 10, 2019 14:52
Show Gist options
  • Save mudroljub/b7e7b0207ac81aee1dd27aabe488399c to your computer and use it in GitHub Desktop.
Save mudroljub/b7e7b0207ac81aee1dd27aabe488399c to your computer and use it in GitHub Desktop.
Common combinators in JavaScript
// list of combinators http://www.angelfire.com/tx4/cus/combinator/birds.html
const I = x => x;
const K = x => y => x; // T
const A = f => x => f(x);
const T = x => f => f(x);
const W = f => x => f(x)(x);
const C = f => y => x => f(x)(y);
const B = f => g => x => f(g(x));
const S = f => g => x => f(x)(g(x));
const P = f => g => x => y => f(g(x))(g(y));
const Y = f => (g => g(g))(g => f(x => g(g)(x)));
// Boolean
const T = a => b => a // K
const F = a => b => b // KI
const not = p => p(F)(T)
// usage
not(T)
not(F)
// Numbers (Church encoding)
const zero = f => a => a // KI
const once = f => a => f(a) // I
const twice = f => a => f(f(a))
const thrice = f => a => f(f(f(a)))
succ = n => f => a => f(n(f)(a))
// usage
twice(not)(F)
thrice(not)(T)
// birds
const B = f => g => a => f(g(a)) // blue bird (compose function)
// usage
B(not)(not)(T) // from right to left
Name # Haskell Ramda Sanctuary Signature
identity I id identity I a → a
constant K const always K a → b → a
apply¹ A ($) call (a → b) → a → b
thrush T (&) applyTo T a → (a → b) → b
duplication W join² unnest² join² (a → a → b) → a → b
flip C flip flip flip (a → b → c) → b → a → c
compose B (.), fmap² map² compose, map² (b → c) → (a → b) → a → c
substitution S ap² ap² ap² (a → b → c) → (a → b) → a → c
psi P on on (b → b → c) → (a → b) → a → a → c
fix-point³ Y fix (a → a) → a

¹) The A-combinator can be implemented as an alias of the I-combinator. Its implementation in Haskell exists because the infix nature gives it some utility. Its implementation in Ramda exists because it is overloaded with additional functionality.

²) Algebras like ap have different implementations for different types. They work like Function combinators only for Function inputs.

³) In JavaScript and other non-lazy languages, it is impossible to implement the Y-combinator. Instead a variant known as the applicative or strict fix-point combinator is implemented. This variant is sometimes rererred to as the Z-combinator.

Note that when I use the word "combinator" in this context, it implies "function combinator in the untyped lambda calculus".

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment