oneminusp.com Computational Finance, Markets, Programming & co

fold left in R

Often used high order functions in functional programming are left and right folds.

A left fold [foldleft f accu l] applies the head of the list l to the function f together with the accumulator variable accu. The result is the new accumulator which is used in the next recursive call together with the tail of the list.

A left (or right) fold is easily implemented in R as follows:

foldleft <- function(f,accu,l) {
	if(length(l)==0) {
		accu
	} else {
		head <- l[1];
		tail <- l[-1];
		foldleft(f, (f(accu, head)) , tail)
	}
}

To see how it works, we could apply it to calculate the variance of a fair die. Remember the variance is just where is the mean, which is implemented in the following function f:

mean<-sum(1:6)/6

f <- function(accu,i) {
	accu+(1/6 * (i-mean)^2)
}

foldleft(f,0,c(1,2,3,4,5,6))

where our last call to foldleft evaluates to 2.91667.