functional programming - non recursive lambda calculus factorial function

Question

How to write a factorial function without use of recursion using lambda calculus? Meaning just the math notation not implementation in any particular programming language.

Answer 1

i didn't say anything i didn't mean

By "without the use of recursion" you must mean "without a function calling itself by name"

Anyway, let's write factorial

fact := λn. zero? n one (mult n (fact (dec n)))

Now, we don't particularly care about zero?, mult, dec, or even one in this example; you can implement those on your own – we just want to remove the bolded, by-name recursion,

... fact (dec n)

The easiest way to do this is to apply a lambda to itself – meet the U combinator

U := λf. f f

Now, we can wrap our original expression in a lambda, and apply U

fact := U (λf. λn. zero? n one (mult n (??? (dec n))))

But what do we put in place of fact ??? – Recall that f is a reference to the outer lambda itself, so in order for that to be the same case in the next "iteration", we must apply f to itself, just as U did – in fact, you can think of U as a sort of mirror, and your function can reflect back into that mirror in order to recur; only this time, without using a name ^_^

fact := U (λf. λn. zero? n one (mult n (f f (dec n))))

Yes, yes, but the even more astute will notice that you can utilize the mirror (U) directly inside the lambda, too

fact := U (λf. λn. zero? n one (mult n (U f (dec n))))

---

expanded without U

We know how to expand the inner – we wrote it that way the first time

fact := U (λf. λn. zero? n one (mult n (f f (dec n))))

Now expand the outer U

fact := (λf. λn. zero? n one (mult n (f f (dec n)))) (λf. λn. zero? n one (mult n (f f (dec n))))

---

does it work?

all church numerals represented as #N

fact := U λf. λn. zero? n #1 (mult n (U f (dec n)))

fact #4

U (λf. λn. zero? n #1 (mult n (U f (dec n))) #4

(λf. f f) (λf. λn. zero? n #1 (mult n (U f (dec n))) #4

(λf. λn. zero? n #1 (mult n (U f (dec n))) (λf. λn. zero? n #1 (mult n (U f (dec n))) #4

(λn. zero? n #1 (mult n (U (λf. λn. zero? n #1 (mult n (U f (dec n))) (dec n))) #4

zero? #4 #1 (mult #4 (U (λf. λn. zero? n #1 (mult n (U f (dec n))) (dec #4)))

zero? #4 #1 (mult #4 (U (λf. λn. zero? n #1 (mult n (U f (dec n))) (dec #4)))

// (zero? #4); false; returns second argument
(mult #4 (U (λf. λn. zero? n #1 (mult n (U f (dec n))) (dec #4)))

// which is #4 * ...
(U (λf. λn. zero? n #1 (mult n (U f (dec n))) (dec #4))

// which is ...
(U (λf. λn. zero? n #1 (mult n (U f (dec n))) #3)

// which is equivalent to...
fact #3

// so ...
(mult #4 (fact #3))

// repeating this pattern ...
(mult #4 (mult #3 (fact #2))
(mult #4 (mult #3 (mult #2 (fact #1)))
(mult #4 (mult #3 (mult #2 (mult #1 (fact #0))))
(mult #4 (mult #3 (mult #2 (mult #1 #1))))
(mult #4 (mult #3 (mult #2 #1)))
(mult #4 (mult #3 #2))
(mult #4 #6)
#24

---

demonstration in javascript

Go ahead and view the U combinator's power with your very own eyeballs !

const U =
  f => f (f)
  
const fact =
  U (f => n =>
    n === 0 ? 1 : n * U (f) (n - 1))
    
console.log (fact (4)) // 24