Czy jest to implementacja kombinatora fixpoint?

Question

Podejrzewałem, że nie można tego nazwać "rekursją punktów stałych", ponieważ było to zbyt proste. Jednak niedawno zdałem sobie sprawę, że tak naprawdę może być.

Czy skutecznie wdrożyłem rekursję punktów stałych?

Oto funkcja w pytaniu:

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

Oto niektóre dodatkowy kontekst:

// 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)); 
    }; 
}; 

Reszta kodu jest here, ale urywek powyżej powinny być wystarczające do naśladowania.

Answer 1

Definicja operator paradoksalny jest funkcją F która odbywa funkcję f i zwraca funkcję p tak że

Biorąc F(f) = p następnie p = f(p)

Istnieje wiele możliwych kombinatorów stałego punktu, który mógłby być pisemny. Nie pozwól, by prostolinijność sprawiła, że ​​myślisz, że coś nie jest kombinatorem o ustalonej pozycji; tutaj jest standardowa definicja w JavaScript, która jest bardzo prosta

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

przykładowe użycia może być następnie obliczyć stałoprzecinkowej za silnia z:

var fact = function(f) { 
       return function(n) { return (n == 0) ? 1 : (n * f(n - 1)) } 
      }; 

alert(fix(fact)(7)); // alerts us with 5040. 

Na przykład inny stały kombinator punktowy (kombinator Y) patrz this helpful blog post.

Sprawdźmy, czy Twój kombinator until oblicza stałe punkty. Ponieważ pracujemy z funkcji monadycznych zmiany definicji stałoprzecinkowych nieznacznie obsługiwać strukturę jednowartościowy, gdzie F jest (monadycznego) operator paradoksalny gdy

Biorąc F(f) = p następnie p = f* . p

gdzie f* . p oznacza kompozycję Kleisli funkcji p z funkcją f (w twoim kodzie napiszesz to kleisli(p, f), możesz myśleć o * jako bind). Użyję tej notacji, ponieważ jest krótsza niż pisanie JavaScript.

Niech rozwinąć definicję until potem i zobacz, co mamy:

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 

Czy p = f* . p?

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

Tak - wierzę w to. Chociaż nie sądzę, że jest to przydatny stały punkt. (Obawiam się, że nie mam na to jeszcze dobrego argumentu - ale myślę, że jest to zasadniczo punkt o największym punkcie, który po prostu się rozejdzie).

Dla mnie wygląda na to, że argumenty podane na kleisli w until powinny zostać zamienione.Oznacza to, że chcemy zrobić równowartość Kleisli stosowania na przykład fix, więc musimy zdać jednowartościowy wynik rekurencyjnego wywołania until(f) do f:

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

Niech rozwinąć tę nową definicję until:

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

Czy p = f* . p? Tak, to:

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

ponieważ dodanie kolejnej kompozycji f * do nieskończonego łańcucha kompozycji f * jest tą samą funkcją.

Mam pewne problemy z rozbieżnościami (niektóre oceny zdarzają się zbyt wcześnie, więc obliczenia trwają, dopóki nie skończę przestrzeni stosu). Zamiast dodaje wydaje się działać dla mnie:

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

Więcej informacji na temat punktów stałych dla monadycznej kodu może chcesz sprawdzić the work of Erkök and Launchbury.