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.
相关问题
- Why wrapping a function into a lambda potentially
- Generating powerset in one function, no explicit r
- Check if tie in count of lists using linq
- C# to VB - How do I convert this anonymous method
- applying a list to an entered function to check fo
相关文章
- Why doesn't C11 support lambda functions
- Is there something like the threading macro from C
- Learning F#: What books using other programming la
- Creating a list of functions using a loop in R
- Will java allow to use functional interfaces as me
- Detect if C++ lambda can be converted to function
- When to use interfaces, and when to use higher ord
- Functors in Ocaml
If by "without the use of recursion" you mean without general recursion and hence without fixpoints (or self applications), we can simply observe that the factorial function is primitive recursive (that is, iterative, in essence), and there is a very general and simple encoding of primitive recursion by means of iteration (provided by church numerals) and pairs. I will discuss the general case that is quite instructive. Let < M,N > be some encoding of pairs, and let fst and snd be the associated projections. For instance, you can define
Suppose to have a primitive recursive definition (without parameters, for the sake of simplicity)
where a and h have been already defined.
The general idea is to use an auxiliary function f', where
So, f'(0) = < 0, a>, and given the pair p = < x,f(x) > = f'(x), we build the next pair < x+1, f(x+1) > by computing the successor on the first component and applying h to the pair of arguments (that, taking advantage of our encoding of pairs, simply amounts to pass the continuation h as input to the pair p).
Summing up,
Finally, to compute f(n) we need to iterate n times the function next starting from < 0, a>, and then take the second component:
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
Now, we don't particularly care about
zero?
,mult
,dec
, or evenone
in this example; you can implement those on your own – we just want to remove the bolded, by-name recursion,The easiest way to do this is to apply a lambda to itself – meet the U combinator
Now, we can wrap our original expression in a lambda, and apply
U
But what do we put in place of
fact
??? – Recall thatf
is a reference to the outer lambda itself, so in order for that to be the same case in the next "iteration", we must applyf
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 ^_^Yes, yes, but the even more astute will notice that you can utilize the mirror (U) directly inside the lambda, too
expanded without U
We know how to expand the inner – we wrote it that way the first time
Now expand the outer U
does it work?
all church numerals represented as #N
demonstration in javascript
Go ahead and view the U combinator's power with your very own eyeballs !
And again as a pure lambda expression
mutual recursion
The above snippet demonstrates a very important property of this recursive process: it's mutually recursive. As you can see, there are actually two (albeit the same) functions driving the recursion; A calls B, B calls A – However in the case of the U combinator, there is only one function that gets applied to itself, so it does in fact enable direct recursion – the lambda does call itself using its parameter, not its name (lambdas don't have a name to call)
Y ?
Because I said so
the U combinator is a little cumbersome because it expects the user to "reflect" the function in order to recur – what if we could provide the outer lambda with a function that is the mirror itself?
I'm gonna show you the same definition again, but on two lines just so you can see the "mirrors" and their positions
So now, whenever you apply
Y
to any lambda (g), its parameter becomes the function to compute the lambda itself – changingfact
toexpanding Y
which is the definition you see there in wikipedia; just alpha-renamed
i just had a profound discovery
Deriving Y from U above, I saw something I've never seen before - a hidden B
One of the most beautiful things I've ever seen – and it works too; not that we should have any reason to think it wouldn't...
Haskellers
Have you ever seen Y expressed as?