gpt4 book ai didi

javascript - 这是定点组合器的实现吗?

转载 作者:数据小太阳 更新时间:2023-10-29 05:19:19 29 4
gpt4 key购买 nike

我认为这不能称为“定点递归”,因为它太简单了。然而,我最近意识到它实际上可能是。

我是否有效地实现了定点递归?

这里是有问题的函数:

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

这里有一些额外的上下文:

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

剩下的代码是here ,但上面的代码片段应该足以跟进。

最佳答案

定点组合器的定义是一个函数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 组合器)的示例,请参阅 this helpful blog post .

让我们看看您的 until 组合器是否计算定点。由于您正在使用 monadic 函数,因此定点定义略有变化以处理 monadic 结构,其中 F 是一个(monadic)定点组合器,当

给定 F(f) = p 然后 p = f* 。 p

其中 f* 。 p 表示函数 p 与函数 f 的 Kleisli 组合(在您的代码中,您将编写此 kleisli(p, f),您可以将 * 视为 bind)。我将使用这种表示法,因为它比编写 JavaScript 更短。

然后让我们展开 until 的定义,看看我们得到了什么:

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

是的-我相信是这样。虽然我不认为这是一个有用的固定点。 (恐怕我对此还没有很好的论据 - 但我认为这基本上是一个最大的固定点,它只会发散)。

在我看来,untilkleisli 的参数似乎应该被交换。也就是说,我们希望在 fix 示例中执行 Kleisli 等效应用程序,因此我们需要将递归调用 until(f) 的单子(monad)结果传递给 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));
};
};

有关单子(monad)代码定点的更多信息,您可能想查看 the work of Erkök and Launchbury .

关于javascript - 这是定点组合器的实现吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17821019/

29 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com