First, let's look at the simpler form of lambda expressions; that is, the ones without a statement block. As mentioned in the previous section, a lambda expression is a shorthand way of declaring a simple anonymous method. The following lambda expression can be used as a delegate that accepts one parameter and returns the result of performing division by 2 on that parameter:

x => x / 2

What this says is "take x as a parameter and return the result of following operation on x." Notice that the lambda expression is devoid of any type information. It does not mean that the expression is typeless. Instead, the compiler will deduce the type of the argument x and the type of the result depending on the context where it is used. It means that if you are assigning a lambda expression to a delegate, the types of the delegate definition are used to determine the types within the lambda expression. The following code shows what happens when a lambda expression is assigned to a delegate type:

using System;
using System.Linq;

public class LambdaTest
{
    static void Main() {
        Func<int, double> expr = x => x / 2;

        int someNumber = 9;
        Console.WriteLine( "Result: {0}", expr(someNumber) );
    }
}

I have marked the lambda expression in bold so that it stands out. The Func<> type is a helper type provided by the System namespace that you can use to declare simple delegates that take up to four arguments and return a result. In this case, I am declaring a variable expr that is a delegate that accepts an int and returns a double. When the compiler assigns the lambda expression to the expr variable, it uses the type information of the delegate to determine that the type of x must be int, and the type of the return value must be double.

Now, if you execute that code, you'll notice that the result is not entirely accurate. That is, the result has been rounded. This is expected because the result of x/2 is represented as an int, which is then cast to a double. You can fix this by specifying different types in the delegate declaration, as shown here:

using System;
using System.Linq;

public class LambdaTest
{
    static void Main() {
        Func<double, double> expr = (double x) => x / 2;

        int someNumber = 9;
        Console.WriteLine( "Result: {0}", expr(someNumber) );
    }
}

For the sake of demonstration, this lambda expression has what's called an explicitly typed parameter list, and in this case, x is declared as type double. Also notice that the type of expr is now Func<double, double> rather than Func<int, double>. The compiler requires that any time you use a typed parameter list in a lambda expression and assign it to a delegate, the delegate's argument types must match exactly. However, because an int is explicitly convertible to a double, you can pass someNumber to expr at call time as shown.

When the lambda expression is assigned to a delegate, the return type of the expression is generally derived from the argument types. So, in the following code statement, the return type of the expression is double because the inferred type of the parameter x is double:

Func<double, int> expr = (x) => x / 2;   // Compiler Error!!!!

However, because double is not implicitly convertible to int, the compiler will complain:

error CS1662: Cannot convert 'lambda expression' to

delegate type 'System.Func<double,int>' because some of the return

types in the block are not implicitly convertible to the delegate return

type

You can "fix" this by casting the result of the lambda expression body to int:

Func<double, int> expr = (x) => (int) x / 2;

Now I want to show you a simple lambda expression that accepts no parameters:

using System;
using System.Linq;

public class LambdaTest
{
    static void Main() {
        int counter = 0;

        WriteStream( () => counter++ );

        Console.WriteLine( "Final value of counter: {0}",
                           counter );
    }

    static void WriteStream( Func<int> generator ) {
        for( int i = 0; i < 10; ++i ) {
            Console.Write( "{0}, ", generator() );
        }
        Console.WriteLine();
    }
}

Notice how simple it was to pass a function as a parameter into the WriteStream method using this lambda expression. Moreover, the function passed in captures an environment within which to run, namely, the counter value in Main. This captured environment and the function together are commonly referred to as a closure.

Finally, I want to show you an example of a lambda expression that accepts more than one parameter:

using System;
using System.Linq;
using System.Collections.Generic;

public class LambdaTest
{
    static void Main() {
        var teamMembers = new List<string> {
            "Lou Loomis",
            "Smoke Porterhouse",
            "Danny Noonan",
            "Ty Webb"
        };

        FindByFirstName( teamMembers,
                         "Danny",
                         (x, y) => x.Contains(y) );
    }

    static void FindByFirstName(
                        List<string> members,
                        string firstName,
                        Func<string, string, bool> predicate ) {
        foreach( var member in members ) {
            if( predicate(member, firstName) ) {
                Console.WriteLine( member );
            }
        }
    }
}

In this case, the lambda expression is used to create a delegate that accepts two parameters of type string and returns a bool. As you can see, lambda expressions provide a nice, succinct way of creating predicates. In a later section, "Iterators Revisited," I'll build upon an example from Chapter 14 showing how to use lambda expressions as predicates to create flexible iterators.

using System;

unsafe public class MyClosure
{
    public MyClosure( int* counter )
    {
        this.counter = counter;
    }

    public delegate int IncDelegate();
    public IncDelegate GetDelegate() {
        return new IncDelegate( IncrementFunction );
    }

private int IncrementFunction() {
        return (*counter)++;
    }

    private int* counter;
}

public class LambdaTest
{
    unsafe static void Main() {
        int counter = 0;

        MyClosure closure = new MyClosure( &counter );

        WriteStream( closure.GetDelegate() );

        Console.WriteLine( "Final value of counter: {0}",
                           counter );
    }

    static void WriteStream( MyClosure.IncDelegate incrementor ) {
        for( int i = 0; i < 10; ++i ) {
            Console.Write( "{0}, ", incrementor() );
        }
        Console.WriteLine();
    }
}

using System;

public class LambdaTest
{
    static void Main() {
        int counter = 0;

        WriteStream( delegate () {
                        return counter++;
                     } );

        Console.WriteLine( "Final value of counter: {0}",
                           counter );
    }

    static void WriteStream( Func<int> counter ) {
        for( int i = 0; i < 10; ++i ) {
            Console.Write( "{0}, ", counter() );
        }
        Console.WriteLine();
    }
}

All the lambda expressions I have shown so far have been purely of the expression type. Another type of lambda expression is one I like to call a lambda statement. It is similar in form to the lambda expressions of the previous section except that it is composed of a compound statement block within curly braces. Because of that, a lambda with statement blocks must have a return statement. In general, all lambda expressions shown in the previous section can be converted to a lambda with a statement block simply by surrounding the expression with curly braces after prefixing the right side with a return statement. For example, the following lambda expression:

(x, y) => x * y

can be rewritten as the following lambda with a statement block:

(x, y) => { return x * y; }

In form, lambdas with statement blocks are almost identical to anonymous methods. But there is one major difference between lambdas with statement blocks and lambda expressions. Lambdas with statement blocks can be converted only to delegate types, whereas lambda expressions can be converted both to delegates and to expression trees typed by the family of types centered around System.Linq.Expressions.Expression<T>. I'll discuss expression trees in the next section.

Now I want to show you an example of how you can take an expression tree generated from a lambda expression and modify it to create a new expression tree. In this case, I will take the expression (n+1) and turn it into 2*(n+1):

using System;
using System.Linq;
using System.Linq.Expressions;

public class EntryPoint
{
    static void Main() {
        Expression<Func<int,int>> expr = n => n+1;

// Now, reassign the expr by multiplying the original
        // expression by 2.
        expr = Expression<Func<int,int>>.Lambda<Func<int,int>>(
                  Expression.Multiply( expr.Body,
                                       Expression.Constant(2) ),
                  expr.Parameters );

        Func<int, int> func = expr.Compile();

        for( int i = 0; i < 10; ++i ) {
            Console.WriteLine( func(i) );
        }

    }
}

The bolded lines show the stage at which I multiply the original lambda expression by 2. It's very important to notice that the parameters passed into the Lambda<> method (the second parameter) need to be exactly the same instances of the parameters that come from the original expression; that is, expr.Parameters. This is required. You cannot pass a new instance of ParameterExpression to the Lambda<> method; otherwise, at run time you will receive an exception similar to the following because the new ParameterExpression instance, even though it might have the same name, is actually a different parameter instance:

System.InvalidOperationException: Lambda Parameter not in scope

There are many classes derived from the Expression class and many static methods for creating instances of them and combining other expressions. It would be monotonous for me to describe them all here. Therefore, I recommend that you refer to the MSDN Library documentation regarding the System.Linq.Expressions namespace for all the fantastic details.

If you have ever studied functional languages such as Lisp, you might notice the similarities between expression trees and how Lisp and similar languages represent functions as data structures. Most people encounter Lisp in an academic environment, and many times concepts that one learns in academia are not directly applicable to the real world. But before you eschew expression trees as merely an academic exercise, I want to point out how they are actually very useful.

As you might already guess, within the scope of C#, expression trees are extremely useful when applied to LINQ. I will give a full introduction to LINQ in Chapter 16, but for our discussion here, the most important fact is that LINQ provides a language-native, expressive syntax for describing operations on data that are not naturally modeled in an object-oriented way. For example, you can create a LINQ expression to search a large in-memory array (or any other IEnumerable type) for items that match a certain pattern. LINQ is extensible and can provide a means of operating on other types of stores, such as XML and relational databases. In fact, out of the box, C# supports LINQ to SQL, LINQ to Dataset, LINQ to Entities, LINQ to XML, and LINQ to Objects, which collectively allow you to perform LINQ operations on any type that supports IEnumerable.

So how do expression trees come into play here? Imagine that you are implementing LINQ to SQL to query relational databases. The user's database could be half a world away, and it might be very expensive to perform a simple query. On top of that, you have no way of judging how complex the user's LINQ expression might be. Naturally, you want to do everything you can to provide the most efficient experience possible.

If the LINQ expression is represented in data (as an expression tree) rather than in IL (as a delegate), you can operate on it. Maybe you have an algorithm that can spot places where an optimization can be utilized, thus simplifying the expression. Or maybe when your implementation analyzes the expression, you determine that the entire expression can be packaged up, sent across the wire, and executed in its entirety on the server.

Expression trees give you this important capability. Then, when you are finished operating on the data, you can translate the expression tree into the final executable operation via a mechanism such as the LambdaExpression.Compile method and go. Had the expression only been available as IL code from the beginning, your flexibility would have been severely limited. I hope now you can appreciate the true power of expression trees in C#.

I've described how you can create custom iterators with C# in a couple of places in this book already.^[65] Now I want to demonstrate how you can use lambda expressions to create custom iterators. The point I want to stress is how the code implementing the algorithm, in this case the iteration algorithm, is then factored out into a reusable method that can be applied in almost any scenario.

I want to show how you can iterate over a generic type that might or might not be a collection in the strict sense of the word. Additionally, you can externalize the behavior of the iteration cursor as well as how to access the current value of the collection. With a little thought, you can factor out just about everything from the custom iterator creation method, including the type of the item stored, the type of the cursor, the start state of the cursor, the end state of the cursor, and how to advance the cursor. All these are demonstrated in the following example, in which I iterate over the diagonal of a two-dimensional array:

using System;
using System.Linq;
using System.Collections.Generic;

public static class IteratorExtensions
{
    public static IEnumerable<TItem>
        MakeCustomIterator<TCollection, TCursor, TItem>(
                     this TCollection collection,
                     TCursor cursor,
                     Func<TCollection, TCursor, TItem> getCurrent,
                     Func<TCursor, bool> isFinished,
                     Func<TCursor, TCursor> advanceCursor) {
        while( !isFinished(cursor) ) {
            yield return getCurrent( collection, cursor );
            cursor = advanceCursor( cursor );
        }
    }
}

public class IteratorExample
{
    static void Main() {
        var matrix = new List<List<double>> {
            new List<double> { 1.0, 1.1, 1.2 },
            new List<double> { 2.0, 2.1, 2.2 },
            new List<double> { 3.0, 3.1, 3.2 }
        };

        var iter = matrix.MakeCustomIterator(
                     new int[] { 0, 0 },
                     (coll, cur) => coll[cur[0]][cur[1]],
                     (cur) => cur[0] > 2 || cur[1] > 2,
                     (cur) => new int[] { cur[0] + 1,
                                          cur[1] + 1 } );

        foreach( var item in iter ) {
            Console.WriteLine( item );
        }
    }
}

Let's look at how reusable MakeCustomIterator<> is. Admittedly, it takes some time to get used to the lambda syntax, and those used to reading imperative coding styles might find it hard to follow. Notice that it takes three generic type arguments. TCollection is the type of the collection, which in this example is specified as List<List<double>> at the point of use. TCursor is the type of the cursor, which in this case is a simple array of integers that can be considered coordinates of the matrix variable. And TItem is the type that the code returns via the yield statement. The rest of the type arguments to MakeCustomIterator<> are delegate types that it uses to determine how to iterate over the collection.

First, it needs a way to access the current item in the collection, which, for this example, is expressed in the following lambda expression which uses the values within the cursor array to index the item within the matrix:

(coll, cur) => coll[cur[0]][cur[1]]

Then it needs a way to determine whether you have reached the end of the collection, for which I supply the following lambda expression that just checks to see whether the cursor has stepped off of the edge of the matrix:

(cur) => cur[0] > 2 || cur[1] > 2

And finally it needs to know how to advance the cursor, which I have supplied in the following lambda expression, which simply advances both coordinates of the cursor:

(cur) => new int[] { cur[0] + 1, cur[1] + 1 }

After executing the preceding code, you should see output similar to the following, which shows that you have indeed walked down the diagonal of the matrix from the top left to the bottom right. At each step along the way, MakeCustomIterator<> has delegated work to the given delegates to perform the work.

1

2.1

3.2

Other implementations of MakeCustomIterator<> could accept a first parameter of type IEnumerable<T>, which in this example would be IEnumerable<double>. However, when you impose that restriction, whatever you pass to MakeCustomIterator<> must implement IEnumerable<>. The matrix variable does implement IEnumerable<>, but not in the form that is easily usable, because it is IEnumerable<List<double>>. Additionally, you could assume that the collection implements an indexer, as described in the Chapter 4 section "Indexers," but to do so would be restricting the reusability of MakeCustomIterator<> and which objects you could use it on. In the previous example, the indexer is actually used to access the current item, but its use is externalized and wrapped up in the lambda expression given to access the current item.

Moreover, because the operation of accessing the current item of the collection is externalized, you could even transform the data in the original matrix variable as you iterate over it. For example, I could have multiplied each value by 2 in the lambda expression that accesses the current item in the collection, as shown here:

(coll, cur) => coll[cur[0]][cur[1]] * 2;

Can you imagine how painful it would have been to implement MakeCustomIterator<> using delegates in the C# 1.0 days? This is exactly what I mean when I say that even just the addition of the lambda expression syntax to C# opens one's eyes to the incredible possibilities.

As a final example, consider the case in which your custom iterator does not even iterate over a collection of items at all and is used as a number generator instead, as shown here:

using System;

using System.Linq;
using System.Collections.Generic;

public class IteratorExample
{
    static IEnumerable<T> MakeGenerator<T>( T initialValue,
                                            Func<T, T> advance ) {
        T currentValue = initialValue;
        while( true ) {
            yield return currentValue;
            currentValue = advance( currentValue );
        }
    }

    static void Main() {
        var iter = MakeGenerator<double>( 1,
                                          x => x * 1.2 );

        var enumerator = iter.GetEnumerator();
        for( int i = 0; i < 10; ++i ) {
            enumerator.MoveNext();
            Console.WriteLine( enumerator.Current );
        }
    }
}

After executing this code, you will see the following results:

1

1.2

1.44

1.728

2.0736

2.48832

2.985984

3.5831808

4.29981696

5.159780352

You could allow this method to run infinitely, and it would stop only if you experienced an overflow exception or you stopped execution. But the items you are iterating over don't exist as a collection; rather, they are generated on an as-needed basis each time you advance the iterator. You can apply this concept in many ways, even creating a random number generator implemented using C# iterators.

In the Chapter 10 section titled "Beware the Captured Variable Surprise," I described how anonymous methods can capture the contexts of their lexical surroundings. Many refer to this phenomenon as variable capture. In functional programming parlance, it's also known as a closure.^[66] Here is a simple closure in action:

using System;
using System.Linq;

public class Closures
{
    static void Main() {
        int delta = 1;
        Func<int, int> func = (x) => x + delta;

        int currentVal = 0;
        for( int i = 0; i < 10; ++i ) {
            currentVal = func( currentVal );
            Console.WriteLine( currentVal );
        }
    }
}

The variable delta and the delegate func embody the closure. The expression body references delta, and therefore must have access to it when it is executed at a later time. To do this, the compiler "captures" the variable for the delegate. Behind the scenes, what this means is that the delegate body contains a reference to the actual variable delta. But notice that delta is a value type on the stack. The compiler must be doing something to ensure that delta lives longer than the scope of the method within which is it declared because the delegate will likely be called later, after that scope has exited. Moreover, because the captured variable is accessible to both the delegate and the context containing the lambda expression, it means that the captured variable can be changed outside the scope and out of band of the delegate. In essence, two methods (Main and the delegate) both have access to delta. This behavior can be used to your advantage, but when unexpected, it can cause serious confusion.

Now I want to show you a great application of closures. One of the foundations of functional programming is that the function itself is treated as a first-class object that can be manipulated and operated upon as well as invoked. You've already seen how lambda expressions can be converted into expression trees so you can operate on them, producing more or less complex expressions. But one thing I have not discussed yet is the topic of using functions as building blocks for creating new functions. As a quick example of what I mean, consider two lambda expressions:

x => x * 3
x => x + 3.1415

You could create a method to combine such lambda expressions to create a compound lambda expression as I've shown here:

using System;
using System.Linq;

public class Compound
{
    static Func<T, S> Chain<T, R, S>( Func<T, R> func1,
                                      Func<R, S> func2 ) {
        return x => func2( func1(x) );
    }

    static void Main() {
        Func<int, double> func = Chain( (int x) => x * 3,
                                        (int x) => x + 3.1415 );

        Console.WriteLine( func(2) );
    }
}

The Chain<> method accepts two delegates and produces a third delegate by combining the two. In the Main method, you can see how I used it to produce the compound expression. The delegate that you get after calling Chain<> is equivalent to the delegate you get when you convert the following lambda expression into a delegate:

x => (x * 3) + 3.1415

Having a method to chain arbitrary expressions like this is useful indeed, but let's look at other ways to produce a derivative function. Imagine an operation that takes a really long time to compute. Examples are the factorial operation or the operation to compute the n^th Fibonacci number. An example that I ultimately like to show demonstrates the Reciprocal Fibonacci constant, which is

where F_k is a Fibonacci number.^[67]

To begin to demonstrate that this constant exists computationally, you need to first come up with an operation to compute the n^th Fibonacci number:

using System;
using System.Linq;

public class Proof
{
    static void Main() {
        Func<int, int> fib = null;
        fib = (x) => x > 1 ? fib(x-1) + fib(x-2) : x;

        for( int i = 30; i < 40; ++i ) {
            Console.WriteLine( fib(i) );
        }
    }
}

When you look at this code, the first thing that jumps up and grabs you is the formation of the Fibonacci routine; that is, the fib delegate. It forms a closure on itself! This is definitely a form of recursion and behavior that I desire. However, if you execute the example, unless you have a powerhouse of a machine, you will notice how slow it is, even though all I did was output the 30^th to 39^th Fibonacci numbers! If that is the case, you don't even have a prayer of demonstrating the Fibonacci constant. The slowness comes from the fact that for each Fibonacci number that you compute, you have to do a little more work than you did to compute the two prior Fibonacci numbers, and you can see how this work quickly mushrooms.

You can solve this problem by trading a little bit of space for time by caching the Fibonacci numbers in memory. But instead of modifying the original expression, let's look at how to create a method that accepts the original delegate as a parameter and returns a new delegate to replace the original. The ultimate goal is to be able to replace the first delegate with the derivative delegate without affecting the code that consumes it. One such technique is called memorization.^[68] This is the technique whereby you cache function return values and each return value's associated input parameters. This works only if the function has no entropy, meaning that for the same input parameters, it always returns the same result. Then, prior to calling the actual function, you first check to see whether the result for the given parameter set has already been computed and return it rather than calling the function. Given a very complex function, this technique trades a little bit of memory space for significant speed gain.

Let's look at an example:

using System;
using System.Linq;
using System.Collections.Generic;

public static class Memoizers
{
    public static Func<T,R> Memoize<T,R>( this Func<T,R> func ) {
        var cache = new Dictionary<T,R>();
        return (x) => {
            R result = default(R);
            if( cache.TryGetValue(x, out result) ) {
                return result;
            }

            result = func(x);
            cache[x] = result;
            return result;
        };
    }
}

public class Proof
{
    static void Main() {
        Func<int, int> fib = null;
        fib = (x) => x > 1 ? fib(x-1) + fib(x-2) : x;
        fib = fib.Memoize();

        for( int i = 30; i < 40; ++i ) {
            Console.WriteLine( fib(i) );
        }
    }
}

First of all, notice that in Main, I have added only one more statement where I apply the Memoize<> extension method to the delegate to produce a new delegate. Everything else stays the same, so the transparent replaceability goal is achieved. The Memoize<> method wraps the original delegate that's passed in via the func argument with another closure that includes a Dictionary<> instance to store the cached values of the given delegate func. In the process of Memoize<> taking one delegate and returning another, it has introduced a cache that greatly improves the efficiency. Each time the derivative delegate is called, it first checks the cache to see whether the value has already been computed.

Run the two previous examples on your own machine to see the amazing difference. Now you can move on to the business of computing the Reciprocal Fibonacci constant by modifying the Main method as follows:

static void Main() {
    Func<ulong, ulong> fib = null;
    fib = (x) => x > 1 ? fib(x-1) + fib(x-2) : x;
    fib = fib.Memoize();

    Func<ulong, decimal> fibConstant = null;
    fibConstant = (x) => {
        if( x == 1 ) {
            return 1 / ((decimal)fib(x));
        } else {
            return 1 / ((decimal)fib(x)) + fibConstant(x-1);
        }
    };
    fibConstant = fibConstant.Memoize();

    Console.WriteLine( "
{0}	{1}	{2}	{3}
",
                       "Count",
                       "Fibonacci".PadRight(24),
                       "1/Fibonacci".PadRight(24),
                       "Fibonacci Constant".PadRight(24) );

    for( ulong i = 1; i <= 93; ++i ) {
        Console.WriteLine( "{0:D5}	{1:D24}	{2:F24}	{3:F24}",
                           i,
                           fib(i),
                           (1/(decimal)fib(i)),
                           fibConstant(i) );
    }
}

The bold text shows the delegate I created to compute the n^th Reciprocal Fibonacci constant. As you call this delegate with higher and higher values for x, you should see the result get closer and closer to the Reciprocal Fibonacci constant. Notice that I memoized the fibConstant delegate as well. If you don't do this, you might suffer a stack overflow due to the recursion as you call fibConstant with higher and higher values for x. So you can see that memoization also trades stack space for heap space. On each line of output, the code outputs the intermediate values for informational purposes, but the interesting value is in the far right column. Notice that I stopped calculation with iteration number 93. That's because the ulong will overflow with the 94^th Fibonacci number. I could solve the overflow problem by using BigInteger in the System.Numeric namespace. However, that's not necessary because the 93^rd iteration of the Reciprocal Fibonacci constant shown here is close enough to prove the point of this example:

3.359885666243177553039387

I have bolded the digits that are significant.^[69] I think you will agree that memoization is extremely useful. For that matter, many more useful things can be done with methods that accept functions and produce other functions, as I'll show in the next section.

In the previous section on closures I demonstrated how to create a method that accepts a function, given as a delegate, and produces a new function. This concept is a very powerful one and memoization, as shown in the previous section, is a powerful application of it. In this section, I want to show you the technique of currying.^[70] In short, what it means is creating an operation (usually a method) that accepts a function of multiple parameters (usually a delegate) and produces a function of only a single parameter.

Suppose that you have a lambda expression that looks like the following:

(x, y) => x + y

Now, suppose that you have a list of doubles and you want to use this lambda expression to add a constant value to each item on the list, producing a new list. What would be nice is to create a new delegate based on the original lambda expression in which one of the variables is forced to a static value. This notion is called parameter binding, and those who have used STL in C++ are likely very familiar with it. Check out the next example, in which I show parameter binding in action by adding the constant 3.2 to the items in a List<double> instance:

using System;
using System.Linq;
using System.Collections.Generic;

public static class CurryExtensions
{
    public static Func<TArg1, TResult>
        Bind2nd<TArg1, TArg2, TResult>(
            this Func<TArg1, TArg2, TResult> func,
            TArg2 constant ) {
        return (x) => func( x, constant );
    }

}

public class BinderExample
{
    static void Main() {
        var mylist = new List<double> { 1.0, 3.4, 5.4, 6.54 };
        var newlist = new List<double>();

        // Here is the original expression.
        Func<double, double, double> func = (x, y) => x + y;

        // Here is the curried function.
        var funcBound = func.Bind2nd( 3.2 );

        foreach( var item in mylist ) {
            Console.Write( "{0}, ", item );
            newlist.Add( funcBound(item) );
        }

        Console.WriteLine();
        foreach( var item in newlist ) {
            Console.Write( "{0}, ", item );
        }
    }
}

The meat of this example is in the Bind2nd<> extension method, which I have bolded. You can see that it creates a closure and returns a new delegate that accepts only one parameter. Then, when that new delegate is called, it passes its only parameter as the first parameter to the original delegate and passes the provided constant as the second parameter. For the sake of example, I iterate through the mylist list, building a second list held in the newlist variable while using the curried version of the original method to add 3.2 to each item.

Just for good measure, I want to show you another way you can perform the currying, slightly different from that shown in the previous example:

using System;
using System.Linq;
using System.Collections.Generic;

public static class CurryExtensions
{
    public static Func<TArg2, Func<TArg1, TResult>>
        Bind2nd<TArg1, TArg2, TResult>(
            this Func<TArg1, TArg2, TResult> func ) {
        return (y) => (x) => func( x, y );
    }
}

public class BinderExample
{
    static void Main() {
        var mylist = new List<double> { 1.0, 3.4, 5.4, 6.54 };
        var newlist = new List<double>();

// Here is the original expression.
        Func<double, double, double> func = (x, y) => x + y;

        // Here is the curried function.
       var funcBound = func.Bind2nd()(3.2);

        foreach( var item in mylist ) {
            Console.Write( "{0}, ", item );
            newlist.Add( funcBound(item) );
        }

        Console.WriteLine();
        foreach( var item in newlist ) {
            Console.Write( "{0}, ", item );
        }
    }
}

I have bolded the parts that are different from the previous example. In the first example, Bind2nd<> returned a delegate that accepted a single integer and returned an integer. In this example, I changed Bind2nd<> to return a delegate that accepts a single parameter (the value to bind the second parameter of the original function to) and returns another delegate that is the curried function. Both forms are perfectly valid. But the purists might prefer the second form over the former.

In the earlier section titled "Closures (Variable Capture) and Memoization," I showed a form of recursion using closures while calculating the Fibonacci numbers. For the sake of discussion, let's look at a similar closure that one can use to calculate the factorial of a number:

Func<int, int> fact = null;
fact = (x) => x > 1 ? x * fact(x-1) : 1;

This code works because fact forms a closure on itself and also calls itself. That is, the second line, in which fact is assigned the lambda expression for the factorial calculation, captures the fact delegate itself. Even though this recursion works, it is extremely fragile, and you must be very careful when using it as written because of reasons I will describe now.

Remember that even though a closure captures a variable for use inside the anonymous method, which is implemented here as a lambda expression, the captured variable is still accessible and mutable from outside the context of the capturing anonymous method or lambda expression. For example, consider what happens if you perform the following:

Func<int, int> fact = null;
fact = (x) => x > 1 ? x * fact(x-1) : 1;
Func<int, int> newRefToFact = fact;

Because objects in the CLR are reference types, newRefToFact and fact now reference the same delegate. Now, imagine that you then do something similar to this:

Func<int, int> fact = null;

fact = (x) => x > 1 ? x * fact(x-1) : 1;
Func<int, int> newRefToFact = fact;
fact = (x) => x + 1;

Now the intended recursion is broken! Can you see why? The reason is that we modified the captured variable fact. We reassigned fact to reference a new delegate based on the lambda expression (x) => x+1. But newRefToFact still references the lambda expression (x) => x > 1 ? x * fact(x-1) : 1. However, when the delegate referenced by newRefToFact calls fact, instead of recursing, it ends up executing the new expression (x) => x+1, which is different behavior from the recursion you had before. Ultimately, the problem is caused by the fact that the closure that embodies the recursion allows you to modify the captured variable (the func delegate) externally. If the captured variable is changed, the recursion could break.

There are several ways to fix this problem, but the typical method is to use anonymous recursion.^[71] What ends up happening is that you modify the preceding factorial lambda expression to accept another parameter, which is the delegate to call when it's time to recurse. Essentially, this removes the closure and converts the captured variable into a parameter to the delegate. What you end up with is something similar to the following:

delegate TResult AnonRec<TArg,TResult>( AnonRec<TArg,TResult> f, TArg arg );
AnonRec<int, int> fact = (f, x) => x > 1 ? x * f(f, x-1) : 1;

The key here is that instead of recursing by relying on a captured variable that is a delegate, you instead pass the delegate to recurse on as a parameter. That is, you traded the captured variable for a variable that is passed on the stack (in this case, the parameter f in the fact delegate). In this example, the recursion delegate is represented by the parameter f. Therefore, notice that fact not only accepts f as a parameter, but calls it in order to recurse and then passes f along to the next iteration of the delegate. In essence, the captured variable now lives on the stack as it is passed to each recursion of the expression. However, because it is on the stack, the danger of it being modified out from underneath the recursion mechanism is now gone.

For more details on this technique, I strongly suggest that you read Wes Dyer's blog entry titled "Anonymous Recursion in C#" at http://blogs.msdn.com/wesdyer. In his blog entry he demonstrates how to implement a Y fixed-point combinator that generalizes the notion of anonymous recursion shown previously.^[72]