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#.


currying in c#

Today i want to write about a functional programming topic. This topic is curried functions. To curry a function is named after the mathematician Haskell Curry and means to build a function with n – 1 parameters out of a function with n parameters. If you have the function:

Func<int, int, int> mul = (x, y) => x * y;

the curried function out of this Function would be:

Func<int, Func<int, int>> curriedMul = mul.Curry();

That means that the curried function takes only one parameter and returns a function with one parameter. If we now call the curried function:

Func<int, int> executedCurriedMul = curriedMul(2);

Now the function executedCurriedMul has saved the first paramter (2) in the function. If we now call the resulting function

 int mulResult = executedCurriedMul(3);
 Console.WriteLine(mulResult);
 6

it returns 6. That means that we split up the pass of the parameters.
Alternative we could invoke the curried function this way:

int mulResult = curriedMul(2)(3);

In haskell every function is a curried function:

mult :: Integer -> Integer -> Integer
mult a b = a * b

*Main> let curriedMult = mult 2
*Main> curriedMult 3
6

In f# also every function is a curried function:

let mult a b = a * b
let curriedMult = mult 2.0
let multResult = curriedMult 3.0

printfn "result = %f" multResult
6.0

but in c# we need a extension method to curry a given function.

//Currying a function with two parameters using anonyme methodes.
//The method generates two nested anonymus methodes.
//with the call of the method a delegate to a anonymus method 
//with one parameter of type T1 and a return type of type
//Func<T1, Func<T2, TResult>> is created.
//if the curried function is called we overtake the p1 parameter (first parameter)
//and get back a Func<T2, TResult> func delegate.
//if we now call the returned Func<T2, TResult> with parameter p2 (second parameter)
//we call the func function with p1 and p2. That works because p1 becomes a closure and
//so we can use it in the second call.
public static Func<T1, Func<T2, TResult>>
    CurryAnonym<T1, T2, TResult>(this Func<T1, T2, TResult> func)
{
    return (Func<T1, Func<T2, TResult>>)delegate(T1 p1)
    {
        return (Func<T2, TResult>)delegate(T2 p2)
        {
            TResult tresult = func(p1, p2);
            return tresult;
        };
    };
}

//Currying a function with two parameters using lambda expressions
//the return type of the Func<T1, Func<T2, TResult>> delegate is explicite to
//make the return types clear. It works the same way a the CurryAnonym function
//but it uses lambda expressions instead of anonym methodes.
public static Func<T1, Func<T2, TResult>>
    Curry<T1, T2, TResult>(this Func<T1, T2, TResult> func)
{
    return new Func<T1, Func<T2, TResult>>(
            p1 => new Func<T2, TResult>(
                p2 => func(p1, p2)
                )
        );
}

//Currying a function with three parameters using lambda expressions
public static Func<T1, Func<T2, Func<T3, TResult>>>
    Curry<T1, T2, T3, TResult>(this Func<T1, T2, T3, TResult> func)
{
    return p1 => p2 => p3 => func(p1, p2, p3);
}

//Currying a function with four parameters using lambda expressions
public static Func<T1, Func<T2, Func<T3, Func<T4, TResult>>>>
    Curry<T1, T2, T3, T4, TResult>(this Func<T1, T2, T3, T4, TResult> func)
{
    return p1 => p2 => p3 => p4 => func(p1, p2, p3, p4);
}

//Uncurry a function with two parameters. Here we overtake the curried function
//and build a new Func<T1, T2, TResult> lambda function 
//that executes the curried function
public static Func<T1, T2, TResult>
    Uncurry<T1, T2, TResult>(this Func<T1, Func<T2, TResult>> func)
{
    return new Func<T1, T2, TResult>(
            (p1, p2) => func(p1)(p2)
        );
}

With this extension methodes it is easy to build a curried function. With the Uncarry extension method it is also possible to revoke the currying of a function.


Simulating a guard in c#

Currently i am reading a book about haskell programming and there is one chapter about guards. Because i like the concept of guards a lot i tried to implement one in c#. In this post you can see the result of my efforts. First of all i want to explain what a guard is and how you can implement one in haskell. So a guard is a pattern matching construct. You can define cases and when the overtaken value corresponds with the case then that case is choosen. This is the definition of a guard in Haskell:

guard :: Integer -> String
guard value
  | doublevalue <= 10 && value >= 0 = "small"
  | doublevalue <= 20 && value >= 0 = "middle"
  | doublevalue <= 30 && value >= 0 = "big"
  | otherwise = "not definied"
  where doublevalue = value * 2

If we call the guard with 2 the this:

 guard 2
 small

is the result. In haskell there is the where clause with this clause it is possible define additional values that can be used in the guard. In this case the value gets doubled and this doublevalue is used in the guard. In f# sharp there is also a construct that works like a guard but it is called match pattern. This is the definition of the match pattern (guard) in f#:

let guard v =
    match v with
    | v when v < 10 && v > 0 -> 1
    | v when v = 50 -> 2
    | v when v > 100 -> 3
    | _ -> 0

guard 2
1

I think that guards could also be a practical construct in c#. Here is my implementation of a c# guard like construct. To see if it works i wrote some test cases.

[TestClass]
public class GuardsTests
{
    [TestMethod]
    public void GuardsTestTrue()
    {
        int i = 2;
        var result = i.Match().
            When(v => v < 10, v => 1).
            When(v => v == 50, v => 2).
            When(v => v > 100, v => 3).
            Default(v => 0).Guard();
        Assert.AreEqual(result, 0);

        string value = "test";
        var resultTest = value.Match().
            When(s => s == "not test", s => "not test").
            When(s => s == "test", v => "test").
            Default(v => "no match").Guard();
        Assert.AreEqual(resultTest, "test");

        i = 25;
        int y = 2;
        var doubleresult = i.Match().Where<int>(x => x * y).
            When(v => v < 10, v => 1).
            When(v => v == 50, v => 2).
            When(v => v > 100, v => 3).
            Default(v => 0).Guard();
        Assert.AreEqual(doubleresult, 2);
    }
}

The Guards class is a generic class with two generic types. T is the type of the overtaken value and TResult is the result type. The When method is used to define the cases of the guard, the Default method defines the Default case.

// the Guards class stores the cases that are defined in the when, else and default clauses and
// when the Guard method is called all stored cases are evaluated and the result is calculated.
public class Guards<T, TResult>
{
    private readonly T value;

    // in this list of tuples all defined when cases are stored
    private List<Tuple<Predicate<T>, Func<T, TResult>>> patterns =
        new List<Tuple<Predicate<T>, Func<T, TResult>>>();

    private Tuple<Predicate<T>, Func<T, TResult>> elsePattern = null;
    // in this func the default case is stored
    private Func<T, TResult> defaultPattern = null;
    // in this func the where case is stored
    private Func<T, T> wherePattern = null;

    public Guards(T value)
    {
        this.value = value;
    }
    // every time the when method is called a tuple of a predicate and a result func is stored in 
    // the patterns list
    public Guards<T,TResult> When(Predicate<T> predicate, Func<T, TResult> result)
    {
        patterns.Add(new Tuple<Predicate<T>, Func<T, TResult>>(predicate, result));
        return this;
    }
    // with the where method it is possible to transform the overtaken value before it comes
    // evaluated
    public Guards<T, TResult> Where(Func<T, T> result)
    {
        wherePattern = result;
        return this;
    }

    public Guards<T, TResult> Else(Predicate<T> predicate, Func<T, TResult> result)
    {
        elsePattern = new Tuple<Predicate<T>, Func<T, TResult>>(predicate, result);
        return this;
    }
    // defines the default case
    public Guards<T, TResult> Default(Func<T, TResult> result)
    {
        defaultPattern = result;
        return this;
    }
    // the guard method evaluates the patterns. That means it calls the
    // predicate definied for the pattern and if the pedicate is true it
    // calles the func defined in the tuple. If no pattern matches the predicate
    // then the default pattern is called.
    public TResult Guard()
    {
        if(elsePattern != null)
            patterns.Add(elsePattern);
        if (wherePattern != null)
        {
            var whereValue = wherePattern(value);
            foreach (var item in patterns)
            {
                if (item.Item1(whereValue))
                {
                    return item.Item2(whereValue);
                }
            }
        }
        else
        {
            foreach (var item in patterns)
            {
                if (item.Item1(value))
                {
                    return item.Item2(value);
                }
            }
        }
        if (defaultPattern != null)
            return defaultPattern(value);
        throw new GuardException();
    }
}

The GuardExtensions class definies the Match method that generates a GuardContext object and overtakes the value the Guard should evaluate.

public static class GuardExtensions
{
    public static GuardContext<T> Match<T>(this T value)
    {
        return new GuardContext<T>(value);
    }
}

The GuardContext class defines the connection between the overtaken value that comes from the Match extension method and the Guards object.
// The GuardContext class holds the value that is evaluated
// and is the starting point for the chain of Guards that evaluates the value.
// the GuardContext is nessecary because it has one generic class type T that defines the type of
// the value and the methodes Where, When and Default have the generic TResult type that defines the
// result type of the chaining Methodes. It is the connection between the overtaken value and the Guards object.
// so if the expression:
// string stringResult =
// 10.Match().When(x => x < 10, x => “klein”).When(x => x >= 10, x => “big”).Guard();
// is evaluated the following things happen:
// 1. the extension method Match is called for 10
// 2. in the Match method a GuardContext Object is created and returned
// 3. the when method of the GuardContext Object is called
// 4. a Guards object is created the value is overtaken to this Guard
// and the When method of this object is called
// 5. the predicate and the result func are stored in the patterns collection of the Guards object
// and the Guards object is returned.
// 6. then the When method of the Guards object is executed the predicate and the result func are
// stored in the patterns collection (now the Guard object has two pattern entries).
// 7. The Guard method of the Guard object is called
// and the entries made in the patterns collection are executed with the value
// stored in the Guard object and return a TResult of type string to the stringResult

public classGuardContext<T>
{
    private T value;

    public GuardContext(T value)
    {
        this.value = value;
    }

    public Guards<T, TResult> Where<TResult>(Func<T, T> result)
    {
        var match = new Guards<T, TResult>(value);
        return match.Where(result);
    }
    // the when method generates a Guards object and overtakes the value to this Guards object.
    // After that it executes the When method of the Guards object and starts the evaluation chain also
    // called a Guard.
    public Guards<T, TResult> When<TResult>(Predicate<T> predicate, Func<T, TResult> result)
    {
        var match = new Guards<T, TResult>(value);
        return match.When(predicate, result);
    }
    public Guards<T, TResult> Default<TResult>(Func<T, TResult> result)
    {
        var match = new Guards<T, TResult>(value);
        return match.Default(result);
    }
}

So my self defined Guard in c# is not so beautiful as in haskell or f# but it served its purpose.