What is the formal term for a "folding" function?

Question

I often use the LINQ Aggregate statement. Essentially, it allows you to “accumulate” a function over a sequence by reapplying this function to the last computed value of the function and the next element of the sequence.

For instance:

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

will calculate the sum of the squares of the elements of the array.

After some searching on Google, I found that the general term for this in functional programming is “fold” .

Now I think that a function that can be evaluated using this statement should only 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. There is one?

Answer 1

To clarify the question: “sum of squares” is a special function, because it has the property that it can be expressed in terms of bend plus lambda functionality, i.e.

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

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

Obviously, due to the mechanics of folding, the statement that f is added is a statement about the existence of h :: A * B -> B such that for any n> 0, x1, ..., xn in A, f ((x1,...xn)) = h (xn, f ((x1,...,xn-1))) .

The statement about the existence of h says almost the same as your condition that

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

therefore you were almost right; the difference is that you need A=B , which is a bit more restrictive than the general fold fold function. More problematic, however, folding in general also assumes the initial value a , which is set to a = f nil . The main reason your wording (*) is incorrect is because it assumes that h is what f does for paired lists, but this is only true when h(x, a) = a . That is, in your example of the sum of the squares, the initial value that you gave Accumulate is 0, which does nothing when you add it, but there are functions with a bend expression where the initial value does something, and in this case we have a folded function that does not satisfy (*).

For example, take this function with a bend expression lengthPlusOne :

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

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

Finally, we give an example of functions on lists that are not expressed in terms of a fold. Suppose we used the 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 simply define it so that these outputs are higher and equal to zero in any other lists). However, it does not add up, because (1) means h(1,1)=1 , and from (2) it follows h(1,1)=2 .

I do not know if there is any other terminology than just saying "function expressed as a fold." Perhaps a handy list function (left and right) is context-sensitive to describe it?

Answer 2

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

You also need to add some stopping conditions, for example

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

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

Answer 3

In functional programming, fold used to combine the results in a collection, such as a list, an array, a sequence ... Your formulation of fold is incorrect, which leads to confusion. The correct wording may be:

 fold fe [x1, x2, x3,..., xn] = f((...f(f(f(e, x1),x2),x3)...), xn) 

The requirement for f is actually very weak. Suppose that the type of elements is T , and the type of e is U Thus, the function f really takes two arguments: the first type of type U and the second type of T , and returns a value of type U (since this value will be provided as the first argument of f again). In short, we have a function to "accumulate" with a signature f: U * T -> U For this reason, I do not think that there is a formal term for these kinds of functions.

In your example, e = 0 , T = int , U = int and your lambda function (result, next) => result + next * next has the signature f: int * int -> int , which satisfies the condition of "folding" functions.

If you want to know, another fold option is foldBack , which accumulates the results in reverse order from xn to x1 :

  foldBack f [x1, x2,..., xn] e = f(x1,f(x2,...,f(n,e)...)) 

There are interesting cases with commutative functions that satisfy f (x, y) = f (x, y) when fold and foldBack return the same result. The fold itself is a special case of catamorphism in category theory. You can learn more about catamorphism here .