implementing fold in c#

Reading about folding in haskell, i thought about implementing this in c#. First of all i want to describe right and left folding in haskell. Folding means that we are executing an operation to every element of a list. So in the next example we subtract all elements of a list. With left folding (foldl) we start at the beginning of the list with our operation, with right folding (foldr) we start at the end of the list with our operations. Here are two haskell examples for left folding and right folding.

foldl (-) [1,2,3,4,5]

> -13

foldr (-) [1,2,3,4,5]

> -5

As we see calculation of foldl starts at the left side of the list (1-2-3-4-5 = -13), foldr starts at the right side of the list (5-4-3-2-1 = -5). In c# left folding (foldl) is implemented in the Aggregate extension method. This example shows the use of Aggreagate:

var value = (new[] { 1, 2, 3, 4, 5 }).Aggregate((a, b) => a - b);
Assert.AreEqual(-13, value);

Now we start implementing FoldL. This first implementation works exact  as the Aggreagte method.

var value = (new[] { 1, 2, 3, 4, 5 }).FoldL((a, b) => a - b);
Assert.AreEqual(-13, value);

As we see in the implementation of FoldL we run through the list and calculate the value by calling the func delegate.

public static T FoldL<T>(this IEnumerable<T> list, Func<T, T, T> func)
{
    bool containsValue = false;
    T firstValue = default(T);
    bool firstValueSet = false;
    IEnumerator<T> iEnumerator = list.GetEnumerator();
    while(iEnumerator.MoveNext())
    {
        containsValue = true;
        T tempValue = iEnumerator.Current;
        if(firstValueSet)
            tempValue = func(firstValue, tempValue);
        firstValueSet = true;
        firstValue = tempValue;
    }
    if(containsValue)
        return firstValue;
    return default(T);
}

For the right folding there is no standard implentation in Linq. For that reason we will implement it here:

var value = (new[] { 1, 2, 3, 4, 5 }).FoldR((a, b) => a - b);
Assert.AreEqual(-5, value);
public static T FoldR<T>(this IEnumerable<T> list, Func<T, T, T> func)
{
    Stack<T> stack = new Stack<T>();
    T firstValue = default(T);
    bool containsValue = false;
    bool firstValueSet = false;
    T tempValue = default(T);
    foreach (var item in list)
    {
        stack.Push(item);
    }
    while (stack.Count() > 0)
    {
        firstValue = stack.Pop();
        containsValue = true;
        if (firstValueSet)
        {
            tempValue = func(tempValue, firstValue);
        }
        else
        {
            firstValueSet = true;
            tempValue = firstValue;
        }                
    }            
    if (containsValue)
        return tempValue;
    return default(T);
}

Now we want to build foldl and foldr a little more haskell style. For that we use a string that contains the operation (for example “-“) and we overtake the list we want to fold. So the calls for foldl and foldr are:

var result = Fold.Fold.FoldL("-", new[] { 1, 2, 3, 4, 5 });
Assert.AreEqual<int>(-13, result);
var result = Fold.Fold.FoldR("-", new[] { 1, 2, 3, 4, 5 });
Assert.AreEqual<int>(-5, result);

The implementation of foldL and foldR works with the dynamic generation of a expressiontree. In case which operation (“+”,”-“,”*”,”/”,”^”) is overtaken it generates a dynamic lambda function (Func<T,T,T>). This dynamic function is then called for every value in the list.

public static T FoldL<T>(string binaryOperator, T[] list)
{
    ParameterExpression startValueParameter = Expression.Parameter(typeof(T), "startValue");
    ParameterExpression listValueParameter = Expression.Parameter(typeof(T), "listValue");
    Func<T, T, T> func = Expression.Lambda<Func<T, T, T>>
        (CreateBinaryExpression(binaryOperator, startValueParameter, listValueParameter),
        new ParameterExpression[] { startValueParameter, listValueParameter }).Compile();
    if (list.Count() == 0)
    {
        return default(T);
    }
    else if (list.Count() == 1)
    {
        return list[0];
    }
    else
    {
        T tempValue = list[0];
        for (int i = 1; i < list.Count(); i++)
        {
            tempValue = func(tempValue, list[i]);
        }
        return tempValue;
    }
}

FoldR works like foldL but the list is iterated form the back to the front.

public static T FoldR<T>(string binaryOperator, T[] list)
{
    ParameterExpression startValueParameter = Expression.Parameter(typeof(T), "startValue");
    ParameterExpression listValueParameter = Expression.Parameter(typeof(T), "listValue");
    Func<T, T, T> func = Expression.Lambda<Func<T, T, T>>
        (CreateBinaryExpression(binaryOperator, startValueParameter, listValueParameter),
        new ParameterExpression[] { startValueParameter, listValueParameter }).Compile();
    if (list.Count() == 0)
    {
        return default(T);
    }
    else if (list.Count() == 1)
    {
        return list[0];
    }
    else
    {
        T tempValue = list[list.Count() - 1];
        for (int i = list.Count() - 2; i >= 0; i--)
        {
            tempValue = func(tempValue, list[i]);
        }
        return tempValue;
    }
}

Here is the CreateBinaryExpression method that converts the overtaken string (for example “-“) to a binary expression and adds the startValueParameter and the listValueParameter to the binaryExpression.

private static BinaryExpression CreateBinaryExpression(string binaryOperator, 
    ParameterExpression startValueParameter,
    ParameterExpression listValueParameter)
{
    BinaryExpression binaryExpression = null;
    switch (binaryOperator)
    {
        case "+":
            binaryExpression = Expression.Add(startValueParameter, listValueParameter);
            break;
        case "-":
            binaryExpression = Expression.Subtract(startValueParameter, listValueParameter);
            break;
        case "*":
            binaryExpression = Expression.Multiply(startValueParameter, listValueParameter);
            break;
        case "/":
            binaryExpression = Expression.Divide(startValueParameter, listValueParameter);
            break;
        case "^":
            binaryExpression = Expression.Power(startValueParameter, listValueParameter);
            break;
        default:
            throw new Exception("no binary Operator specified.");
    }
    return binaryExpression;
}

So one could argue that foldl and foldr in haskell are much more powerfull than just using addition, subtraction, multiblication, division and square and thats right but nevertheless i like that haskell style in c#.

Advertisements


If you have a note or a question please write a comment.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s