As you know the Fixed Point Combinator, or Y-Combinator, allows to implement recursive functions without using recursive calls, and maybe you are asking yourself what kind of magic is this. The Fixed Point Combinator can be easily implemented on any language with functional features with a consistent anonymous function implementation. The concept comes from Lambda Calculus, a formal system created by the mathematician Alonzo Church, to study functions, and also it allows the representation of computations. The Fixed Point Combinator, as any combinator used to compose functions, creates a composite function that is called recursively without doing recursive calls using an anonymous function to create the recursive call instance.
The Y-Combinator is expressed in Lambda Calculus as λg.(λx.g(x x))(λx.g(x x)), and once you apply that combinator on a function, compositing a new function, you have a pseudo-recursive construct that creates a new function using anonymous functions to make the recursive call, rather than doing the recursive call with the function name. For example if we apply the Y-Combinator to the identity combinator λx.x, we have a sequential reduction as follows.
- (λg . (λx . g (x x)) (λx . g (x x))) (λm.m)
- (λx . (λm.m) (x x)) (λx . (λm.m) (x x))
- (λm.m) ((λx . (λm.m) (x x)) (λx . (λm.m) (x x)))
- (λm.m) ( ((λg . (λx . g (x x)) (λx . g (x x)))) (λm.m)) { equal to (λm.m) (Y (λm.m)) }
The same approach can be implemented in any programming language that implements anonymous functions or lambda expressions properly, like JavaScript or Coffee Script — which compiles to JavaScript. So you can derive that combinator in that language, as you can do it in Lisp and Haskell, because JavaScript implements that functional feature without obstacles. In other languages like C Plus Plus 11x you cannot implement the Y-Combinator due to its anonymous function implementation, because it seems that does not allow anonymous function nesting and treating anonymous functions as first order citizens.
Y = (h) -> ((f) ->
f f) (f) ->
h (n) ->
f(f) n
fact = Y((g) ->
(n) ->
return 1 if n < 2
n * g(n - 1)
)
console.log (fact 5)
As exercise, trace the function calls and anonymous function declarations and compare it to the Lambda Calculus expression and trace. You will find the recursion on the nested anonymous functions rather than finding the recursive call in a language literal like a function name. Despite its theoretical background, this combinator can be used with other libraries, like Katy, to traverse node trees and apply transformations, and your code will probably look a little bit monadic, but still will be based in combinators.
Entries 