定点组合器的定义是一个函数F
,它接受一个函数f
并返回一个函数p
,使得
F(f) = p
当时给定p = f(p)
可以编写许多可能的定点组合器。不要让直截了当让您认为某事不是定点组合器;这是JavaScript中的一个标准定义,非常简单:
var fix = function(f) {
return function(x) {
return f(fix(f))(x)
}
};
一种用法可能是计算阶乘的定点,其中:
var fact = function(f) {
return function(n) { return (n == 0) ? 1 : (n * f(n - 1)) }
};
alert(fix(fact)(7)); // alerts us with 5040.
有关不同定点组合器(Y 组合器)的示例,请参阅这篇有用的博客文章。
让我们看看您的until
组合器是否计算定点。由于您使用的是单子函数,因此定点定义会略有变化以处理单子结构,其中F
(单子)定点组合器在
F(f) = p
当时给定p = f* . p
其中表示函数与函数f* . p
的 Kleisli 组合(在您的代码中,您将编写 this ,您可以将其视为)。我将使用这种表示法,因为它比编写 JavaScript 更短。p
f
kleisli(p, f)
*
bind
让我们展开until
then 的定义,看看我们得到了什么:
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
有吗p = f* . p
?
... . f* . f* . f =?= f* . ... . f* . f* . f
是的——我相信是的。虽然我不认为这是一个有用的固定点。(恐怕我对此还没有很好的论据——但我认为这基本上是一个最大固定点,只会发散)。
对我来说,看起来应该交换kleisli
in的参数。until
也就是说,我们希望在fix
示例中执行与应用程序等效的 Kleisli,因此我们需要将递归调用的一元结果传递until(f)
给f
:
var until = function(f) {
return function(a) {
return kleisli(until(f), f)(a);
};
};
让我们展开这个新的定义until
:
until(f) = f* . until(f)
= f* . (f* . until(f))
= f* . f* . ...
= p
有吗p = f* . p
?是的,它确实:
f* . f* ... = f* . (f* . f* . ...)
因为将 f* 的一个组合添加到 f* 组合的无限链上是相同的功能。
使用你的kleisli
函数我遇到了一些分歧问题(一些评估发生得太快了,所以计算运行直到我用完堆栈空间)。相反,以下似乎对我有用:
var until = function(f) {
return function(a) {
return bind(f,until(f)(a));
};
};
有关 monadic 代码的定点的更多信息,您可能想查看Erkök 和 Launchbury 的工作。