View the whole series:
I figured since we went over the "Fold" (also called Reduce) higher order function in the last post, we would go over the "Map" higher order function in this post. Since everyone these days has heard of Map-Reduce because of Google, I figured I would try and close the circle. Map is actually more simple than reduce, it just takes a set of items and a method. It then runs this method on each item in the set. We are going to just create this function as an extension method, since it will make it much easier to use. Our "Map" function would end up looking like this:
public static IEnumerable<TResult> Map<TArg, TResult>(
this IEnumerable<TArg> list,
Func<TArg, TResult> func)
{
if (list == null || list.Count() == 0)
{
return new List<TResult>();
}
else
{
List<TResult> result = new List<TResult>();
result.Add(func(list.First()));
result.AddRange(
Map(list.Skip(1).Take(list.Count() - 1).ToList(), func));
return result;
}
}
This function may look a little bit daunting at first, but trust me, it is actually really simple. The first parameter "this IEnumerable<TArg> list" is our list of data that we are going to operate on. We have added "this" on the front of it because this is an extension method that is called like "IEnumerable.Map();". You will have parameters, but we will get to that in just a second. Our second parameter "Func<TArg, TResult> func" is the method that we are going to apply against the items in our list.
The first part of the method is just the base case for our recursion. If this list is empty or null then we just return an empty list. The second part of our method declares a new List as a result and then adds the first item in the list to it after applying the specified method. Then we call Map recursively passing in the tail of the list (everything except the first item). Here we are using the Linq extension methods to do this, but you could do it however you wanted to. Then we simply return the list that we created. Easy as pie! You would call this method like this:
var result = numbers.Map(x => x * 2);
This would return to you a list of the same size with every item in the list multiplied by 2. And there you have it! We can combine our map and reduce methods like this. This will multiply all the items in the list and then add the results up into an integer.
var comboResult =
numbers.Map(x => x * 2).Fold((int x, int y) => x + y);
Pretty awesome, huh? So, now we have learned how to "map" a function to all the items in a list and then "fold" that list back into a single result. In the future I might have a post that will get into the usefulness of these a bit more, and show you how we could extend these to create more useful functions. In the meantime, get out there and come up with a creative use for it! Be sure to let me know how you use it.
Update:
Someone posted a comment below about how inefficient the Map function I had was. I did it the way that I did because I was trying to implement it in a more functional style. But since I implemented some of my other methods in a more imperative manner I figured I would add an updated version that is more efficient.
public static IEnumerable<TResult> Map<TArg, TResult>(
this IEnumerable<TArg> list,
Func<TArg, TResult> func)
{
List<TResult> result = new List<TResult>();
foreach (TArg item in list)
{
result.Add(func(item));
}
return result;
}
Loved the article? Hated it? Didn’t even read it?
We’d love to hear from you.
I assume you choose that particular implementation of Map() to demonstrate functional techniques such as recursion (an implementation similar to Filter() in the next article would be far better), but I’m not sure you realize exactly how bad that implemetation is. It’s like scary bad!
Map() should be a linear (O(n)) function. However, Count() which you use twice, is by itself linear. By that alone, you moved this from a linear function to a quadradic (O(n*n)) function (and possibly to a cubic — O(n*n*n) — function; I hadn’t fully unrolled it yet)
Another important consideration is that this implementation iterates over the full range of the enumerator several time. This assumes that the enumerator can be iterated over more than one — that’s not actually guarenteed by IEnumerator. In fact, one category of iterators (C++’s equivalent of enumerators) are expression defined as no being able to.
You know, I was actually waiting for that to come up. 🙂 Since IEnumerable.Count() is actually a Linq extension method, it does have to get a new enumerator and loop through each item to count them up. I could have factored count out, but that would have muddied up the example code. A better solution would to have been to just implement this method using ICollection instead, which would have allowed me to get the count (for most all implementations) in O(1) time.
With respect to not being able to iterate through an interator more than once, well, thanks for informing me of this. I will keep an eye out for it in the future, since I don’t believe I have ever had to work with iterators that could only be interated through once. Thanks!
As far as how the recursion is used with the creating of new Lists and using the rest of the old list. Well, I was going for a more functional implementation here where we are not modifying any variables merely creating new ones. It definitely does not lead to the most efficient code, but it keeps with the ideals of functional programming in that sense. If I get some time I’ll try to update the article with a more optimized version of Map for ICollection. Thanks for the feedback!
After making the last comment and then going back and looking at it, I realized exactly what you were saying with regard to the Filter function I had. Yes, it would be quite trivial to implement the Map function in the exact same way as the Filter function. I think I overcomplicated my response with regard to ICollection, but I still think that the current implementation is more meaningful from a functional programming standpoint. I will append the new Map function to the post later this evening.
Simplest implementation of the Map in C# 3.0+ would be the following
public static IEnumerable<TResult> Map<TArg, TResult>(
this IEnumerable<TArg> list,
Func<TArg, TResult> func)
{
return list.Select(func);
}
You simply select each list by applying the func.