I got back to coding tonight, at least to get away from the images on TV. For the past week or so, I've been writing code for the Imagine Cup Software design invitation (www.thespoke.net/india) . It's a chess-related problem where you have to find the move that leads to a checkmate.
As you can imagine, such code involves operations involving all the pieces (members of a PiecesCollection).So a huge chunk of my time for the past one week has been spent in
a. Setting up a loop over the PiecesCollection or a subset
b. Calling a function on each member
Now, this is pretty standard .NET stuff, but my patience started to wear thin after the 10th or so loop. I was missing Python's 'map' function (and list comprehensions even more). Tonight, I sat for an hour or so and tried to write some of those functional-language utilities for C# (and .NET in general, obviously).
Here's the result I wanted - the ability to say
Map(FunctionName , ListOfSomeSort);
I quickly wrote up the template
using System;
using System.Collections;
using System.Reflection;
namespace NLambda
{
public class Lambda
{
}
}
Ok - now, let's make an attempt at writing 'map'.
Map is a function which takes two arguments - a function and a list (a kind of array). It calls the function for every element of the list, passing the element as the parameter for the function.
I immediately hit my first road-block - how do you pass a function as a parameter. In C, you could have passed a function pointer, while in functional languages like Lisp or Scheme, functions are first class citizens and you can do anything with them. Similar story with dynamic languages like Python. But how in hell do you pass a function as a parameter in .NET? [1][2]
The first thought that came to my head was ..delegates. After all, delegates are the things you use to pass around functions in .NET, right? After one hour of mucking around, I couldn't figure out anyway to conjure up a delegate which could *take any function* [3]. Now, I could be making a huge mistake here so if one of you does know a way of passing *any* method through a delegate, please do enlighten me.
This brought me back to my first problem - how do you pass a function as a parameter? I could have taken the lazy route and passed a MethodInfo object for the function - but that meant writing reflection code on the caller side - which is a ugly hack [4]. So I decided to drop my sights a bit and relented to using a string to pass the function name in.
[Update: I made a major goof-up here. I had thought that the ability to pass any function is important - but in reality, I know the signature of the function. So I could have simply used delegates For Map, a delegate taking an object as parameter and returning an object. For Remove,it should reduce a bool. Also, delegates would be much faster.The problem I had actually solved here was how to write the 'apply' function in C#. My bad]
Now, do remember that this is reflection code- and any reflection code is slow. Really slow.So do not ever think of using this approach in your production code.
I formed a new target
Map(string FunctionName,ListOfSomeSort)
I also wanted to avoid CodeDom and building assemblies at run-time.However, you may need to dive into those monsters if you want to implement things like Python's list comprehensions or something resembling Lisp's macros.
I had a small issue to resolve - static methods and non-static methods. Non-static methods need a object to be called on - and this object has to be passed. I have written the code for handling static methods too - but I'm not writing it in this post. Its quite similar - you don't need to pass a object to the MethodInfo.Invoke function
Second issue - what type of lists should I handle. I pulled out MSDN and saw that ICollection was implemented by every list-like type out there- but it lacked functionality like removing or adding items - something I wanted badly. I settled on using IList [5] . All settled , I wrote up my code (comments and error-handling removed for brevity). Obviously, .in NET 2.0 this code would look very different and unnecessary in fact.
public static IList Map(Object target,string mapFunction,IList collection)
{
Assembly listAssembly = (collection.GetType()).Module.Assembly;
IList result = (IList)listAssembly.CreateInstance(collection.GetType().ToString());
MethodInfo method = (target.GetType()).GetMethod(mapFunction);
for(int i=0;i<collection.Count;i++)
{
result.Add(method.Invoke(target,new object[]{collection[i]}));
}
return result;
}
Here's how you use it (in another class) -
public void Display(Object number)
{
Console.WriteLine(number);
}
public void TestMap()
{
ArrayList input = new ArrayList();
for(int i=0;i<100;i++)
{
input.Add(i);
}
Lambda.Map(this,"Display",input);
}
This prints out all numbers from 0 to 99 - the members of the 'input' arraylist
Emboldened by this, I quickly wrote up another lambda-related utility - 'remove'.Remove takes a list and a function returning a boolean. If the function returns true, the element is removed from the list otherwise kept. Here's my version of 'remove' (it's destructive - it operates on the same list passed in).
public static IList Remove(Object target,string removeFunction,IList collection)
{
Type targetType = target.GetType();
MethodInfo method = targetType.GetMethod(removeFunction);
for(int i=0;i<collection.Count;i++)
{
if((bool)(method.Invoke(target,
new object[]{collection[i]}
)))
{
collection.RemoveAt(i);
i--; //Changing the loop counter like this is dangerous
//but as all the elements are shifted down by one, this is ok
}
}
return collection;
}
This method is a real kludge - first of all, it is destructive,which is bad. Even worse, it has some code that I usually wouldn't write - modifying an array while looping over it. Even worse,I modify the counter inside. The reason - this was personal code and I was pretty insistent on the performance bit - and this seemed the fastest way - without any extra storage.
Here's how you use it
public static bool IsEven(Object number)
{
return (int)number%2==0;
}
public void Display(Object number)
{
Console.WriteLine(number);
}
public void RunTest()
{
ArrayList input = new ArrayList();
for(int i=0;i<100;i++)
{
input.Add(i);
}
ArrayList result = null;
result = (ArrayList)Lambda.Remove(this,"IsEven",input);
}
The result arraylist would now contain only odd numbers.
Do understand that this code isn't anywhere near production quality - but if you don't have access to C# 2.0, you might want to consider writing your own version of things like this to simplify your code. And you could use it to show off to your functional-programming friends like I intend to do :-)
Notes
[1]: In C# 2.0, with anonymous delegates, everything I've written is unnecessary
[2]: Yes, I know Microsoft Research has a functional language called F# - but my net connection wasn't working at the time and also, I was too lazy :)
[3] The code in this blog is generic, i.e, I use strings to pass function names to make it as generic as possible. In my chess code,I would know beforehand the functions and their signatures, so I could use delegates and make the whole thing a lot easier - and a lot tougher for any of my readers to use. So if you want speed, use delegates. If you want real speed, forget this approach and use a real loop. If you want your code to go faster than that, pick up a book on assembly
[4] Whether that hack is uglier than my approach is debatable :-)
[5] The other option is using IDictionary - this code can be easily adapted for that