November 12, 2008

Predicates / List.FindAll()

When I came across the term predicates just after the advent of .NET 2.0, it took a great deal of my time to understand the term given Microsoft’s atrocious “EndsWithSaurus” example (http://msdn.microsoft.com/en-us/library/fh1w7y8z.aspx) which I referenced in my previous post. The basic concept is that given a list of dinosaurs: List<string>/List(Of String) we need to obtain a list of items that end with the string “saurus”. We will ignore the details of how Microsoft did that for the moment…

The 1.1 way…

So to demonstrate the original way of finding all matching items in our list (pretend our list of dinosaurs is called Dinosaurs and is already populated with a bunch:

VB:

Dim Sauruses As New List(Of String)
Dim SearchString As String = "saurus"
For Each Item As String In Dinosaurs
    If Item.SubString(Item.Length – SearchString.Length) = _
      SearchString Then
        Sauruses.Add(Item)
    End If
Next

C#:

List<string> Sauruses As new List<string>;
string SearchString = "saurus";
foreach(string item in Dinosaurs){
    if(item.SubString(item.length - SearchString.Length) ==
       SearchString{
           Sauruses.Add(Item)
       }
}

As you can see, the 1.1 way we would simply have iterated over the list and pulled out matching items which isn’t a particularly huge chore, although it would be nice if it were more elegant.

The 2.0 Way…

In 2.0 the concept of predicates has been added along with the FindAll method in our List class. What on earth are Predicates? In grammatical terms, a sentence is made up of two parts – the subject which is the object of discussion; and the predicate which provides some reflection on the subject perhaps in the form of a description.

Imagine the sentence: “My hair is brown”, given my previous description, you’ve probably already created two containers in your head: Subject and Predicate and you’ve most likely already attributed “Hair” as the subject and “Brown” as the predicate. In programming terms, a predicate is some method that reflects on the descriptive properties of an object and returns some value depending on our method definition.

I’ll simplify Microsoft’s predicate definition because I firmly believe that if an example is easier to read, it makes the concept easier understand…

VB:

Private Function EndsWith(ByVal s As String) As Boolean
    Return s.EndsWith = "saurus"
End Function

What’s going on here? Okay, think for a moment of a single item in our list of dinosaurs and forget the rest of the list for the moment. We are passing a string value into the method which is evaluated as either ending in saurus… or not. This will be used as our predicate and is no different than any regular function. In this case it provides us with a description of our string – stating that it either ends in “saurus” or doesn’t.

One thing to note is that when a function is to be used as a predicate it can only have a single argument that must match the type of the object that will be referenced. In our case, each list item is a string, so the argument must be of type string. The return type must be of whichever type the method invoking the predicate requires to complete its task. FindAll requires a Boolean value, so we return a Boolean.

In .NET 2.0, the List.FindAll method iterates through each of the items in the list and passes the item into the predicate we defined. So the s parameter will refer to the name of the current dinosaur we’re checking. Sadly, nobody had the foresight to allow arguments to be passed to the predicate as it is called on each iteration, so our options were to at worst hardcode what we’re looking for which is the example provided by Microsoft (I’ll bite my tongue here and refer to my previous post); at best involves wrapping the search in a class to allow for thread safety which is more work than necessary in most cases; or by using a class level static field, which isn’t great programming practice and is not thread safe, but unfortunately these are the cards we’ve been dealt and it is with those that we must play…

In this example, we set the _SearchTerm field as “saurus” and then we tell the FindAll method that the EndsWith method is the predicate that will be referenced for each of the items in the list. Think of the FindAll method in a similar manner as ForEach; it iterates through the list and runs the predicate method for each item. The s parameter in our predicate method becomes the currently referenced instance in the iteration.

Don’t be distracted by the use of AddressOf if you’re not familiar with it – The AddressOf keyword is really just telling the FindAll() method that with each iteration it is using the EndsWith() method to evaluate if the subject (in this case, the name of our dinosaur) meets the find condition. The EndsWith() method becomes the predicate container, The search condition: Ends with saurus becomes the content of our predicate container and when the predicate evaluates, it returns true or false notifying FindAll whether the current item should be in the return list or not… (Note: there is a better way to do this in 3.0 and I go on to describe it further down…)

VB:

Private _SearchTerm As String

Private Function EndsWith(ByVal s As String) As Boolean
    Return s.EndsWith = _SearchTerm
End Function

Sub Main()
    _SearchTerm = "saurus"
    Dim sauruses As List(Of String) = _
          dinosaurs.FindAll(AddressOf EndsWith)
End Sub

C#:

private static string _SearchTerm = null;

private static bool EndsWith(string s)
{
    return s.Substring(s.Length - _SearchTerm.Length) == _SearchTerm;
}

static void Main(string[] args)
{
    _SearchTerm = "saurus";
    List<string> sauruses = dinosaurs.FindAll(EndsWith);
}

I can’t wrap my head around why nobody thought that providing the ability to pass a search term into the FindAll method was unnecessary, but somehow it was missed… and the inability to use the search in multiple concurrent threads is ridiculous. If you want to use it in different threads, you would have to build a wrapper class to do the search for you which instead of saving you coding, actually causes far more than necessary! Where we’ve attempted to sidestep list iteration with our For…Each or While Iter.MoveNext… or however we’ve passed over the list, we’re now having to write a whole extra search class that allows us to pass in a search term and the FindAll method which had the potential to be extremely useful became useless in many cases.

The 3.0 Way…

In 3.0, there are a few ways this could be achieved, the most useful it seems is with another new concept called Lambda functions. A lambda function is resurrected from mathematics – the concept is basic, while its paradigm is another big shift for VB programmers that have never had this concept to grasp previously. Think of it as an inline function… it’s more or less the same as the predicate concept we’ve just discussed, but allows for more flexibility because unlike the predicate function which was separate and thus didn’t have access to private variables a lambda function is inline and has access to variables and objects that fall within the current scope of the current method. As demonstrated below…

VB:

Dim SearchString As String = "saurus"
Dim sauruses As List(Of String) = _
    dinosaurs.FindAll( _
        Function(item) item.EndsWith(SearchString) _
    )

C#:

string SearchString = "saurus";
List<string> sauruses =
    dinosaurs.FindAll(
        item => item.EndsWith(SearchString)
    );

Now you can see, we don’t need to hard code the search term as our inline (lambda) expression has access to our search criteria.

So how does it work? Well just like before the FindAll method does the iterative work for you. For each item in the list (item), the current dinosaur in this case. The lambda function tests to see if the item ends with the search criteria returning true or false to the FindAll() method, notifying it whether or not the current item belongs in the return list.

2 comments:

  1. I just wanted to say a big "thank you". You are the first person that explained predicates in a way that I could understand them. Then you went on to explain Lambda functions. It is nice to be able to read your work and understand it, unlike so many other examples out there. Thank you for spelling it out so clearly!

    -Brian

    ReplyDelete