Is this a fixed point combinator implementation?

Question

I assumed that this could not be called "fixed-point recursion" because it was too simple. However, I recently realized that this is really possible.

Did I really implement fixed-point recursion?

Here the function in question:

/* recursive kleisli fold */ var until = function(f) { return function(a) { return kleisli(f, until(f))(a); }; }; 

Here is another additional context:

 // The error monad bind var bind_ = function(f, m) { return mm === Success ? f(ma) : m; }; var bind = function(f, m) { return m !== undefined && mm !== undefined && ma !== undefined ? bind_(f, m) : m; }; var kleisli = function(f1, f2) { return function(a) { return bind(f2, f1(a)); }; }; 

The rest of the code is here , but the above snippet should be enough.

Answer 1

The definition of a fixed-point combinator is a function F that takes a function F and returns a function p such that

Given F(f) = p , then p = f(p)

There are many possible fixed-point combinators that can be written. Do not allow straightforwardness to make you think that something is not a fixed-point combinator; here is the standard definition in JavaScript, which is very simple:

  var fix = function(f) { return function(x) { return f(fix(f))(x) } }; 

Then fixed-point calculation for factorial can be used with:

 var fact = function(f) { return function(n) { return (n == 0) ? 1 : (n * f(n - 1)) } }; alert(fix(fact)(7)); // alerts us with 5040. 

For an example of another fixed-point combinator (Y combinator), see this useful blog post .

Let's see if your combinator until calculates fixed points. Since you are working with monadic functions, the definition of a fixed point changes slightly to handle a monadic structure, where F is a (monadic) fixed point combinator when

Given F(f) = p , then p = f* . p p = f* . p

where f* . p f* . p means Claysley composition of function p with function F (in your code you would specify this kleisli(p, f) , you can think of * as bind ). I will use this notation as it is shorter than spelling JavaScript.

Let me expand the definition of until and see what we get:

 until(f) = (until(f))* . f = (until(f)* . f)* . f = ((... . f)* . f)* . f = ... . f* . f* . f (associativity of bind for a monad: (g* . f)* = g* . f*) = p 

Is there p = f* . p p = f* . p ?

 ... . f* . f* . f =?= f* . ... . f* . f* . f 

Yes, I think so. Although I do not think this is a useful fixed point. (I'm afraid I have no good arguments in favor of this yet, but I think that this is, in fact, the biggest point that just diverges).

It seems to me that the kleisli arguments in until should be replaced. That is, we want to make the equivalent of the Kleisli application in the fix example, so we need to pass the monadic result of the recursive call until(f) to F :

  var until = function(f) { return function(a) { return kleisli(until(f), f)(a); }; }; 

Let expand this new definition until :

 until(f) = f* . until(f) = f* . (f* . until(f)) = f* . f* . ... = p 

Is there p = f* . p p = f* . p ? Yes it is:

 f* . f* ... = f* . (f* . f* . ...) 

since adding another composition f * to an endless chain f * of composition is the same function.

Using your kleisli function, I had some problems with the discrepancy (some evaluation happens too early, so the calculation is done until the stack space has ended). Instead, the following works for me:

  var until = function(f) { return function(a) { return bind(f,until(f)(a)); }; }; 

For more information on fixed points for monadic code, you might want to check out Erkök and Launchbury .