在R中使用高阶函数的callCC

Question

我试图弄清楚如何得到R的callCC函数，用于短路计算一个函数，以便与像lapply和Reduce这样的函数一起工作。

动机

这将使Reduce和lapply具有渐近效率> O(n)，因为它允许您提前退出计算。

例如，如果我在列表中搜索一个值，我可以在列表中映射一个'finder‘函数，第二次发现它就会停止运行并返回这个值(就像中断一个循环，或者使用一个return语句提前爆发)。

问题是，我很难使用callCC所需的样式编写lapply和Reduce应该使用的函数。

示例

假设我正在编写一个函数，以便在列表中找到'100‘值:相当于

imperativeVersion <- function (xs) {
    for (val in xs) if (val == 100) return (val)
}

传递给lapply的函数如下所示：

find100 <- function (val) { if (val == 100) SHORT_CIRCUIT(val)  }
functionalVersion <- function (xs) lapply(xs, find100)

这(显然)崩溃，因为短路功能还没有定义。

callCC( function (SHORT_CIRCUIT) lapply(1:1000, find100) )

问题是，这也会崩溃，因为在定义find100时，短路函数并不存在。我希望类似的东西能起作用。

以下操作之所以有效，是因为SHORT_CIRCUIT是在创建传递给lapply的函数时定义的。

callCC(
    function (SHORT_CIRCUIT) {
        lapply(1:1000, function (val) {
             if (val == 100) SHORT_CIRCUIT(val)
        })
)

如何在传递给lapply的函数中定义SHORT_CIRCUIT，而不像上面那样内联地定义它呢？

我知道这个例子可以使用循环、减少或任何其他方法来实现。我正在寻找一个解决方案的问题，使用callCC与lapply和减少在具体。

如果我是模糊的，或需要任何澄清，请在下面留下评论。我希望有人能帮上忙:)

编辑一:方法应该是“生产-质量”；没有偏离功能或类似的黑魔法。

Answer 1

我找到了解决这个问题的方法：

find100 <- function (val) {
    if (val == 100) SHORT_CIRCUIT(val)
}

short_map <- function (fn, coll) {


    callCC(function (SHORT_CIRCUIT) {

        clone_env <- new.env(parent = environment(fn))
        clone_env$SHORT_CIRCUIT <- SHORT_CIRCUIT

        environment(fn) <- clone_env
        lapply(coll, fn)

    })
}

short_map(find100, c(1,2,100,3))

使高阶函数与callCC一起工作的诀窍是，在执行程序的其余部分之前，将短路函数分配到输入函数环境中。我复制了一个环境以避免意外的副作用。

Answer 2

您可以在R @alexis_laz中使用元编程来实现这一点，实际上，这种方法已经是元编程了。然而，他使用的字符串是一个肮脏的黑客和容易出错的字符串。所以你很好地拒绝了它。

接近@alexis_laz方法的正确方法是在代码级别上进行争论。在基本R中，这是使用substitute()完成的。然而，还有更好的包，如哈德利韦翰的rlang。但是我给出了一个基本的R解决方案(更少的依赖性)。

lapply_ <- function(lst, FUN) {
  eval.parent(
    substitute(
      callCC(function(return_) {
        lapply(lst_, FUN_)
      }), 
      list(lst_ = lst, FUN_=substitute(FUN))))
}

您的SHORT_CIRCUIT函数实际上是一个更通用的控制流return函数(或者一个使用参数返回它的break函数)。因此，我称它为return_。

我们希望有一个lapply_函数，其中我们可以在FUN=部分中使用return_来从通常的lapply()中提取break。

正如你所表明的，这就是目标：

callCC(
  function (return_) {
    lapply(1:1000, function (x) if (x == 100) return_(x))
  }
)

关于这个问题，我们希望能够概括这个表达式。我们想要

callCC(
  function(return_) lapply(lst, FUN_)
)

在这里，我们可以在函数定义中使用我们为FUN_提供的return_。但是，只有在将函数定义代码插入到该表达式中时，函数定义才能看到return_。这正是@alexis_laz尝试使用字符串和eval的方法。或者你通过操纵环境变量来做到这一点。

我们可以使用substitute(expr, replacer_list)安全地实现文字代码的插入，其中expr是要操作的代码，replacer_list是替换代码的查找表。通过substitute(FUN)，我们使用为FUN=给出的用于lapply_的字面代码，而不计算它。这个表达式返回引用文字的代码(比@alexis_laz方法中的字符串更好)。

大的substitute命令说：“接受表达式callCC(function(return_) lapply(lst_, FUN_))，并将表达式中的lst_替换为为coll和FUN_提供的列表，将其替换为为FUN提供的引用表达式。

然后在父环境(eval.parent())中计算这个替换的表达式，意思是:得到的表达式替换了lapply_()调用，并准确地在放置的位置执行。

eval.parent() (或eval( ... , envir=parent.frame()))的这种使用是愚蠢的证明。(否则，tidyverse软件包就不会是生产级.)。

因此，通过这种方式，您可以泛化callCC()调用。

lapply_(1:1000, FUN=function(x) if (x==100) return_(x))
## [1] 100

Answer 3

我不知道它是否有用，但是：

    find100 <- "function (val) { if (val == 100) SHORT_CIRCUIT(val)  }"
    callCC( function (SHORT_CIRCUIT) lapply(1:1000, eval(parse(text = find100))) )
    #[1] 100