Iterators and functional programming

Posted Thu, Nov 2 2006 8:58 by bill
I’ve been meaning to blog about Iterators for sometime now but can never find the time to give the subject as it deserves. But rather than stay silent, I’ve decided to at least blurb some of my thoughts.
 
A couple of weeks ago Nick posted an example of what you can do with iterators in C#. The sample was a tree iterator, the tree being similar in nature to a file-system: each folder has Items which are files as well as a collection of folders. 
 
My first thoughts where that this is in fact a common thing to do, and that a case by case iterator was (and is) a bad approach.  Rather you should be able to simply return a generic tree enumerator.  Typically when working with collections you rarely need to use an iterator other than the standard ones, such as an array’s or a List’s.  That is, in 99.9% of cases, the iterators you want to return are common patterns, and the guidance of code re-use should steer us well away from custom iterators, especially inline ones.  This particular example however poses other problems. 
 
If we wanted to solve this problem with a generic tree iterator, we’d need to provide two bits of information, (i) the item property get, and (ii) the child nodes property get (or function).  We can solve (i) via the IList interface and it would be reasonable to expect that to be implemented, but for (ii) the list of folders we don’t have another interface to use. Given the framework doesn’t have such an interface, we can’t really expect an existing class to have already implemented an interface which we are yet to define ;).. Hence the need for functional programming…….
 
In this example we can’t simply pass the lists to an iterator because the iteration is recursive.. that is as each child node is traversed, the iterator needs to get a list of the child’s children (sub-folders) as well as the child’s items (files).  So one approach would be to pass in MethodInfo and the root object to the generic iterator’s constructor. The MethodInfo would be the function or property_get for the child nodes.  The problem with this approach is that all strong typing is lost.
 
What we really need here is a type safe way to work with what is essentially a delegate, but one in without the instance being fixed….. a “first class” way of dealing with function types, just as we can with class types.
 
Let’s say for example we introduced a GetMethod keyword, similar in nature to GetType in VB (or TypeOf in C#).  We might also want to simplify getting Property Get’s and Set’s by providing specific keywords for them, eg GetPropertyGet ;)
We’d also want a nice way to refer to these methods and an easy way to convert them to and from delegates. (similar to RuntimeMethodHandle, but castable to a delegate not just an IntPtr)
Now we should have enough to build our generic tree enumerator.
 
Class TreeEnumerator(Of T)
 
       Sub New( ByVal root As IList(Of T), ByVal method As Function()  returns IList(Of IList(Of T)) )
               …..
 
In the above constructor, I’ve used an inline way of defining the Function and instead of having the parameter read as: method As function As returntype, I’ve added a “returns” keyword to better inline describe what the function does rather than multiples As’s ;)
 
Now in the above example, “method” would in fact be a delegate already, and this would fit nicely to how we’d actually call it as the first method would in fact be on the root instance.  As we iterate this however we’d need to get from that delegate the MethodHandle and from that then get the Delegate for the next instance.
 
So in essence what is needed here to preserve the strong typing is to be able to have a derived MethodInfo, much like how we have derived Delegates, and to be able to create a Delegate easily from the derived MethodInfo specifying the Target, and have that nice design time checking in place.
 
The GetMethod, GetPropertyGet etc, would only be needed for static types, in the other cases we’d really be dealing with StronglyTyped delegates in a more flexible manner than what we can today.
 
But I have digressed, I was talking about iterators   (or was I ??? <g>) And the question has been raised is how important are iterators from a language point of view. 
 
From my view point I see iterators as focusing very much on the plumbing, not the end points.  They don’t encourage code re-use, in fact quite the opposite.. the solution rather than being descriptive becomes procedural.  And I do believe that in the vast majority of cases you can use standard enumerators.  Of course for those few cases where you do need to jump in between the pipes, having to actually write your own enumerator is very much like being inside the sewer pipe ;)
Filed under: ,

Comments

# On the subject of iterators. &laquo; notgartner

Saturday, November 04, 2006 4:46 AM by On the subject of iterators. « notgartner