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)应该只返回前导数字.

注意:我对懒惰序列而不是自然数本身更感兴趣.

编辑:以下是Clojure的来源lazy-seq:

(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单元格,但是......

第二个挑战是强制数据结构中的承诺.R使用隐式承诺有一些懒惰的评估语义,但这些是二等公民.返回显式promise的函数delay已被弃用,有利于隐式delayedAssign,仅针对其副作用执行 - "未评估的promise应永远不可见".函数参数是隐式承诺,因此您可以接受它们,但是如果不强制它,您就不能将承诺放入数据结构中.

第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用户,我会尝试基于我的草图Clojure懒惰序列如何工作的插图.这仅用于示例目的,并未以任何方式调整性能.它可能更好地实现为C扩展(如果已经不存在).

延迟序列使序列的其余部分在thunk中生成计算.它没有被立即调用.当请求每个元素(或者元素块)时,调用下一个thunk来检索值.如果它继续,那个thunk可能会创建另一个thunk来表示序列的尾部.神奇之处在于:(1)这些特殊的thunk实现了一个序列接口,可以透明地使用它.(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}

Answer 2

该iterators库可能能够达到你要查找的内容:

library(iterators)
i <- icount()
nextElem(i)
# 1
nextElem(i)
# 2

你可以nextElem永远打电话.

Answer 3

由于R在向量上效果最好,因此通常需要一个返回向量的迭代器

library(iterators)
ichunk <- function(n, ..., chunkSize) {
    it <- icount(n)              # FIXME: scale by chunkSize
    chunk <- seq_len(chunkSize)
    structure(list(nextElem=function() {
        (nextElem(it) - 1L) * chunkSize + chunk
    }), class=c("abstractiter", "iter"))
}

典型的使用是在数百万范围内使用chunkSize.至少这会加快这种方法的永久性.