Map, Filter and Reduce in Cocoa

June 18, 2007 at 10:42 pm 4 comments

After working in Scheme, Python or Ruby, all of which (more or less) support function objects and the map(), filter() and reduce() functions, languages that don’t seem to be somewhat cumbersome. Cocoa manages to get these paradigms almost correctly implemented.

map()

One would think that Objective-C’s ability to pass functions around as objects in the form of selectors would make writing a map() method easy. Observe, however, the crucial differences of the NSArray equivalent to map(). (For those unfamilar with it, map(), when given an array and a method/function taking one argument, returns the result of mapping the function onto each item of the array.)

From the NSArray documentation:

makeObjectsPerformSelector:

Sends the aSelector message to each object in the array, starting with the first object and continuing through the array to the last object.

– (void)makeObjectsPerformSelector:(SEL)aSelector
Discussion

The aSelector method must not take any arguments. It shouldn’t have the side effect of modifying the receiving array.

This is different on no fewer than two levels. Firstly, even in the NSMutableArray subclass, this method is not allowed to have side effects. Frankly, I can think of few situations in which I would need to map an idempotent function onto an array; the point of map() is to be able to apply a function quickly to every element of an array and get back the changes! Secondly, an unaware or hurried programmer would think that this function was implemented so that one could write code like this:

- (void)printAnObject:(id)obj
{
NSLog([obj description]);
}

and then do this:
[anArray makeObjectsPerformSelector: @selector(printAnObject:)];

This is not the case – the above code would just make each element call printAnObject:, not call printAnObject with each element. I’m sure that to some it seems obvious, but I, for one, found this to be an insidiously tricky wart.

However, there is a (limited) workaround.

NSArray’s valueForKey: method (somewhat counter-intuitively) returns the result of invoking valueForKey on each of the array’s elements. As such, one can map KVC functions onto arrays. For example:

NSArray *arr = [NSArray arrayWithObjects: @"Get", @"CenterStage", @"0.6.2", @"because", @"it", @"rocks", nil];
[arr objectForKey: @"length"]; // returns [3, 10, 6, 7, 2, 5]

This can be used in many helpful ways; sadly, it only works on KVC-compliant properties/methods.

Anyway, moving on…

filter()

With OS X 10.4, Apple introduced the NSArray filteredArrayUsingPredicate: method, which allows one to filter an array based on criteria established by an NSPredicate. Observe:

NSArray *arr = [NSArray arrayWithObjects: @"This", @"is", @"the", @"first", @"CenterStage", @"release", @"I", @"helped", nil];
arr = [arr filteredArrayWithPredicate: [NSPredicate predicateWithFormat: @"SELF.length > 5"]]; // arr is now [@"CenterStage", "@"release", @"helped"]

Verbose, but useful.

reduce()

Frankly, Apple don’t give us any way to do this in pure Cocoa. The best way I’ve found (if you really need this, which is less often than one needs map() and filter()) is to use the F-Script framework and apply the \ operator to an array. Unfortunately, this takes a bit of overhead.

In conclusion, Cocoa and Objective-C almost bring us the joys of functional programming. We can only hope that Leopard and Obj-C 2.0 improve on these in some way.

List comprehensions, anyone?

Entry filed under: cocoa, code, functional, objc, programming, snippets. Tags: .

Sandwiches. Inform 7: Natural-Language Programming Lives

4 Comments

  • 1. Erik  |  June 19, 2007 at 12:21 pm

    If you were to use map() in Python, and the function call you are mapping was to call system.out() or log() or print(), you would observe the same behavior that you describe as a gotcha in Obj-C when trying to use makeObjectsPerformSelector:. The string still needs to be returned from the function call explicitly as a return value, not printed off to some buffer as a side effect.

    Generally speaking, you probably don’t want to use a function that causes side effects when using map() in any language, not just in Obj-C.

  • 2. Patrick Thomson  |  June 19, 2007 at 1:56 pm

    Well, yes – print() is idempotent.

    And why not have map() side effects? In Python, it seems useful to do this:

    map((lambda x: x.capitalize()), [“thanks”, “for”, “the”, “comment”])

    That method has side effects.

    I’m genuinely interested in your opinion.

  • 3. kongtomorrow  |  June 20, 2007 at 8:04 pm

    There aren’t built-in methods for these operations, but there is nothing stopping you from adding them.

    @implementation NSArray (FunctionalProgrammingAdditions)

    // the selector ‘reducer’ must take one object argument and return an object.
    – (id)objectByReducingUsingSelector:(SEL)reducer {
    // implementation goes here
    }

    – (id)objectByReducingUsingFunction:(id (*)(id, id, void *))reducer context:(void *)context {
    // implementation goes here
    }

    // etc.
    @end

  • 4. HeerneClitte  |  August 3, 2008 at 5:10 pm

    Brilliant!


About Me



I'm Patrick Thomson. This was a blog about computer programming and computer science that I wrote in high school and college. I have since disavowed many of the views expressed on this site, but I'm keeping it around out of fondness.

If you like this, you might want to check out my Twitter or Tumblr, both of which are occasionally about code.

Blog Stats

  • 656,770 hits

%d bloggers like this: