6

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

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

这是有问题的功能：

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

其余的代码在这里，但上面的代码片段应该足以遵循。

4

1 回答 1

6

定点组合器的定义是一个函数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 更短。pfkleisli(p, f)*bind

让我们展开untilthen 的定义，看看我们得到了什么：

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

是的——我相信是的。虽然我不认为这是一个有用的固定点。（恐怕我对此还没有很好的论据——但我认为这基本上是一个最大固定点，只会发散）。

对我来说，看起来应该交换kleisliin的参数。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 的工作。

于 2013-07-26T17:05:28.470 回答