Blog

Where we discuss our work, thoughts, and process

Map / Reduce in PHP & Scheme

Ever wondered what higher-order functions look like in PHP? Now that PHP has lambdas and closures it is possible to code in a beautiful, functional style and implement functions like map / reduce in native PHP. Dig this:

function map($fn, $list) {  
    return empty($list) ?
               array() :
               construct($fn(first($list)),
                         map($fn, rest($list)));}

Never think you'd live to see beautiful PHP, did you? Now you have. For comparison's sake, here's the equivalent in Scheme:

(define (map fn lis)
   (if (null? lis)
       '()
       (cons (fn (car lis))
             (map fn (cdr lis)))))

If you are more familiar with loops than recursion and higher-order functions, check out Part II of the series on Functional PHP covering function types, map and reduce implemented with loops, and an explanation of the recursive implementation. It goes into much more depth and is worth checking out if these side-by-sides feel a little voodoo.

Let's apply some reductionary powers with reduce...

function reduce($fn, $list, $identity) {  
    return empty($list) ? 
               $identity  :
               $fn(first($list),
                  reduce($fn, rest($list), $identity));}

And, again for a little scheme side-by-side:

(define (reduce fn lis identity)
   (if (null? lis)
       identity
       (fn (car lis)
           (reduce fn (cdr lis) identity))))

How awesome does that PHP look? The helper functions used in PHP construct, first, and rest, corresponding to lisp/Scheme's cons, car, cdr are implemented in this tutorial on functional PHP over at the Recess PHP Blog.

Comments

 zorg's avatar
zorg

How long before you blow the stack ?
no TCO in PHP, Scheme wins !

 adorton's avatar
adorton

Can't this also be implemented in PHP 5.2? It's cool to be sure, but I don't see any 5.3-specific features in your examples.

Luke 's avatar
Luke

PHP has goto. Let me say it again: PHP has goto. What was this article about again?

 Kris Jordan's avatar
Kris Jordan

@adorton - you can do this with 5.2 if the functions you are passing to map/reduce are first class functions or created using the, pretty awful, create_method [by string eval] function.

With 5.3 you can use anonymous functions which makes higher order functions significantly more useful to work with:

map(function($string) { return $string . "foo"; }, $myListOfStrings);

 Kris Jordan's avatar
Kris Jordan

Re @Luke "PHP has goto" ... and the United States has nukes. Both have awesome powers. I hope I never live to see the day where the best solution I can come up with is to fire off a flurry of GOTOs. That said, knowing they are on ice in a silo somewhere guarded by decades of advice urging us not to use them, well, thats the power and responsibility that one feels when programming in PHP.

Jach's avatar
Jach

That's pretty awesome, now I can feel less ashamed about loving PHP despite prior to this its anon functions sucked. (Still somewhat shamed because they added goto, but whatever, Python's my favorite anyway.) I'm waiting a bit before I upgrade, but they've done a good job with this release (minus the addition of goto!).

Tom Brearley's avatar
Tom Brearley

Have you heard of the array_map method in PHP? Or array_reduce? Just wondering.

Kris Jordan's avatar
Kris Jordan NMC team member

@Jach - with the advent of 5.3 PHP is turning a bit of a corner. Fun times!

@Tom - Yes, I'm aware of the built-in functions. Their use is demonstrated in the full version of the post linked to from this article. The point was to demonstrate what higher-order functions look like in PHP and map/reduce are well-known enough functions expressing their implementation in plain-old PHP and Scheme is interesting.

Pat Collins's avatar
Pat Collins

For those looking to try out PHP 5.3 easily, check out buildphp:

http://github.com/patcoll/buildphp

It is a build system I wrote, based on Rake, that grabs, builds and installs PHP and supporting files for all desired extensions. With minimal effort, it is possible to upgrade your dev environment to use PHP 5.3 to see how it can work for you.

Anton Vedeshin's avatar
Anton Vedeshin

Looking for contributors on PHP Map/Reduce project
http://anton.vedeshin.com/articles/php-mapreduce-similar-implementation-draft

Leave a comment

Real Time Web Analytics