fold right - recursive list (vector) operators

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)

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/

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