Combinator

Published: 1/18/2020
Last edited: 1/26/2020

A combinator is a primitive higher-order function without free-variables.

// identity combinator
const I = x => x
// constant combinator
const K = x => () => x
// apply combinator
const A = f => x => f(x)
// thrush combinator
const T = x => f => f(x) 
// duplication combinator
const W = f => x => f(x)(x)
// flip combinator
const C = f => y => x => f(x)(y) 
// compose combinator
const B = f => g => x => f(g(x))
// amalgamation combinator
const S = f => g => x => f(x)(g(x))
// psi combinator
const P = f => g => x => y => f(g(x))(g(y))
// fixed-point Y combinator
const Y = f => (g => g(g))(g => f(x => g(g)(x))) 

// morphisms
S(K)(K) === I
C(A) === T
W(T)(I) === I
C(W(K)(T)) === A
S(K)(A) === A

Often if you can identify combinators in your code, you can use them to simplify logical parts of the code because of a knowledge of certain morphisms.

Read much more on wikipedia. (The above definitions provided by this gist.)

(A common reference is To Mock A Mockingbird but your mileage may vary.)

There's a lot more to read about but one of the reasons it's cool is that using just S and K above, you can define a Turing complete language.

Published: 1/18/2020
Last edited: 1/26/2020
See this page on Github
Built with ๐Ÿ’› by Open Sorcerers
Created with Gatsby using the ๐Ÿ˜Ž foresight starter