Ответ 1
Альтернативная реализация
Введение
Мне приходилось чаще работать в R с этого поста, поэтому я предлагаю альтернативную базовую реализацию R. Опять же, я подозреваю, что вы можете получить гораздо лучшую производительность, опустившись до уровня расширения C. Оригинальный ответ следует после разрыва.
Первой задачей в базе R является отсутствие истинного cons (выставленного на уровне R, то есть). R использует c для гибридной cons/concat-операции, но это не создает связанный список, а скорее новый вектор, заполненный элементами обоих аргументов. В частности, должна быть известна длина обоих аргументов, что не относится к ленивым последовательностям. Кроме того, последовательные операции c показывают квадратичную производительность, а не постоянное время. Теперь вы можете использовать "списки" (которые действительно являются векторами, а не связанными списками) длины два для эмуляции cons-ячеек, но...
Вторая проблема заключается в форсировании promises в структурах данных. R имеет некоторую ленивую семантику оценки с использованием неявного promises, но это граждане второго сорта. Функция для возврата явного обещания delay была устарела в пользу неявного delayedAssign, который выполняется только для его побочных эффектов - "Unevaluated promises никогда не будет видимым". Аргументы функции неявные promises, поэтому вы можете их обмануть, но вы не можете поместить обещание в структуру данных без принуждения.
CS 101
Оказывается, эти две проблемы могут быть решены, если вспомнить Computer Science 101. Структуры данных могут быть реализованы посредством закрытий.
cons <- function(h,t) function(x) if(x) h else t
first <- function(kons) kons(TRUE)
rest <- function(kons) kons(FALSE)
Теперь из-за семантики аргумента R lazy функции наши минусы уже способны к ленивым последовательностям.
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) }
Давайте используем то, что мы создали, чтобы суммировать все четные числа Фибоначчи менее 4 миллионов (Euler Project # 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) эти специальные thunks реализуют интерфейс последовательности и могут прозрачно использоваться как таковые, и (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
Lazy class class
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 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}