5

我试图弄清楚如何获得 R 的 callCC 函数，以对函数进行短路评估，以使用 lapply 和 Reduce 等函数。

动机

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

例如，如果我在列表中搜索一个值，我可以在列表中映射一个“finder”函数，第二个发现它 lapply 停止运行并返回该值（很像打破循环，或使用return 声明提前爆发）。

问题是我在编写 lapply 和 Reduce 应该使用 callCC 需要的样式的函数时遇到问题。

例子

假设我正在尝试编写一个函数来在列表中查找值“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 和 Reduce 结合使用的问题。

如果我含糊不清或需要任何澄清，请在下面发表评论。我希望有人可以帮助解决这个问题:)

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

4

3 回答 3

3

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

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 一起工作的技巧是在继续执行程序的其余部分之前将短路函数分配到输入函数环境中。我克隆了环境以避免意外的副作用。

于 2013-10-29T03:43:05.840 回答
2

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

处理@alexis_laz 方法的正确方法是在代码级别上争论不休。在基础 R 中，这是使用substitute(). 然而，有更好的软件包，例如rlangHadley Wickham。但我给你一个基本的 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=其中使用 a return_to breakout of the通常的部分lapply()。

正如您所展示的，这是目标：

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

就问题而言，我们希望能够概括这个表达式。我们想要

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

我们可以在我们FUN_为return_. return_但是，只有将函数定义代码插入到这个表达式中，我们才能让函数定义看到。这正是@alexis_laz 尝试使用字符串和评估。或者您通过操作环境变量来做到这一点。

我们可以安全地实现文字代码的插入，使用substitute(expr, replacer_list)whereexpr是要操作的代码，replacer_list是用于替换代码的查找表。我们采用forsubstitute(FUN)给出的文字代码而不对其进行评估。此表达式返回文字引用代码（比@alexis_laz 方法中的字符串更好）。FUN=lapply_

大substitute命令说：“取表达式callCC(function(return_) lapply(lst_, FUN_))并用给定的列表替换lst_此表达式中的列表coll和给定FUN_的文字引用表达式 for 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
于 2021-08-13T07:17:57.197 回答
0

我不知道它是否可以使用，但是：

    find100 <- "function (val) { if (val == 100) SHORT_CIRCUIT(val)  }"
    callCC( function (SHORT_CIRCUIT) lapply(1:1000, eval(parse(text = find100))) )
    #[1] 100
于 2013-10-17T19:10:42.363 回答