javascript - Is this an implementation of a fixpoint combinator? -

i presumed couldn't called "fixed point recursion" because straightforward. however, realized might be.

have implemented fixed point recursion?

here's function in question:

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

here's additional context:

// 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 code here, snippet above should enough follow.

the definition of fixed-point combinator function f takes function f , returns function p such that

given f(f) = p p = f(p)

there many possible fixed point combinators written. don't let straightforwardness make think isn't fixed-point combinator; here standard definition in javascript, simple:

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

a usage might compute fixed-point factorial, with:

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

for example of different fixed point combinator (the y combinator) see this helpful blog post.

let's see if until combinator computes fixed-points. since working monadic functions fixed-point definition changes handle monadic structure, f (monadic) fixed-point combinator when

given f(f) = p p = f* . p

where f* . p means kleisli composition of function p function f (in code write kleisli(p, f), can think of * bind). i'll use notation shorter writing javascript.

let's unroll definition of until , see get:

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

does p = f* . p?

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

yes- believe so. although don't think useful fixed point. (i'm afraid don't have argument yet- think greatest-fixed point diverge).

to me, looks arguments kleisli in until should have been swapped. is, wish kleisli equivalent of application in fix example, need pass monadic result of recursive call until(f) f:

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

let's unroll new definition of until:

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

does p = f* . p? yes does:

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

since adding 1 more composition of f* onto infinite chain of f* composition same function.

using kleisli function had problems divergence (some evaluation happening computation runs until run out of stack space). instead, following seems work me:

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

for more on fixed-points monadic code might check out the work of erkök , launchbury.