R help - Nov 2004 - fold right - recursive list (vector) operators

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?

Regards MJ

Dear MJ,

If I follow correctly what you want to do, then the following should
work:

foldr <- function(f, x){
      if (length(x) > 1) f(c(x[1], Recall(f, x[-1])))
      else f(x)
      }

For example,
> sum(c(4, sum(c(2, sum(6)))))
[1] 12
> foldr(sum, c(4,2,6))
[1] 12

I hope this helps,
 John

On Wed, 3 Nov 2004 22:59:11 +0100 (CET)
 Mads Jeppe Tarp-Johansen <s02mjtj at math.ku.dk>
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?
> 
> Regards MJ
> 
> ______________________________________________
> R-help at stat.math.ethz.ch mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide!
> http://www.R-project.org/posting-guide.html
--------------------------------
John Fox
Department of Sociology
McMaster University
Hamilton, Ontario, Canada
http://socserv.mcmaster.ca/jfox/

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

Mads Jeppe Tarp-Johansen <s02mjtj at math.ku.dk> writes:
> 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?
R does generally encourage abstraction and encapsulation. However
operations like foldr are not common in statistics, I'd say. We have
cumsum and cumprod, which are the same sort of thing, hard coded. It's
easy to implement in R, although possibly not efficiently. Something
like this should work (untested!):

foldr <- function(f, b, x) {
   if (!(n <- length(x))) stop("zero-length x not allowed")
   if (n == 1)
      f(b, x) 
   else
      foldr(f, f(x[n], b), x[-n])
}

or non-recursively (equally untested)

foldr <- function(f, b, x)
{
   if (!(n <- length(x))) stop("zero-length x not allowed")
   while (n) { 
     b <- f(b, x[n])
     n <- n - 1
   }
   b
}



-- 
   O__  ---- Peter Dalgaard             Blegdamsvej 3  
  c/ /'_ --- Dept. of Biostatistics     2200 Cph. N   
 (*) \(*) -- University of Copenhagen   Denmark      Ph: (+45) 35327918
~~~~~~~~~~ - (p.dalgaard at biostat.ku.dk)             FAX: (+45) 35327907