r - R中的惰性序列

Question

在 Clojure 中，使用惰性序列构造函数很容易创建无限序列。例如，

(def N (iterate inc 0))

返回一个数据对象 N相当于无限序列

(0 1 2 3 ...)

评估值 N导致无限循环。评估 (take 20 N)返回前 20 个数字。由于序列是惰性的，inc函数仅在您要求时迭代。由于 Clojure 是同音异形的，因此惰性序列是递归存储的。

在 R 中，是否可以做类似的事情？您能否提供一些生成数据对象的示例 R 代码 N这相当于自然数的完整无限序列？评估完整对象 N应该会导致循环，但类似于 head(N)应该只返回前导数字。

注意:我真的对惰性序列而不是自然数本身更感兴趣。

编辑:这里是 lazy-seq 的 Clojure 源代码:

(defmacro lazy-seq
"Takes a body of expressions that returns an ISeq or nil, and yields
a Seqable object that will invoke the body only the first time seq
is called, and will cache the result and return it on all subsequent
seq calls. See also - realized?"
{:added "1.0"}
[& body]
(list 'new 'clojure.lang.LazySeq (list* '^{:once true} fn* [] body)))    

我正在寻找在 R 中具有相同功能的宏。

Answer 1

替代实现

介绍

自从这篇文章以来，我有机会更频繁地在 R 中工作，所以我提供了一个替代的基本 R 实现。同样，我怀疑您可以通过降低到 C 扩展级别来获得更好的性能。休息后有原始答案。

基础 R 中的第一个挑战是缺乏真正的 cons (暴露在 R 级，即)。 R 使用 c对于混合 cons/concat 操作，但这不会创建一个链表，而是一个填充了两个参数的元素的新向量。特别是，必须知道两个参数的长度，而惰性序列则不是这种情况。此外，连续 c运算表现出二次性能而不是恒定时间。现在，您可以使用长度为 2 的“列表”(实际上是向量，而不是链表)来模拟 cons 单元格，但是...

第二个挑战是在数据结构中强制 promise 。 R 有一些使用隐式 promise 的惰性求值语义，但这些是二等公民。返回显式 promise 的函数，delay , 已被弃用以支持隐式 delayedAssign ，这只是为了它的副作用而执行——“未评估的 promise 永远不应该是可见的。”函数参数是隐含的 Promise，因此您可以掌握它们，但您不能在没有强制执行的情况下将 Promise 放入数据结构中。

CS 101

事实证明，这两个挑战可以通过回想计算机科学 101 来解决。数据结构可以通过闭包来实现。

cons <- function(h,t) function(x) if(x) h else t

first <- function(kons) kons(TRUE)
rest <- function(kons) kons(FALSE)  

现在由于 R 的惰性函数参数语义，我们的缺点已经能够处理惰性序列。

fibonacci <- function(a,b) cons(a, fibonacci(b, a+b))
fibs <- fibonacci(1,1)

为了有用，我们需要一套惰性序列处理函数。在 Clojure 中，作为核心语言一部分的序列处理函数自然也适用于惰性序列。另一方面，R 的序列函数不会立即兼容。许多人依赖于提前知道(有限)序列长度。让我们定义一些能够处理惰性序列的方法。

filterz <- function(pred, s) {
  if(is.null(s)) return(NULL)
  f <- first(s)
  r <- rest(s)
  if(pred(f)) cons(f, filterz(pred, r)) else filterz(pred, r) }

take_whilez <- function(pred, s) {
   if(is.null(s) || !pred(first(s))) return(NULL)
   cons(first(s), take_whilez(pred, rest(s))) }

reduce <- function(f, init, s) {
  r <- init
  while(!is.null(s)) {
    r <- f(r, first(s))
    s <- rest(s) }
  return(r) }

让我们使用我们创建的所有小于 400 万的偶数斐波那契数求和(欧拉项目 #2):

reduce(`+`, 0, filterz(function(x) x %% 2 == 0, take_whilez(function(x) x < 4e6, fibs)))
# [1] 4613732

原始答案

我对 R 非常生疏，但是由于(1)因为我熟悉 Clojure，并且(2)我认为您没有将您的观点传达给 R 用户，所以我将尝试基于我的草图illustration of how Clojure lazy-sequences work .这仅用于示例目的，不以任何方式调整性能。它可能会更好地实现为 C 扩展(如果尚不存在)。

惰性序列在 thunk 中具有序列生成计算的其余部分。它不会立即被调用。当请求每个元素(或可能的元素 block )时，将调用下一个 thunk 以检索值。如果继续，该 thunk 可能会创建另一个 thunk 来表示序列的尾部。神奇之处在于(1)这些特殊的 thunk 实现了一个序列接口(interface)，并且可以透明地用作这样的接口(interface)；(2)每个 thunk 只被调用一次——它的值被缓存——所以实现的部分是一个值序列。

先说标准例子

自然数

numbers <- function(x) as.LazySeq(c(x, numbers(x+1)))
nums <- numbers(1)

take(10,nums) 
#=> [1]  1  2  3  4  5  6  7  8  9 10

#Slow, but does not overflow the stack (level stack consumption)
sum(take(100000,nums))
#=> [1] 5000050000

斐波那契数列

fibonacci <- function(a,b) { 
 as.LazySeq(c(a, fibonacci(b, a+b)))}

fibs <- fibonacci(1,1)

take(10, fibs)
#=> [1]  1  1  2  3  5  8 13 21 34 55

nth(fibs, 20)
#=> [1] 6765

其次是天真的R实现

惰性序列类

is.LazySeq <- function(x) inherits(x, "LazySeq")

as.LazySeq <- function(s) {
  cache <- NULL
  value <- function() {
    if (is.null(cache)) {
      cache <<- force(s)
      while (is.LazySeq(cache)) cache <<- cache()}
    cache}
  structure(value, class="LazySeq")}

一些具有 LazySeq 实现的通用序列方法

first <- function(x) UseMethod("first", x)
rest <- function(x) UseMethod("rest", x)

first.default <- function(s) s[1]

rest.default <- function(s) s[-1]

first.LazySeq <- function(s) s()[[1]]

rest.LazySeq <- function(s) s()[[-1]]

nth <- function(s, n) {
  while (n > 1) {
    n <- n - 1
    s <- rest(s) }
  first(s) }

#Note: Clojure's take is also lazy, this one is "eager"
take <- function(n, s) {
  r <- NULL
  while (n > 0) {
    n <- n - 1
    r <- c(r, first(s))
    s <- rest(s) }
  r}