From Wikipedia: In functional programming, fold or reduce or accumulate is a family of higher-order functions that process a data structure in some order and build up a return value. This is as opposed to the family of unfold
functions which take a starting value and apply a function to it
repeatedly to generate a data structure. Typically, a fold deals with
two things: a combining function, and a data structure, typically a list of elements. The fold then proceeds to combine elements of the data structure using the function in some systematic way.
Haskell has two folding functions: foldl and foldr.
Hugs> foldl (+) 10 [1,2,3,4]
20
Hugs> foldr (-) 10 [1,2,3,4]
8
As we can see, both functions have three arguments. The first argument is a function which takes two arguments. The second is a accumulator and the third is a list which is folded. foldl function works this way: it takes the accumulator and the first left element of the list and applies the function (first argument) on them. The result becomes the new accumulator. Then the function is applied on the accumulator and the second left element of the list. This process is repeated with all the elements of the list. foldr function do the opposite. It takes the first right element of the list and applies the function on the accumulator and this element. The result becomes new accumulator. The function is then applied on this new accumulator and the second right element of the list.
So, foldl (+) 10 [1,2,3,4] is actually this:
((((1 + 10) + 2) + 3) + 4) = 20
and foldr (-) 10 [1,2,3,4] is:
(1 - (2 - (3 - (4 - 10)))) = 8
But fold functions aren't limited to infix functions. If you want to find the biggest element in the list, you can write something like:
Hugs> foldl max 0 [1,2,6,4]
6
Now when we know how the fold functions are working, we can implement them in C#. First we will define a delegate (an object which will mimic the behavior of a function which is first argument in foldl and foldr).
public delegate T Fun<T>(T val1, T val2);
Then we will implement both fold functions, foldl and foldr.
public static T Foldl<T>(Fun<T> function,
T accumulator,
IEnumerable<T> list)
{
foreach (T listItem in list)
accumulator = function(listItem, accumulator);
return accumulator;
}
public static T Foldr<T>(Fun<T> function, T
accumulator,
IEnumerable<T> list)
{
list = list.Reverse<T>();
foreach (T listItem in list)
accumulator = function(listItem, accumulator);
return accumulator;
}
That's it. Now we just need to see how can we use this two functions. In C# 2.0 you can do:
int[] list = new list[]{1,2,3,4};
//find the sum of all elements
int res = Foldl<int>(
delegate(int val1, int val2)
{ return val1 + val2; },
0,
list);
//nothing usefull :)
res = Foldr<int>(
delegate(int val1, int val2)
{ return val1 - val2; },
10,
list);
//find the biggest element in a list
res = Foldl<int>(
delegate(int val1, int val2)
{ return (val1 >= val2) ? val1 : val2; },
Int32.MinValue,
list);
But, in C# 3.0 you can write something like this:
//find the biggest element in a list
var r = Foldl(
(x1, x2) => (x1 >= x2) ? x1 : x2,
Int32.MinValue,
list);