Church encoding

church.spec.js

const c = {
  and:   a => b => a(b)(c.false),
  exp:   m => n => n(m),
  false: a => b => b,
  isEQ:  m => n => c.and(c.isLE(m)(n))(c.isLE(n)(m)),
  isLE:  m => n => c.isZ(c.sub(m)(n)),
  isZ:   n => n(x => c.false)(c.true),
  mult:  m => n => f => m(n(f)),
  plus:  m => n => f => x => m(f)(n(f)(x)),
  pred:  n => f => x => n(g => h => h(g(f)))(u => x)(u => u),
  sub:   m => n => n(c.pred)(m),
  succ:  n => f => x => f(n(f)(x)),
  true:  a => b => a,

  encodeInt: n => {
    if (n <= 0) return f => a => a
    return c.succ(c.encodeInt(n - 1))
  },

  decodeInt: f => {
    const inc = a => {
      return a + 1
    }
    return f(inc)(0)
  },

  decodeBool: f => {
    return f(true)(false)
  },
}

describe('foo', () => {
  it('subtracts', () => {
    const x = c.encodeInt(9),
      y = c.encodeInt(5),
      z = c.sub(x)(y)
    expect(c.decodeInt(z)).toEqual(4)
  })

  it('predecessor', () => {
    const x = c.encodeInt(10),
      z = c.pred(x)
    expect(c.decodeInt(z)).toEqual(9)
  })

  it('exponents', () => {
    const x = c.encodeInt(3),
      y = c.encodeInt(3),
      z = c.exp(x)(y)
    expect(c.decodeInt(z)).toEqual(27)
  })

  it('multiplies', () => {
    const x = c.encodeInt(3),
      y = c.encodeInt(5),
      z = c.mult(x)(y)
    expect(c.decodeInt(z)).toEqual(15)
  })

  it('detects zero', () => {
    const x = c.encodeInt(0),
      y = c.encodeInt(10),
      t = c.isZ(x),
      f = c.isZ(y)
    expect(c.decodeBool(t)).toBe(true)
    expect(c.decodeBool(f)).toBe(false)
  })

  it('compares with <=', () => {
    const x = c.encodeInt(5),
      y = c.encodeInt(10),
      t = c.isLE(x)(y),
      f = c.isLE(y)(x)

    expect(c.decodeBool(t)).toBe(true)
    expect(c.decodeBool(f)).toBe(false)
  })

  it('compares with ==', () => {
    const x = c.encodeInt(5),
      y = c.encodeInt(10),
      z = c.encodeInt(10),
      t = c.isLE(z)(y),
      f = c.isLE(y)(x)

    expect(c.decodeBool(t)).toBe(true)
    expect(c.decodeBool(f)).toBe(false)
  })
})