Is this an implementation of a fixpoint combinator?

Question

I presumed this couldn't be called "fixed point recursion" because it was too straightforward. However, I recently realized it actually might be.

Have I effectively implemented fixed point recursion?

Here's the function in question:

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

Here's some additional context:

// The error monad's bind
var bind_ = function(f, m) { return m.m === Success ? f(m.a) : m; };

var bind = function(f, m) {
    return m !== undefined && m.m !== undefined && m.a !== 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 snippet above should be enough to follow.

Answer 1

The definition of a fixed-point combinator is a function F which 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 could be written. Don't let the straightforwardness make you think that something isn't a fixed-point combinator; here is a standard definition in JavaScript, which is very simple:

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

A usage might be then to compute the fixed-point for factorial, 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 a different fixed point combinator (the Y combinator) see this helpful blog post.

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

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

where f* . p means the Kleisli composition of the function p with the function f (in your code you would write this kleisli(p, f), you can think of * as bind). I'll use this notation as it is shorter than writing JavaScript.

Let's unroll the definition of until then 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 

Does p = f* . p?

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

Yes- I believe so. Although I don't think this is a useful fixed point. (I'm afraid I don't have a good argument for this yet- but I think this is basically a greatest-fixed point which will just diverge).

To me, it looks like the arguments to kleisli in until should have been swapped. That is, we wish to do the Kleisli equivalent of 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's unroll this new definition of until:

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

Does p = f* . p? Yes it does:

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

since adding one more composition of f* onto an infinite chain of f* composition is the same function.

Using your kleisli function I had some problems with divergence (some evaluation is happening too soon so the computation runs until I run out of stack space). Instead, the following seems to work for me:

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

For more on fixed-points for monadic code you might like to check out the work of Erkök and Launchbury.