Non-recursive Factorial implementation using U/Y/Z combinators

factorial-uyz-combinator.mjs

// U-combinator
const U  = f => f(f)
const Uz = f => v => f(f)(v) // like U, but for eager/non-lazy languages
                            // (stops infinite expansion caused by eager evaluation)

// Y/Z-combinator
const Y = g => (f => g(      f(f)    )) (f => g(      f(f)    )) // or g => U( f => g(  U(f) ) )
const Z = g => (f => g( v => f(f)(v) )) (f => g( v => f(f)(v) )) // or g => U( f => g( Uz(f) ) )
// properties:
// Y g = g(Y g) = g(g(Y g)) = g(...g(Y g)...)
// Z g v = g(Z g) v

const factR =      n => n === 0 ? 1 : n * factR(n - 1) // recursive, function references and calls itself
const g_    = f => n => n === 0 ? 1 : n *  U(f)(n - 1) // non-recursive (U-combinator)
const g     = f => n => n === 0 ? 1 : n *     f(n - 1) // non-recursive (Y/Z-combinator)

const factU = U(g_)
// const factY = Y(g) // call stack overflow (programming language limitation, eager evaluation -> infinite expansion)
const factZ = Z(g)

const testFacts = (n) => ({
  [`factR(${n})`]: factR(n),
  [`factU(${n})`]: factU(n),
  // [`factY(${n})`]: factY(n),
  [`factZ(${n})`]: factZ(n),
})

function main() {
  console.table(testFacts(4))
}

main()
/**
┌──────────┬────────┐
│ (index)  │ Values │
├──────────┼────────┤
│ factR(4) │   24   │
│ factU(4) │   24   │
│ factZ(4) │   24   │
└──────────┴────────┘
 */