Skip to content

Latest commit

 

History

History
183 lines (155 loc) · 6.92 KB

README.md

File metadata and controls

183 lines (155 loc) · 6.92 KB
Raw

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:

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