4 ms·
Here's what the factorial function on Church numerals ends up looking like if you expand it out: ((λ (f) ((λ (g) (g g)) (λ (h) (λ (x) ((f (h h)) x)))))
by lisper 13y ago
Here's what the factorial function on Church numerals ends up looking like if you expand it out:
((λ (f) ((λ (g) (g g)) (λ (h) (λ (x) ((f (h h)) x)))))
(λ (f)
(λ (n)
(if ((λ (p a b) (p a b)) ((λ (n) (n (λ (x) (λ (x y) y)) (λ (x y) x))) n) t nil)
((λ (n) (λ (f x) (f (n f x)))) (λ (f x) x))
((λ (m n) (m ((λ (m n) (λ (f x) (m f (n f x)))) n) (λ (f x) x)))
n (f ((λ (n) (λ (f x) (n (λ (g h) (h (g f))) (λ (u) x) (λ (u) u)))) n)))))))
Note the use of the Y combinator to implement recursion :-)
Here it is in action computing the factorial of 6:
? (((λ (f) ((λ (g) (g g)) (λ (h) (λ (x) ((f (h h)) x)))))
(λ (f)
(λ (n)
(if ((λ (p a b) (p a b)) ((λ (n) (n (λ (x) (λ (x y) y)) (λ (x y) x))) n) t nil)
((λ (n) (λ (f x) (f (n f x)))) (λ (f x) x))
((λ (m n) (m ((λ (m n) (λ (f x) (m f (n f x)))) n) (λ (f x) x)))
n (f ((λ (n) (λ (f x) (n (λ (g h) (h (g f))) (λ (u) x) (λ (u) u)))) n)))))))
((λ (n) (λ (f x) (f (n f x))))
((λ (n) (λ (f x) (f (n f x))))
((λ (n) (λ (f x) (f (n f x))))
((λ (n) (λ (f x) (f (n f x))))
((λ (n) (λ (f x) (f (n f x))))
((λ (n) (λ (f x) (f (n f x))))
(λ (f x) x))))))))
#<COMPILED-LEXICAL-CLOSURE #x30200105130F>
? (funcall * '1+ 0)
720
- tromp 13y agoChurch factorial can be implemented without recursion though. Hint: consider a function that maps the pair <n,n!> to <(n+1),(n+1)!> ...
- tromp 13y agoHere is Church factorial in graphical notation: ┬────────────────────── │ ┬────────────── ─ ┬ ┬ │ ┼─┬───────┬──── ┬ │ │ │ ┼─┼───────┼─┬── │ │ │ │ │ ┼─┬─┬── ┼─┼─┬ │ │ │ │ │ ┼─┼─┼─┬ │ ├─┘ │ │ │ │ │ └─┤ ├─┘ ├─┘ │ │ │ │ │ ├─┘ │ │ │ │ │ └───┤ │ │ │ │ │ ├─────┘ │ │ │ └─────┤ │ │ │ └───────────┤ │ │ └─┤ │ └─┘
- lisper 13y agoThat's pretty cool looking, but I have no idea what I'm looking at. Does this notation have a name? Is it documented somewhere? (Hm, I wonder how hard it would be to write a parser for it. :-)
- tromp 13y agoThat's my graphical notation for lambda calculus, documented at http://www.cwi.nl/~tromp/cl/diagrams.html http://www.cwi.nl/~tromp/cl/diagrams.html Btw, here's an even shorter version of factorial: ┬──────────────── ┼─────────────┬── │ ──┬──────── ┼ ┬ │ ┬─┼─┬────── │ │ │ │ │ ┼─┬─┬── │ │ │ │ │ ┼─┼─┼─┬ │ │ │ │ │ └─┤ ├─┘ │ │ │ │ │ ├─┘ │ │ │ │ ├───┘ │ │ │ ├─┘ │ │ └─┤ │ │ └───────────┤ │ └─┘ In de-Bruijn notation it is \\2 (\\1 (2 (\\3 2 (2 1)))) (\2) (\1), which in conventional notation is \n\f.n (\x\m.m (x (\a\b.m a (a b)))) (\x.f) (\x.x)
- lisper 13y agoWhether the loop is recursive or iterative you still need a loop, so you still need a Y combinator.