What's the formal term for a "foldable" function?

Question

I use the LINQ Aggregate operator quite often. Essentially, it lets you "accumulate" a function over a sequence by repeatedly applying the function on the last computed value of the function and the next element of the sequence.

For example:

int[] numbers = ...
int result = numbers.Aggregate(0, (result, next) => result + next * next);

will compute the sum of the squares of the elements of an array.

After some googling, I discovered that the general term for this in functional programming is "fold". This got me curious about functions that could be written as folds. In other words, the f in f = fold op.

I think that a function that can be computed with this operator only needs to satisfy (please correct me if I am wrong):

f(x1, x2, ..., xn) = f(f(x1, x2, ..., xn-1), xn)

This property seems common enough to deserve a special name. Is there one?

Answer 1

An Iterated binary operation may be what you are looking for.

You would also need to add some stopping conditions like

f(x) = something
f(x1,x2) = something2

They define a binary operation f and another function F in the link I provided to handle what happens when you get down to f(x1,x2).

Answer 2

To clarify the question: 'sum of squares' is a special function because it has the property that it can be expressed in terms of the fold functional plus a lambda, ie

sumSq = fold ((result, next) => result + next * next) 0

Which functions f have this property, where dom f = { A tuples }, ran f :: B?

Clearly, due to the mechanics of fold, the statement that f is foldable is the assertion that there exists an h :: A * B -> B such that for any n > 0, x1, ..., xn in A, f ((x1,...xn)) = h (xn, f ((x1,...,xn-1))).

The assertion that the h exists says almost the same thing as your condition that

f((x1, x2, ..., xn)) = f((f((x1, x2, ..., xn-1)), xn))     (*)

so you were very nearly correct; the difference is that you are requiring A=B which is a bit more restrictive than being a general fold-expressible function. More problematically though, fold in general also takes a starting value a, which is set to a = f nil. The main reason your formulation (*) is wrong is that it assumes that h is whatever f does on pair lists, but that is only true when h(x, a) = a. That is, in your example of sum of squares, the starting value you gave to Accumulate was 0, which is a does-nothing when you add it, but there are fold-expressible functions where the starting value does something, in which case we have a fold-expressible function which does not satisfy (*).

For example, take this fold-expressible function lengthPlusOne:

lengthPlusOne = fold  ((result, next) => result + 1) 1

f (1) = 2, but f(f(), 1) = f(1, 1) = 3.

Finally, let's give an example of a functions on lists not expressible in terms of fold. Suppose we had a black box function and tested it on these inputs:

f (1) = 1
f (1, 1) = 1    (1)
f (2, 1) = 1
f (1, 2, 1) = 2 (2)

Such a function on tuples (=finite lists) obviously exists (we can just define it to have those outputs above and be zero on any other lists). Yet, it is not foldable because (1) implies h(1,1)=1, while (2) implies h(1,1)=2.

I don't know if there is other terminology than just saying 'a function expressible as a fold'. Perhaps a (left/right) context-free list function would be a good way of describing it?