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

Thomas Lumley tlumley at u.washington.edu
Wed Nov 3 23:26:16 CET 2004

```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

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

```