🐦 Some combinators
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.gitignore
.nvmrc
.travis.yml egassem timmoc commit message Feb 21, 2018
CHANGELOG.md add a bunch more combinators Dec 12, 2015
README.md docs(readme): Tweak See Also section Feb 21, 2018
index.es6.js
index.js
package.json opaque commit message Feb 21, 2018
test.js mythical commit message Feb 21, 2018

README.md

combinators-js

npm version Build Status

Getting Started

Install (other package managers are available):

npm i -S combinators-js

Import (other module systems are available):

import {
  B, B1, B2, B3, C, C_, C__, D, D1, D2, E, F, F_, F__ G, H, I, I_, I__, J, K, L,
  M, M2, O, Q, Q1, Q2, Q3, Q4, R, R_, R__, S, T, U, V, V_, V__, W, W_, W__, W1, Y,
} from 'combinators-js'

Definitions

Here are the included combinators with their definitions (they are compiled to standard functions so will run in any JS evironmment):

const B = a => b => c => a(b(c))
const B1 = a => b => c => d => a(b(c)(d))
const B2 = a => b => c => d => e => a(b(c)(d)(e))
const B3 = a => b => c => d => a(b(c(d)))
const C = a => b => c => a(c)(b)
const C_ = a => b => c => d => a(b)(d)(c)
const C__ = a => b => c => d => e => a(b)(c)(e)(d)
const D = a => b => c => d => a(b)(c(d))
const D1 = a => b => c => d => e => a(b)(c)(d(e))
const D2 = a => b => c => d => e => a(b(c))(d(e))
const E = a => b => c => d => e => a(b)(c(d)(e))
const F = a => b => c => c(b)(a)
const F_ = a => b => c => d => a(d)(c)(b)
const F__ = a => b => c => d => e => a(b)(e)(d)(c)
const G = a => b => c => d => a(d)(b(c))
const H = a => b => c => a(b)(c)(b)
const I = a => a
const I_ = a => b => a(b)
const I__ = a => b => c => a(b)(c)
const J = a => b => c => d => a(b)(a(d)(c))
const K = a => b => a
const L = a => b => a(b(b))
const M = a => a(a)
const M2 = a => b => a(b)(a(b))
const O = a => b => b(a(b))
const Q = a => b => c => b(a(c))
const Q1 = a => b => c => a(c(b))
const Q2 = a => b => c => b(c(a))
const Q3 = a => b => c => c(a(b))
const Q4 = a => b => c => c(b(a))
const R = a => b => c => b(c)(a)
const R_ = a => b => c => d => a(c)(d)(b)
const R__ = a => b => c => d => e => a(b)(d)(e)(c)
const S = a => b => c => a(c)(b(c))
const T = a => b => b(a)
const U = a => b => b(a(a)(b))
const V = a => b => c => c(a)(b)
const V_ = a => b => c => d => a(c)(b)(d)
const V__ = a => b => c => d => e => a(b)(e)(c)(d)
const W = a => b => a(b)(b)
const W_ = a => b => c => a(b)(c)(c)
const W__ = a => b => c => d => a(b)(c)(d)(d)
const W1 = a => b => b(a)(a)
const Y = a => (b => b(b))(b => a(c => b(b)(c)))

Tests

test('B')(S(K(S))(K))
test('B1')(S(K(S(K(S))(K)))(S(K(S))(K)))
test('B2')(S(K(S(K(S(K(S))(K)))(S(K(S))(K))))(S(K(S))(K)))
test('C')(S(S(K(S(K(S))(K)))(S))(K(K)))
test('C_')(S(K(S(S(K(S(K(S))(K)))(S))(K(K)))))
test('C__')(S(K(S(K(S(S(K(S(K(S))(K)))(S))(K(K)))))))
test('D')(S(K(S(K(S))(K))))
test('D1')(S(K(S(K(S(K(S))(K))))))
test('D2')(S(K(S(K(S))(K)))(S(K(S(K(S))(K)))))
test('E')(S(K(S(K(S(K(S))(K)))(S(K(S))(K)))))
test('F')(S(K(S(S(K)(K))(K(S(K(S(S(K)(K))))(K)))))(S(K(S(K(S(K(S))(K)))(S(K(S))(K))))(S(K(S(S(K)(K))))(K))))
test('F_')(S(K(S(K(S(S(K(S(K(S))(K)))(S))(K(K))))))(S(K(S(S(K(S(K(S))(K)))(S))(K(K))))(S(K(S(S(K(S(K(S))(K)))(S))(K(K)))))))
test('F__')(S(K(S(K(S(K(S(S(K(S(K(S))(K)))(S))(K(K))))))(S(K(S(S(K(S(K(S))(K)))(S))(K(K))))(S(K(S(S(K(S(K(S))(K)))(S))(K(K)))))))))
test('G')(S(K(S(K(S))(K)))(S(S(K(S(K(S))(K)))(S))(K(K))))
test('H')(S(K(S(K(S(S(K(S(S(K)(K))(S(K)(K))))(S(K(S(K(S))(K)))(S(K(S(S(K)(K))))(K))))))(K)))(S(K(S(S(K(S(K(S))(K)))(S))(K(K))))))
test('I')(S(K)(K))
test('I_')(S(S(K)))
test('J')(S(K(S(K(S(S(K(S(K(S))(K)))(S))(K(K))))))(S(S(K(S(S(K)(K))(S(K)(K))))(S(K(S(K(S))(K)))(S(K(S(S(K)(K))))(K))))(K(S(K(S(S(K(S(K(S))(K)))(S))(K(K))))(S(K(S(K(S(K(S))(K)))(S(K(S))(K)))))))))
test('K')(K)
test('L')(S(S(K(S))(K))(K(S(S(K)(K))(S(K)(K)))))
test('M')(S(S(K)(K))(S(K)(K)))
test('M2')(S(K(S(S(K)(K))(S(K)(K)))))
test('O')(S(S(K)(K)))
test('Q')(S(K(S(S(K(S))(K))))(K))
test('Q1')(S(K(S(S(K(S(K(S))(K)))(S))(K(K))))(S(K(S))(K)))
test('Q2')(S(K(S(S(K(S(S(K(S(K(S))(K)))(S))(K(K))))(S(K(S))(K)))))(K))
test('Q3')(S(K(S(K(S(S(K)(K))))(K))))
test('Q4')(S(K(S(S(K(S(K(S))(K)))(S))(K(K))))(S(K(S(S(K(S(S(K(S(K(S))(K)))(S))(K(K))))(S(K(S))(K)))))(K)))
test('R')(S(K(S(K(S))(K)))(S(K(S(S(K)(K))))(K)))
test('R_')(S(K(S(S(K(S(K(S))(K)))(S))(K(K))))(S(K(S(S(K(S(K(S))(K)))(S))(K(K))))))
test('R__')(S(K(S(K(S(S(K(S(K(S))(K)))(S))(K(K))))(S(K(S(S(K(S(K(S))(K)))(S))(K(K))))))))
test('S')(S)
test('T')(S(K(S(S(K)(K))))(K))
test('U')(S(K(S(S(K)(K))))(S(S(K)(K))(S(K)(K))))
test('V')(S(K(S(S(K(S(K(S))(K)))(S))(K(K))))(S(K(S(S(K)(K))))(K)))
test('V_')(S(K(S(K(S(S(K(S(K(S))(K)))(S))(K(K))))(S(K(S(K(S(S(K(S(K(S))(K)))(S))(K(K))))))(S(K(S(S(K(S(K(S))(K)))(S))(K(K))))(S(K(S(S(K(S(K(S))(K)))(S))(K(K))))))))))
test('W')(S(K(S(S(K(S(S(K)(K))(S(K)(K))))(S(K(S(K(S))(K)))(S(K(S(S(K)(K))))(K))))))(K))
test('W_')(S(K(S(K(S(S(K(S(S(K)(K))(S(K)(K))))(S(K(S(K(S))(K)))(S(K(S(S(K)(K))))(K))))))(K))))
test('W__')(S(K(S(K(S(K(S(S(K(S(S(K)(K))(S(K)(K))))(S(K(S(K(S))(K)))(S(K(S(S(K)(K))))(K))))))(K))))))
test('W1')(S(K(S(S(K(S(S(K(S(S(K)(K))(S(K)(K))))(S(K(S(K(S))(K)))(S(K(S(S(K)(K))))(K))))))(K))))(K))

Ideas

// LISP data structures
const KI = K(I)
const cons = (a, b) => V(a)(b) // manual uncurry
const car = T(K)
const cdr = T(KI)

console.log(car(cons(0, 1))) // => 0
console.log(cdr(cons(0, 1))) // => 1

const nil = () => {}
const list = (...args) => args.reduce((l, arg) => V(arg)(l), nil)
const reverse = (l, m = nil) => l === nil ? m : reverse(l(KI), V(l(K))(m))
const reduce = f => l => m => l(KI) === undefined ? m : f(reduce(f)(l(KI))(m))(l(K))
const map = f => l => reduce(acc => val => V(f(val))(acc))(l)(nil)
const length = l => reduce(acc => val => 1 + acc)(l)(0)
const filter = f => l => reduce(acc => val => f(val) ? V(val)(acc) : acc)(l)(nil)

const arbitraryList = list(0, 1, 2, 3, 4, 5)

console.log(length(arbitraryList)) // => 6

const reduced = reduce(acc => val => V(val)(acc))(arbitraryList)(nil)
const filtered = filter(x => x > 2)(reduced)
const mapped = map(x => x ** 2)(filtered)
const reversed = reverse(mapped)

console.log(length(reversed)) // => 3
map(::console.log)(reversed) // => 25 16 9
// recursion of anonymous functions
Y(recur => x => x === 1 ? 1 : x * recur(x - 1))(5) // => 120

// TCO'd recursion of anonymous functions using a modified Y
// taking a variadic non-combinator function
const Y_ = a => (b => a((...c) => b(b)(...c)))(b => a((...c) => b(b)(...c)))
Y_(recur => (x, y = 1) => x === 1 ? y : recur(x - 1, x * y))(5) // => 120
// omega bird (mock a mockingbird)
M(M)

Practical Ideas

See Also

I built a Church encoding library too.

Further Reading