lambda_calc.ts

/** Identity */
const I = x => x

/** self apply */
const S = s => s(s)

// Church Numerals
const churchZero = f => I
const nextChurch = n => f => x => f(n(f)(x))
const churchToInt = c => c(x => x + 1)(0)
const intToChurch = n =>
  n === 0 ? churchZero : nextChurch(intToChurch(n - 1))
console.log(churchToInt(intToChurch(5)) === 5)

/** fibanauci lamba expression */
const fible = f => x => (x <= 1 ? x : f(x - 1) + f(x - 2))

/** Y combinator */
const Y = le => S(f => le(x => f(f)(x)))

/** fibanauci implemented with Y combinator */
const fibY = Y(fible)

/** memoized Y combinator */
const Ym = le =>
  S(f =>
    le(x =>
      (key => (key in f ? f[key] : (f[key] = f(f)(x))))(JSON.stringify(x))
    )
  )

/** fibanauci implemented with memoized Y combinator */
const fibYm = Ym(fible)