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 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 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@cbs.dk Priv: PDalgd@gmail.com
>>
>>
>
[[alternative HTML version deleted]]