Sprinkles: The functional fruits must be tasted!

by kengilmer

Some problems are a natural fit for functional style programming.  By this I mean applying functions, often recursively, to lists of data.  Some languages support this out of the box, in a compact elegant fashion, such as Python.  Frustrated with the OOP approach to a problem involving files, I began to write some static helper methods to try to restructure my program in functional way.  The result, after two weeks of thoroughly enjoyable exploration of recursion and self-reference, is Sprinkles.  Sprinkles consists of a “function” interface and a set of static methods that allow the functions, such as map() and fold(), to be applied to elements and collections.  The base function interface is simply:


public interface Function {
    public Object apply(Object element);
}

I know I know, how could anything useful come from such a simple interface…?  Calling the Fn.map(Function, Object) static method will cause every element contained in Object (assuming what’s passed implements Iterable) to be passed to Function, with the result being put in a new Collection as the return value.  When this pattern is applied multiple times, I find that certain problems that would require a lot of code in a traditional OOP approach are quite clean and concise.

To get a sense of the value of Sprinkles, let’s look at some examples.  In these examples I use annonymous inner classes for brevity.  But in real code, I typically define my functions explicitly, as I’ve found I want to reuse them.

Let’s say I want to “walk” the filesystem for all the files from a given directory:

Collection results =
    Fn.map(ReturnFilesFunction.GET_FILES_FN, new File("/tmp"));

See how easy that was? results now contains every file that is a child of /tmp. Ok, I admit this is cheating, but bear with me. I wrote some static functions for common activites like this.
Well, now let’s say I want to figure how the total size of all those files.  Well, the results of my first function is a list of all files.  What if apply another function that returns the sizes of those files:

Collection results = Fn.map(
    new Function(){
          public Object apply(Object element) {
                  return ((File) element).length();
          }
    }, Fn.map(ReturnFilesFunction.GET_FILES_FN, new File("/tmp")));

Now, results will contain a list of the sizes of all the files.  Thankfully, Java autoboxes the primitive types for me since I’m using Java 6.

To get my final result, I simply need to “collapse” the list of sizes into a sum using the fold() function:

</span>

<span style="font-family: Consolas, Monaco, 'Courier New', Courier, monospace; font-size: 12px; line-height: 18px; white-space: pre;">Object result = Fn.fold(new FoldFunction() {</span>
<pre>    public Object apply(Object element, Object result) {
        Long ival = (Long) element;
        Long rval = (Long) result;
        if (rval == null)
               return ival;
        return ival + rval;
    }
    }, Fn.map(new Function() {
            public Object apply(Object element) {
                    return ((File) element).length();
            }
    }, Fn.map(ReturnFilesFunction.GET_FILES_FN, new File("/tmp"))));
System.out.println("Total size: " + result);

You may be thinking, well that’s really hard to read, and I admit it’s true.  There are a few things to make it better.  First, as I mentioned, do not use the anonymous inner classes:

Object result = Fn.fold(
    new AddLongElements(), Fn.map(
        new FileToSize(), Fn.map(
                ReturnFilesFunction.GET_FILES_FN, new File("/tmp"))));

The other trick is using the version of Map() that takes in a Collection<Function>. This let’s the function chain be composed in a linear, non-nested way:

Collection<Fn.Function> functions = new ArrayList<Fn.Function>();
functions.add(ReturnFilesFunction.GET_FILES_FN);
functions.add(new FileToSize());
Object result = Fn.fold(new AddLongElements(),
              Fn.map(functions, new File("/tmp")));

Albiet, in our file example this approach doesn’t help much, since we are only applying a few functions.  But as the chain grows, this code style quickly ends up being easier to read.

One of the interesting twists of Sprinkles is that a Function can return a Collection (list), and that list is then acted upon as such.  When a Function does not want to return a value, it simply returns null and it will not be appended to the list.  However, where ever Collections are used in the API, empty Collections are passed/returned instead of null, making the code much cleaner, since there is no need for null checks everywhere.  And finally, anything can be passed into map().  If what’s passed in is iterable, then the function is applied as a list, otherwise the function is applied as if it’s a list of single element.  This has great impact when composing sets of recursive functions that can expand and contract based on the results of a function.

Drawbacks?  Well, in general this approach works well for certain kinds of problems.  Also, the Object-in-Object-out approach essentially boils down to dynamic typing, since only at runtime is it know what types will be passed and returned.  However since types can be constrained from the entry point of a function, in practice I don’t have much problem with this.  Function reuse is somewhat limited in that a function has to be explicitly written to handle all static types that may be passed to it.  And finally, there are no generics in the API.  I simply don’t understand generics as implemented in the Collections framework well enough yet.

There are more techniques to cover later, such as using find() and depth-first function traversal.  With Sprinkles, I can finally taste the forbidden fruits of functional programming in Java.  It’s amazing to find how easy functions can be composed and reused!

Advertisements