День второй (lazy list)

ЗАДАЧА
Реализация ленивых списков и ленивых вычислений над ними.

РЕШЕНИЕ
Первоначально я сконструировал список так:

> nums_from <-function(n)
     c(function() n, 
       function() 
          c(function() n + 1, 
            function() nums_from(n + 2)))

Сразу же выяснил, что писать функции, работающие с ним не очень удобно:

> ints <- nums_from(1) 
> ints[[1]]()
[1] 1
> ints[[2]]()[[1]]()
[1] 2
> ints[[2]]()[[2]]()[[1]]()
[1] 3

Следующий вариант стал более удачным:

> nums_from <-function(n)               
     pairlist(head = function() n,                        
              tail = function() 
                 pairlist(head = function() n + 1,
                          tail = function() nums_from(n + 2)))
> ints <- nums_from(1) # ленивый список натуральных числел
> ints$head()
[1] 1
> ints$tail()$head()
[1] 2
> ints$tail()$tail()$head()
[1] 3

В этот момент, я вспомнил, как где - то мне встречалось утверждение о том, что в R модель вычислений ленивая. Последовала незамедлительная проверка, не переливаю ли я из пустого в порожнее:

> nums_from <-function(n) c(n, c(n+1, nums_from(n + 2))) #1
> ints <- nums_from(1) #2
Ошибка: исполнение расположено слишком глубоко: неопределенная рекурсия / options(expressions=)?
> ?options
....
expressions:    sets a limit on the number of nested expressions that 
will be  evaluated. Valid values are 25...500000 with default 5000. 
If you increase it, you  may also want to start R with a larger protection 
stack; see --max-ppsize in  Memory. Note too that you may cause a segfault 
from overflow of the C stack, and on  OSes where it is possible you may 
want to increase that
.....

Так что #1 - если вычисления аргументов и ленивые, то непонятно, почему #2 - стек сносит. Т.е. стек сносит понятно почему - вычисления всё - таки производятся, при этом хвостовая реурсия, можно предположить, не оптимизируется. Тут определённо какие - то тонкости. С ними разберусь потом.

> take <- function(count, nums) {             
     if(count == 1) nums$head()             
     else  c( nums$head(), take(count - 1, nums$tail()) )
}
> take(6, ints)
[1] 1 2 3 4 5 6
> is.even <- function(num) num %% 2 == 0
> sieve <- function(cond, nums) {      
     if (cond(nums$head())) 
        pairlist(head = nums$head,                    
                 tail = function() sieve(cond, nums$tail()))
     else              
        sieve(cond, nums$tail())
}
> take(3, sieve( is.even, ints ))
[1] 2 4 6

В последнем вызове - sieve( is.even, ints )) уже лениво фильтруются чётные числа. Далее вычисляются 7 первых простых числел:

> nums_down_from <- function(n)       
     pairlist(head = function() n,              
              tail=function() pairlist(head = function() n - 1,   
                                       tail = function()
                                          nums_down_from(n - 2)))
> has.divider <- function(nums, dvding) {     
     if (nums$head() == 1) F     
     else if (dvding %% nums$head() == 0) T         
     else has.divider(nums$tail(), dvding) 
}
> is.prime <- function(num) {     
     if (num == 1) F      
     else {            
        nums <- nums_down_from(floor(sqrt(num)))           
        !has.divider(nums, num)      
     }
 }
> take(7, sieve( is.prime, ints ))
[1] 2 3 5 7 11 13 17

ВЫВОД
Второй предок R - Scheme. Вполне понятно моё желание поиграться с ленивыми списками и вычислениями. Я это сделал. Но результаты не очень - то и радуют. Похоже, хвостовая рекурсия съедает стек, а вместе с ним и все преимущества ленивости. Да, кстати, и memoization не реализована. Сегодняшний день породил больше вопросов чем ответов.