Posted on 12/26/2007 1:04:26 PM by Justin Etheredge
In the previous post in this series we discussed currying and partial application with examples in two variables. We saw that with two variables partial application and currying look very similar. Currying just appears to have an extra step of creating the method that generates our partially applied methods, but this is actually somewhat deceptive. When going beyond two parameters we will start to see the differences in currying and partial application a little more clearly.
So, lets use a multiply method with a third parameter:
public static int Multiply(int a, int b, int c)
{
return a * b * c;
}
So, lets first look at an implementation of a Curry function with three arguments:
public static Func<TArg1, Func<TArg2, Func<TArg3, TResult>>>
Curry<TArg1, TArg2, TArg3, TResult>
(this Func<TArg1, TArg2, TArg3, TResult> func)
{
return argument1 => argument2 => argument3 =>
func(argument1, argument2, argument3);
}
You may already be seeing the differences here. With the currying method we are chaining these arguments together so that we build up new methods by passing in single arguments at a time. Here is how this would look when we used it:
Func<int, int, int, int> method = Multiply;
var curriedMultiply = method.Curry();
var multiplyByTwo = curriedMultiply(2);
var multiplyByTwoThenFive = multiplyByTwo(5);
var multiplyByTwoThenSix = multiplyByTwo(6);
int result1 = multiplyByTwoThenFive(10);
int result2 = multiplyByTwoThenSix(10);
You see what we are doing here? We have curried the method, then we build up our methods by calling our curried methods over and over but always with only one parameter! You can shorten it with a bit of somewhat confusing syntax:
Func<int, int, int, int> method = Multiply;
var curriedMultiply = method.Curry();
var multiplyByTwoThenFive = curriedMultiply(2)(5);
var multiplyByTwoThenSix = curriedMultiply(2)(6);
int result1 = multiplyByTwoThenFive(10);
int result2 = multiplyByTwoThenSix(10);
You may or may not find it hard to read, but we are just skipping the intermediate step by passing two parameters with the second one being passed to the return type. In this instance though you are bypassing the advantages of currying, which is the ability to slowly build up methods, and you might as well be using partial application. You'll see why in a second.
So, before we look at an implementation of a three parameter "PartiallyApply" method let me just say that there is more than one. When you think about it that makes sense. With two parameters "partially applied" can mean only one thing, that we have passed in one parameter. Otherwise it would be "unapplied" or "fully applied". :-) With three parameters though we can have one parameter pre-applied or two. So, here is our three parameter "PartiallyApply" methods:
public static Func<TArg2, TArg3, TResult>
PartiallyApply<TArg1, TArg2, TArg3, TResult>
(this Func<TArg1, TArg2, TArg3, TResult> func, TArg1 argument1)
{
return (argument2, argument3) =>
func(argument1, argument2, argument3);
}
public static Func<TArg3, TResult>
PartiallyApply<TArg1, TArg2, TArg3, TResult>
(this Func<TArg1, TArg2, TArg3, TResult> func,
TArg1 argument1, TArg2 argument2)
{
return argument3 => func(argument1, argument2, argument3);
}
There you have it, a three parameter "PartiallyApply" method that has been partially applied in two different ways. Here you can see how we use them:
Func<int, int, int, int> method = Multiply;
var needTwoMoreParams = method.PartiallyApply(2);
var needOneMoreParam = method.PartiallyApply(2, 5);
int result1 = needTwoMoreParams(5, 3);
int result2 = needOneMoreParam(3);
So easy! So, now you see how currying and partial application are actually quite different concepts. Currying is useful if you need to slowly build up your function over several different iterations while partial application is useful if you just need to set a few parameters on a function and the rest will be filled in later. While you will probably be able to find a few places where partial application may be useful, currying will probably be a bit harder to find a real world use for. If you have any good examples of using these in the real world, please leave a comment!
Posted on 12/24/2007 8:02:37 PM by Justin Etheredge
We are now finally back for Part 8 of my functional programming series. In this part of my series we are going to be discussing currying in C# 3.0. Currying is actually a mathematical term where you take a function with multiple parameters and turn it into a function with only one parameter. This is done by simply providing values for the parameters that you want to take away. You are probably thinking "Well, that is pretty simple." And quite frankly, the concept is simple. The execution gets a bit more tricky, but it isn't too bad. Especially if you have made it through this whole series.
Just like most of our other entries in this series, we are going to start off with a two argument multiply method to get our gears turning. This method looks like this:
public static int Multiply(int a, int b)
{
return a * b;
}
Now, our end goal is to supply a value for one of our arguments in order to make a function that only takes a single argument. So, the way we will do that is by creating an extension method that will operate on a two parameter delegate and will return a method which takes one parameter (This is our curried method). This new method will then take that parameter and return a new method that takes a single parameter, using the parameter that we passed to our curried method (this method is said to be "partially applied"). It sounds a lot more complex than it is, so lets first look at the usage to clear up what I said above.
//Put Multiply method into a delegate so we can use
//our extension method
Func<int, int, int> method = Multiply;
//Now curry our Multiply method
var curriedMultiply = method.Curry();
//Use the curried method to create
//partially applied methods
var doubler = curriedMultiply(2);
int result1 = doubler(5);
int result2 = doubler(10);
Hopefully that made what I was saying much more clear. Our curried method just generates partially applied methods. So in this case we generated a doubler, but we could have also generated a tripler or quadrupler. Lets look at the method that generates this method:
public static Func<TArg1, Func<TArg2, TResult>>
Curry<TArg1, TArg2, TResult>
(this Func<TArg1, TArg2, TResult> func)
{
return argument1 => argument2 => func(argument1, argument2);
}
Let's break this down so it doesn't look so crazy. First lets look at "Curry<TArg1, TArg2, TResult>" which is actually the generic method signature. This tells us that we have two arguments and a result type that need to be specified. In our case it is <int,int,int>. The extension method just takes a Func delegate with the same generic parameters as our method signature. Our multiply method works fine because it takes two args. The return type "Func<TArg1, Func<TArg2, TResult>>" is the interesting part. This just says that our extension method is returning a delegate that takes one parameter "TArg1" and then returns another delegate that also takes one parameter.
We accomplish this return type by chaining two lambdas together as you can see above. It may look weird, but argument1 and argument2 are just integer parameters. The inside lambda takes one parameter and returns a closure that is bound to argument2 from the outer lambda (Go back and check out earlier posts in the series for info on closures). So what you end up with is the outer lambda taking one parameter and then returning a closure that uses that parameter. It may look a bit more intuitive if I write it like this:
public static Func<TArg1, Func<TArg2, TResult>>
Curry<TArg1, TArg2, TResult>
(this Func<TArg1, TArg2, TResult> func)
{
return (TArg1 argument1) => {
return (TArg2 argument2) =>
{
return func(argument1, argument2);
};
};
}
Personally I think the lambda syntax is actually easier to read, but you should do what is the most clear for you and your team. In this new, updated version you can more clearly see that we are returning a closure that returns a closure that returns the result of our "func" method. So, the caller to our method will end up with a reference to the outermost closure.
So, now that we have succeeded in creating our curry method we have to ask ourselves, "do we really need it?" Instead of creating this curried method that generates all of our other methods, wouldn't it just be easier to pass our initial value to the curry method and get back a partially applied method right away? And the answer in this case is, yes, it would be. To do this we are going to create a method called "PartiallyApply." Here is how we are going to use this method:
Func<int, int, int> method = Multiply;
//Create our partially applied method
var doubler = method.PartiallyApply(2);
int result1 = doubler(5);
int result2 = doubler(10);
Essentially we are just turning it into one step. We are passing our value into the "PartiallyApply" method and we are getting back a method that can be called immediately to get a value. This method looks like this:
public static Func<TArg2, TResult>
PartiallyApply<TArg1, TArg2, TResult>
(this Func<TArg1, TArg2, TResult> func, TArg1 argument1)
{
return argument2 => func(argument1, argument2);
}
Here we are just passing in a delegate and a single argument, then we call our delegate with the value of the argument we passed in and return a method that takes the additional argument. This is much easier to use than our Curry method, and so you may be wondering why we would need the currying to begin with. Well, it all starts to become apparent when you graduate beyond two parameters.
This post is starting to get a bit a bit long-winded, so I am going to go ahead and stop there. We have seen how currying and partial application work in two parameters, and so far they seem to be very similar only that the currying seems to involve this useless middle step. When we return with Part 9 we are going to move beyond two parameters and show you why currying and partial application really aren't as alike as they may seem right now. So stay tuned!
Posted on 12/3/2007 10:48:21 PM by Justin Etheredge
In this entry in my C# functional programming series we are finishing up the topic of memoization. If you have not read part 6 then you need to go there and read it now. This entry is going to pick up in the middle of the topic.
In the last part of this series we left off with this method:
public static Func<int,int,int> CachedMultiply()
{
var cache = new Dictionary<Tuple<int,int>, int>();
return (int arg1, int arg2) =>
{
int result;
var arguments = new Tuple<int, int>()
{ One = arg1, Two = arg2 };
if (cache.TryGetValue(arguments, out result))
{
return result;
}
else
{
result = Multiply(arg1, arg2);
cache.Add(arguments, result);
return result;
}
};
}
We had finally gotten to the point where we had the ability to cache our multiply method with two variables, the only thing left to do is to make this generic. In order to do this, we are going to use generics! Instead of returning Func<int,int,int> from this method we are going to change it to be Func<TArg1,TArg2,TResult>, and then the method now gets a parameter so that we can pass the method to it that we are going to memoize. Here is the generic memoize function that has been converted from the method above.
public static Func<TArg1, TArg2, TResult>
Memoize<TArg1, TArg2, TResult>
(Func<TArg1, TArg2, TResult> func)
{
var cache = new Dictionary<Tuple<TArg1, TArg2>, TResult>();
return (TArg1 argument1, TArg2 argument2) =>
{
TResult result;
var arguments = new Tuple<TArg1, TArg2>
{ One = argument1, Two = argument2 };
if (cache.TryGetValue(arguments, out result))
{
return result;
}
else
{
result = func(argument1, argument2);
cache.Add(arguments, result);
return result;
}
};
}
Looks pretty similar, huh? All we really had to do is change all of our types to generic type arguments. So, how would we use this in order to memoize multiply?
var cachedMultiply = Memoize<int,int,int>(Multiply);
int result1 = cachedMultiply(2, 3);
int result2 = cachedMultiply(3, 4);
int result3 = cachedMultiply(2, 3);
It's a shame that we still have to pass the types to this method, but it is because of method overloading. Since you aren't passing any type information when you pass Multiply, you are passing a method group, the Memoize function needs to know which method to use. If you are interested in this, you can read more about at Eric Lippert's Blog. As you can see in the example though, we can now use this Memoize method for any method with two parameters. In order to do a three parameter memoize method, we just add another argument and use a 3-tuple. It would look like this:
public static Func<TArg1, TArg2, TArg3, TResult>
Memoize<TArg1, TArg2, TArg3, TResult>
(Func<TArg1, TArg2, TArg3, TResult> func)
{
var cache = new
Dictionary<Tuple<TArg1, TArg2, TArg3>, TResult>();
return (TArg1 argument1, TArg2 argument2, TArg3 argument3) =>
{
TResult result;
var arguments = new Tuple<TArg1, TArg2,TArg3>
{ One = argument1, Two = argument2, Three = argument3 };
if (cache.TryGetValue(arguments, out result))
{
return result;
}
else
{
result = func(argument1, argument2, argument3);
cache.Add(arguments, result);
return result;
}
};
}
It is identical to the two parameter version except for the addition of an extra type parameter. And this is what we want! We can now repeat this for as many parameters as we want. Since there is no way to really pass a Func with an arbitrary number of parameters, we are stuck with implementing one for every number of arguments. Now you may think that you can get around this with a parameter array, but not really. For example, lets say our method looked like this:
public static int Multiply(params int[] values)
{
if (values.Length == 0)
{
return 0;
}
int result = 1;
foreach (int i in values)
{
result *= i;
}
return result;
}
Which you would call like this:
int result = Multiply(2, 3, 5, 4);
This is just syntactic sugar though. The compiler just turns these variables into an array. So if we wanted to memoize this method call you would want do this:
var cachedMultiply = Memoize<int[], int>(Multiply);
int result = cachedMultiply(3, 4, 5, 6);
The only problem is that this doesn't work. The method is now seen as a method with a single array parameter, and we would have to call it like this:
var cachedMultiply = Memoize<int[], int>(Multiply);
int result = cachedMultiply(new int[] {3, 4, 5, 6});
Which isn't terrible, but not ideal either. The other downside to this is that all of the parameters have to have the same types.
Another thing that is also possible with the Memoize function is to make it an extension method. An extension method of what you say? Well, Func<TArg1,TArg2,TResult> of course! You will just change the func parameter to add "this" and there you go. It would end up looking like this:
public static Func<TArg1, TArg2, TResult>
Memoize<TArg1, TArg2, TResult>
(this Func<TArg1, TArg2, TResult> func)
{
var cache = new Dictionary<Tuple<TArg1, TArg2>, TResult>();
return (TArg1 argument1, TArg2 argument2) =>
{
TResult result;
var arguments = new Tuple<TArg1, TArg2>
{ One = argument1, Two = argument2 };
if (cache.TryGetValue(arguments, out result))
{
return result;
}
else
{
result = func(argument1, argument2);
cache.Add(arguments, result);
return result;
}
};
}
Calling it is a bit different from what we were doing before. The ideal method would be to just say "Multiply.Memoize()" but we can't because at this point because "Multiply" is not a delegate and even if it was we don't have the type info we need. So, in order to call it we have to cast Multiply:
var cachedMultiply = ((Func<int,int,int>)Multiply).Memoize();
var result1 = cachedMultiply(2, 3);
This may look clumsy when you are calling it like this, but if you have a method where a delegate is being passed in this will work very nice:
public void RunThis(Func<int, int, int> method)
{
var cachedMethod = method.Memoize();
cachedMethod(2, 3);
}
Wow, is this over yet? Thankfully yes. We have now completed my tutorial on memoization. We have seen how to make our Memoize method generic so that we can call it using any method, all we have to do is implement the memoize methods for each number of parameters into a library along with the tuples, and voila, we can use them wherever we need to. I hope you enjoyed this post, and I will be back soon with my next functional programming entry. I'm sure there are parts of this that are not clear, so please leave me a comment if you don't understand something!
If you liked it, please vote for it below!
Posted on 12/3/2007 2:26:39 AM by Justin Etheredge
So far in this series we have gone through closures, lambdas, higher-order functions, and then we have gone over the implementation of several higher order functions. We are now going to talk about a technique called memoization, which is a much easier concept to describe than it is to implement. What memoization does is it caches the return value of a function for each unique combination of arguments. It works for deterministic functions (functions that always return the same value for a given set of inputs) but will not work with non-deterministic functions (functions that will return different values for the same arguments) for obvious reasons. To start this off, I am going to show you very simple function called MultiplyByTwo. It has one parameters, an integer, and it returns an integer. It looks like this:
public int MultiplyByTwo(int a)
{
return a * 2;
}
Pretty complex, huh? Yeah, makes your brain hurt just staring at it. So anyways, if we wanted to do some ghetto "memoization like" behavior (also called caching), we could do this:
public class CachedMultiplier
{
Dictionary<int, int> cache = new Dictionary<int, int>();
public int MultiplyByTwo(int a)
{
int result;
if (cache.TryGetValue(a, out result))
{
return result;
}
else
{
result = a * 2;
cache.Add(a, result);
return result;
}
}
}
Notice that we have now added a class that we have to instantiate. We need this because we have to have our cache stick around between calls to "MultiplyByTwo". If we declared it inside of the method then it would be garbage collected between calls and this wouldn't provide much caching, now would it?
Sidenote:
Please ignore the fact that looking up a result in a Dictionary object and instantiating the CachedMultiplier takes longer than actually doing the multiplication. I am trying not to complicate the topic by introducing a more complex method into the mix.
So now if we wanted to do this without having an extra class to instantiate then we could just wrap it in another method, correct? Well, no, not really. The problem would be that even if we did something like this...
public int CachedMultiplyByTwo(int a)
{
var cache = new Dictionary<int, int>();
int result;
if (cache.TryGetValue(a, out result))
{
return result;
}
else
{
result = MultiplyByTwo(a);
cache.Add(a, result);
return result;
}
}
public int MultiplyByTwo(int a)
{
return a * 2;
}
We would still have the issue where cache goes out of scope between every call to CachedMultiplyByTwo. But is there a way around that? Sure there is! The answer is returning a delegate. Since a delegate is a closure, which means that it is bound to all of the methods local variables that it references, we can just return a delegate from this method like this:
public static Func<int,int> CachedMultiplyByTwo()
{
var cache = new Dictionary<int, int>();
return (int arg) =>
{
int result;
if (cache.TryGetValue(arg, out result))
{
return result;
}
else
{
result = MultiplyByTwo(arg);
cache.Add(arg, result);
return result;
}
};
}
public static int MultiplyByTwo(int a)
{
return a * 2;
}
Notice though that CachedMultiplyByTwo takes no parameters! How is it supposed to work then? Well, you also have to notice that we are no longer returning an "int" type, we are returning a type of Func<int,int>. As you saw in an earlier post, this is a shortcut for a delegate that takes a single int parameter and then returns an int. So, instead of actually calling this method to get your result, you call this method and it returns a function to you that you then use to multiply. You will notice the "return (int arg) =>", well this is a lambda and you'll see the curly braces after it that surrounds the body of the lambda. Once this lambda is returned it can be called like this:
var cachedMultiply = CachedMultiplyByTwo();
int result1 = cachedMultiply(5);
int result2 = cachedMultiply(3);
int result3 = cachedMultiply(5);
We call CachedMultiplyByTwo and put the result into the variable cachedMultiply. This is now our method that we are calling. The "cache" variable from the "CachedMultiplyByTwo" method is still bound to this method, so it is available until the local cachedMultiply variable goes out of scope. Here we call this newly returned method with 5, then 3, then 5 again. The second time we call it with 5 we are getting the cached result back out. Keep in mind that the result of each call to CachedMultiplyByTwo returns a new closure that is bound to different variables. So, if we called it twice, we would get two delegates with two different caches. In some instances this could be quite useful, but in other instances it might be unexpected. Take this for example:
var cachedMultiply = CachedMultiplyByTwo();
var cachedMultiply2 = CachedMultiplyByTwo();
int result1 = cachedMultiply(5);
int result2 = cachedMultiply2(5);
There would have been no cached results used in this instance. How sad.
Now all this is find and great, but what happens when we go to two variables. Lets look at this method:
public static int Multiply(int a, int b)
{
return a * b;
}
So, once we have two variables, how do we store them in our dictionary? Well, we could convert them to strings and concatenate them, but I don't really like that solution. There are a few other ways we could do it, but I am going to borrow another concept that is often used in function languages, tuples. Now tuples have nothing really to do with functional languages, they are just generic holders for variables or objects, but they certainly come in handy. Since C# is a statically typed language, we could either make tuples that just store an object type or we could define them with generics. I am choosing to define mine with generics so that type inference will work better a bit later on. Before we get any further, let me show you what a 1-tuple, 2-tuple, and 3-tuple will look like.
public struct Tuple<T1>
{
public T1 One { get; set; }
}
public struct Tuple<T1, T2>
{
public T1 One { get; set; }
public T2 Two { get; set; }
}
public struct Tuple<T1, T2, T3>
{
public T1 One { get; set; }
public T2 Two { get; set; }
public T3 Three { get; set; }
}
Sidenote:
Structs implement
ValueType.Equals, instead of Object.Equals, which uses reflection to compare the fields of the types. This is fairly inefficient, and so Equals can be overridden to help this. I did not do this in the post in order to not put too much extra code into the example.
The first tuple type stores one item, the second two items, and the third three items. Now there is very little use for the 1-tuple, but I am just showing you for completeness. Since we now have a single type that can be used with our dictionary, lets implement the cached multiply method.
public static Func<int,int,int> CachedMultiply()
{
var cache = new Dictionary<Tuple<int,int>, int>();
return (int arg1, int arg2) =>
{
int result;
var arguments = new Tuple<int, int>()
{ One = arg1, Two = arg2 };
if (cache.TryGetValue(arguments, out result))
{
return result;
}
else
{
result = Multiply(arg1, arg2);
cache.Add(arguments, result);
return result;
}
};
}
First, notice that we have changed our return type to Func<int,int,int>, this is the delegate that takes two ints and returns an int. Next you will notice that the Dictionary's key is declared as a Tuple<int,int>. This represents our two arguments passed as one item. We are returning a lambda with two int arguments, and the first thing we do is create our tuple by using the new C# 3.0 object initializers, setting the "One" and "Two" properties to arg1 and arg2. Then we just use this Tuple with the Dictionary and the rest of the method works pretty much the same as before. Pretty sweet huh? We are getting pretty close with our implementation here, we just need to make it generic.
I'm going to have to stop there and continue this post on another day. This post has turned out much longer than I had anticipated, and so I'll just split it into two pieces. In this piece we saw how to implement caching on methods with one and two parameters, and in the next part we are going to see how to turn this into full blown memoization by making this generic.
If you liked it, please vote for it below!
Posted on 11/27/2007 9:24:54 PM by Justin Etheredge
In the last two parts of this series I went over the Map and Fold (reduce) methods and so in this part I figured that I would touch on the Filter higher order function. Don't worry, this will be the last higher order function that we will go over before we start getting into some other functional concepts.
The filter function takes a list and a function that returns a boolean. It loops through each item in the list and applies the function to determine inclusion in the result. The result is simply a filtered version of the input list. We are going to create this function as an extension method of IEnumerable.
public static IEnumerable<T> Filter<T>(
this IEnumerable<T> list,
Func<T, Boolean> func)
{
List<T> result = new List<T>();
foreach (T item in list)
{
if (func(item))
{
result.Add(item);
}
}
return result;
}
As you can see, this method only has one Generic parameter because the result list is always the same type as the items in the input list. This method returns "IEnumerable<T>" which is the filtered list. The function that is being passed to it "Func<T, Boolean> func" takes an item of the types in the list and returns a boolean which determines whether or not that particular item is included in the result. We simply loop through each item, using an if statement that runs the passed function on each item.
As an example of using this, I am going to use the same example list as I have in previous parts of this series.
//declare our integer list
List<int> numbers = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8 };
var result = numbers.Filter(x => x % 2 == 0);
Here we have our list of integers and then we call Filter on it passing in a method that checks each integer to see if it is even. We get a list back with the values 2, 4, 6, and 8. This can be used for far more than just finding even numbers in a list though.
First we will declare a simple Person class.
public class Person
{
public string FirstName { get; set; }
public string LastName { get; set; }
}
Then we will use the new Collection initializers to declare a short list of Person objects.
var people = new List<Person>
{
new Person { FirstName = "Bob", LastName="Parker" },
new Person { FirstName = "Fred", LastName="Thompson"},
new Person { FirstName = "Bob", LastName="Smith"}
};
Then we decide that we want to find all of the Bobs. (Oh that made me think of Office Space). We could find all of the Bob's like this:
var Bobs = people.Filter(x => x.FirstName.ToUpper() == "BOB");
Now that we have gone through all of these higher order functions I will now have to break it to you that Linq provides a built in method that will do pretty much exactly what all of these function do. The method for Filter is called "Where" and it takes a Predicate as a parameter, which is just a delegate declared like this:
public delegate bool Predicate<T>(T obj);
Essentially it is the same as the Func<T, Boolean> that we used earlier, and could have been used instead but I didn't want to throw it in without explaining it. You would use this method like this:
var Bobs = people
.Where(x => x.FirstName.ToUpper() == "BOB").ToList();
This works almost exactly the same as our "Filter" method with the exception that we have to add "ToList" to the call in order to have the query executed immediately, otherwise it will be turned into an expression tree that can later be executed.
Well, that wraps up our discussion of the "Filter" higher order function. As usual, I hope that you learned something from this post. In the next post we are going to discuss a fairly simple concept that a lot of people try to make super complicated, Memoization. So, until next time, happy programming.