[R] fold right - recursive list (vector) operators

[Thomas Lumley]

On Wed, 3 Nov 2004, Mads Jeppe Tarp-Johansen wrote:

>
> The programming language mosml comes with foldr that 'accumulates' a
> function f over a list [x1,x2,...,xn] with initial value b as follows
>
> foldr f b [x1,x2,...,xn]  =  f(x1,...,f(xn-1,f(xn,b))...)
>
> Observe that "list" should have same elements so in R terminology it would
> perhaps be appropriate to say that the accumulation takes place over a
> 'vector'.
>
> I wonder if R comes with a similar function and in general a library or
> package with list (vector) operators. Or is such programming style not
> intended in R?
>

Only a few such second-order functions are built in, eg sapply() and 
mapply().

For short vectors it is easy to write recursive implementations of most of 
them, eg your foldr function:

reduce<-function(f,b,x){
         n<-length(x)
 	if (n==1)
  	   f(x,b)
         else
 	   f(x[1],reduce(f,b,x[-1]))
}

For longer vectors you need an iterative implementation.
eg
reduce<-function(f,b,x){
     n<-length(x)
     rval<-f(x[n],b)
     if (n>1){
       for (xn in rev(x[-1]))
   	rval<-f(xn,rval)
       }
     return(rval)
}

 	-thomas