Re: [R] R and lazy evaluation

From: Russ Abbott <russ.abbott_at_gmail.com>
Date: Sat, 09 Apr 2011 10:51:10 -0700

I attempted to vectorize the preceding as follows.

fibs = function() {
  fibNumbers = 0:1
  fib =
    function(n) {

      print(n)
      ifelse(n <= length(fibNumbers),
            fibNumbers[n],
            fibNumbers[n] <- fib(n-1) + fib(n-2))
  }
}

Unless I'm misunderstanding what's going on,* ifelse()* seems to compute the conditional on the entire vector and take an *&* of the result. Here is the output. (Note the print statement at the beginning of the function.)

>x(5:7)[1] 5 6 7

[1] 4 5 6
[1] 3 4 5
[1] 2 3 4
[1] 1 2 3
[1] 0 1 2
[1] -1  0  1Error in fibNumbers[n] : only 0's may be mixed with
negative subscripts
*-- Russ Abbott*
*_____________________________________________*
***  Professor, Computer Science*
*  California State University, Los Angeles*

On Sat, Apr 9, 2011 at 12:50 AM, Russ Abbott <russ.abbott_at_gmail.com> wrote:

> The following doesn't rely on lazy evaluation, but it accomplishes
> something similar by taking advantage of R's closure capability.
>
> >fibs = function() {
> fibNumbers = 0:1
> fib = function(n) {
> if (n <= length(fibNumbers)) return(fibNumbers[n])
> fibNumbers[n] <- fib(n-1) + fib(n-2)
> return(fibNumbers[n])
> }
> }
> >x = fibs()
> >x(1)
> [1] 0
> >x(2)
> [1] 1
> >x(7)
> [1] 8
>
> The recursive calls to fib(n-1) and fib(n-2) are not inefficient since most
> of the results will be returned via lookup in fibNumbers. This also works.
>
> >sapply(1:12, x) [1] 0 1 1 2 3 5 8 13 21 34 55 89
>
>
> *-- Russ *
>
>
>
> On Fri, Apr 8, 2011 at 8:36 PM, Russ Abbott <russ.abbott_at_gmail.com> wrote:
>
>> Here's how to do it in Haskell.
>>
>> First define fibs to be an infinite list. Since Haskell is lazy, the list
>> isn't actually created until needed.
>>
>> The function zipWith takes three arguments: a function and two lists. (It
>> is similar to sapply except that it takes a function and two lists.) It
>> applies the function to the two lists pairwise (as in R) and returns the
>> result. In R one would presumably write this fibs + (tail fibs).
>>
>> So zipWith (+) fibs (tail fibs) adds the lists fibs and (tail fibs).
>>
>> So fibs is defined to be [0, 1, followed by the result of zipWith ... ].
>>
>>
>> let fibs = 0 : 1 : (zipWith (+) fibs (tail fibs))
>> fibs :: (Num a) => [a]
>> (0.00 secs, 527804 bytes)
>>
>> The previous statement defined fibs, which is an infinite list. The next
>> statement returns the first 10 element.
>>
>>
>> > take 10 fibs
>> [0,1,1,2,3,5,8,13,21,34]
>>
>> In R, one might try the following.
>>
>> >fibs <- c(0, 1, (fibs + fibs[-1]))
>>
>> Error: object 'fibs' not found
>>
>> But since this is a recursive definition in a context in which recursion is
>> not expected, an error message is produced.
>> *-- Russ *
>>
>>
>> On Fri, Apr 8, 2011 at 12:51 AM, peter dalgaard <pdalgd_at_gmail.com> wrote:
>>
>>>
>>> On Apr 8, 2011, at 06:08 , Russ Abbott wrote:
>>>
>>> > Haskell is the prototypical lazy evaluation language. One can compute a
>>> > Fibonacci sequence by the Haaskell equivalent of the following R code.
>>> >
>>> >> fibs <- c(0, 1, rep(0, 8))
>>> >> fibs[3:10] <- fibs + fibs[-1]
>>> >
>>> > This works as follows.
>>> >
>>> > fibs = 0, 1, 0, 0, 0, 0, 0, 0, 0, 0
>>> > fibs = 0, 1, 0, 0, 0, 0, 0, 0, 0, 0
>>> >
>>> > When one adds fibs to fibs[-1], one is effectively adding diagonally:
>>> > fibs[3] <- fibs[1] + fibs[2]
>>> > fibs[4] <- fibs[2] + fibs[3]
>>> > fibs[5] <- fibs[3] + fibs[4]
>>> > etc.
>>> >
>>> > In Haskell, the value of fibs[3] used to compute fibs[4] is the value
>>> just
>>> > created by adding fibs[1] and fibs[2]. Similarly the value of fibs[4]
>>> used
>>> > to compute fibs[5] is the value that was just created in the previous
>>> > addition. In other words:
>>> >
>>> > fibs[3] <- fibs[1] + fibs[2] # 0 + 1 = 1
>>> > fibs[4] <- fibs[2] + fibs[3] # 1 + 1 = 2
>>> > fibs[5] <- fibs[3] + fibs[4] # 1 + 2 = 3
>>> > fibs[6] <- fibs[4] + fibs[5] # 2 + 3 = 5
>>> > etc.
>>> >
>>> >
>>> > But if you actually carry out this calculation in R, this is you get.
>>> >
>>> >> v <- c(0, 1, rep(0, 8))
>>> >
>>> >> v
>>> >
>>> > [1] 0 1 0 0 0 0 0 0 0 0
>>> >
>>> >> v[3:10] <- v + v[-1]
>>> >
>>> > Warning messages:
>>> >
>>> > 1: In v + v[-1] :
>>> >
>>> > longer object length is not a multiple of shorter object length
>>> >
>>> > 2: In v[3:10] <- v + v[-1] :
>>> >
>>> > number of items to replace is not a multiple of replacement length
>>> >
>>> >> v
>>> >
>>> > [1] 0 1 1 1 0 0 0 0 0 0
>>> >
>>> >
>>> > Is there any way to make this work?
>>> >
>>>
>>> I should hope not.... (it would break call-by-value semantics, for one
>>> thing)
>>>
>>> The closest you can get is something like
>>>
>>> > delayedAssign("fib6", fib5+fib4)
>>> > delayedAssign("fib5", fib4+fib3)
>>> > delayedAssign("fib4", fib3+fib2)
>>> > delayedAssign("fib3", fib2+fib1)
>>> > delayedAssign("fib2", 1)
>>> > delayedAssign("fib1", 0)
>>> > fib6
>>> [1] 5
>>>
>>> (you can construct those assignments programmatically in a loop with a
>>> little extra work.)
>>>
>>> --
>>> Peter Dalgaard
>>> Center for Statistics, Copenhagen Business School
>>> Solbjerg Plads 3, 2000 Frederiksberg, Denmark
>>> Phone: (+45)38153501
>>> Email: pd.mes_at_cbs.dk Priv: PDalgd_at_gmail.com
>>>
>>>
>>
>

        [[alternative HTML version deleted]]



R-help_at_r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code. Received on Sat 09 Apr 2011 - 19:51:32 GMT

Archive maintained by Robert King, hosted by the discipline of statistics at the University of Newcastle, Australia.
Archive generated by hypermail 2.2.0, at Sat 09 Apr 2011 - 20:10:28 GMT.

Mailing list information is available at https://stat.ethz.ch/mailman/listinfo/r-help. Please read the posting guide before posting to the list.

list of date sections of archive