In my current work, the main stream platform is .NET. I have not invested a lot of time to start to program in C# for .NET, but I am kind of attracted by F#, which is a functional language for .NET that I would like to know more about.
Recently, I purchased a book to know more about F# and I learn some thing that is called “Y-combinator” in functional programming. The F# code for the “Y-combinator” looks like this,
let rec y f x = f (y f) x;;
You can apply the “Y-combinator” to some non-recursive functional function to make it recursive. For example,
let fac f = function | 0 -> 1 | n -> n * f (n-1);; > y fac 5;; val it : int = 120
I was curious about how to do similar thing in Python. So, I try the following code snippet:
def Y(f):
def g(x):
return f(Y(f))(x)
return g
def fac(f):
def g(x):
return 1 if x == 0 else x * f(x-1)
return g
With these function definitions, “Y(fac)(10)” will give you the correct result 3628800. On the other hand, it is not really easy for me to understand this code as most of my daily programming tasks are in imperative programming style with some more straight forward functional feature. Beside the mathematical way (described in the wiki page) to understand how this work, one way one can see how this work is to see how the code unroll under python interpreter:
Y(fac)(5) -> fac(Y(fac))(5) -> g(5) inside fac with f = Y(fac)
Then the “g(5)” inside fac returns 5 * Y(fac)(4) . The Y(fac)(4) will return 4 * Y(fac)(3) and so on.
It seems there is a lot interesting thing in pure functional world. Hope I will learn more about them soon.
