วันเสาร์ที่ 12 มกราคม พ.ศ. 2551

Extension Methods for Delegate Types

The great resource, that I highly recommend you to read is Wesdyer's blog. His blog contains much information about Functional Programming in C#. Articles you should read that relate to this post are Function Memoization and Partial Function Application.

Put this code onto your extension class (source: Wesdyer's blog).

public static Func<T, TResult> Memoize<T, TResult>(this Func<T, TResult> func) {
    var dict = new Dictionary<T, TResult>();
    return arg => {
        TResult value;
        if (!dict.TryGetValue(arg, out value)) {
            value = func(arg);
            dict.Add(arg, value);
        }
        return value;
    };
}
public static Func<T2, TResult> Partial<T1, T2, TResult>(this Func<T1, T2, TResult> func, T1 arg1) {
    return arg2 => func(arg1, arg2);
}


Function Memoization is technic to speed up repeating calculation by storing arguments and result.

Compare this simple fibonacci function

Func<int, int> fib = null;
fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;
Console.WriteLine(fib(38));
//39088169
//2.35 seconds


with memoized fibonacci

Func<int, int> fib = null;
fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;
fib = fib.Memoize();
Console.WriteLine(fib(38));
//39088169
//0.01 second


Memoized function performs much faster. Just add only 1 line of code.

Partial Function Application is to define an argument of a function and create another function with remaining argument.

Here is an example.

Func<int, int, int> gcd = null;
gcd = (x, y) => (y == 0) ? x : gcd(y, x % y);
Func<int, int> gcdBy20 = gcd.Partial(20);
var max = 1.To(15).Max(gcdBy20);
//max = 10


First, we declare Greatest Common Divisor (GCD) function. Then, we partial it and create new gcdBy20 function. This function takes only one argument and return greatest common divisor with 20. To use, we generate numbers 1 to 15, and find which value has maximum gcdBy20.

Now more extension methods by me.

public static Func<T1, T2, TResult> Memoize<T1, T2, TResult>(this Func<T1, T2, TResult> func) {
    var dict = new Dictionary<T1, Func<T2, TResult>>();
    return (arg1, arg2) => {
        Func<T2, TResult> value;
        if (!dict.TryGetValue(arg1, out value)) {
            value = func.Partial(arg1).Memoize();
            dict.Add(arg1, value);
        }
        return value(arg2);
    };
}
public static Func<T, bool> And<T>(this Func<T, bool> predicate1, Func<T, bool> predicate2) {
    return arg => predicate1(arg) && predicate2(arg);
}
public static Func<T, bool> Or<T>(this Func<T, bool> predicate1, Func<T, bool> predicate2) {
    return arg => predicate1(arg) || predicate2(arg);
}
public static Func<T, TResult> When<T, TResult>(this Func<T, TResult> func, Func<T, bool> predicate, Func<T, TResult> alternative) {
    return arg => predicate(arg) ? alternative(arg) : func(arg);
}
public static Func<T1, T2, TResult> When<T1, T2, TResult>(this Func<T1, T2, TResult> func, Func<T1, T2, bool> predicate, Func<T1, T2, TResult> alternative) {
    return (arg1, arg2) => predicate(arg1, arg2) ? alternative(arg1, arg2) : func(arg1, arg2);
}


Memoize function memorizes the result of function with 2 arguments. The first memoize function is able to memorize only 1 argument. If you notice, you can see that this Memoize function uses both Partial and previous Memoize functionality to memorize.

And/Or functions are simple. They takes a predicate and produce another predicate with And/Or logic.

Func<int, bool> predicate = x => x % 2 == 0;
predicate = predicate.And(x => x % 3 == 0);
predicate = predicate.And(x => x % 4 == 0);
var value = 1.To(20).Where(predicate);
//value = {12}


Example above, we create predicate function which find whether x is divisible by 2 And 3 And 4. Then generate numbers 1 to 20, and filter which numbers pass the predicate.

"When" function provides conditional to evaluate alternative expression if condition is met.

Func<int, int> fact = null;
fact = x => fact(x - 1) * x;
fact = fact.When(x => x == 0, x => 1);
Console.WriteLine(fact(10));
//3628800


Factorial function equal to factorial of x - 1 multiply by x. But "When" function creates alternation instruction, when x equal to 0, result will equal to 1.

A little bit more extension methods

public static Func<T, bool> PredicateAll<T>(this IEnumerable<Func<T, bool>> source) {
    using (var source_enum = source.GetEnumerator()) {
        if (!source_enum.MoveNext())
            return x => true;

        Func<T, bool> result = source_enum.Current;
        while (source_enum.MoveNext())
            result = result.And(source_enum.Current);
        return result;
    }
}
public static Func<T, bool> PredicateAny<T>(this IEnumerable<Func<T, bool>> source) {
    using (var source_enum = source.GetEnumerator()) {
        if (!source_enum.MoveNext())
            return x => false;

        Func<T, bool> result = source_enum.Current;
        while (source_enum.MoveNext())
            result = result.Or(source_enum.Current);
        return result;
    }
}


PredicateAll transforms list of predicates to a predicate that will be true if all predicates are true. On the other hand, PredicateAny create predicate that will be false if all predicates false.

List<Func<int, bool>> predicateList = new List<Func<int, bool>>();
predicateList.Add(x => x % 2 == 0);
predicateList.Add(x => x % 3 == 0);
predicateList.Add(x => x % 4 == 0);
var predicateAll = predicateList.PredicateAll();
var predicateAny = predicateList.PredicateAny();

var result = 1.To(20).Where(predicateAll);
//result = {12}
var result2 = 1.To(20).Where(predicateAny);
//result2 = {2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20}


Example above, predicateAll returns true only numbers that is divisible by 2, and 3, and 4 which is 12. predicateAny returns true for any numbers that is divisible by 2, or 3, or 4 which are 2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20.

Next post continue on extension methods.

ไม่มีความคิดเห็น: