Map / Reduce in PHP & Scheme
Kris Jordan
Kris Jordan leads web programming & development at New Media Campaigns; Kris previously worked for Microsoft's Developer Division, and studied Computer Science at Brown University and UNC Chapel Hill. You should follow Kris on Twitter.
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.
About the Author
Kris Jordan leads web programming & development at New Media Campaigns; Kris previously worked for Microsoft's Developer Division, and studied Computer Science at Brown University and UNC Chapel Hill. You should follow Kris on Twitter.
Subscribe to RSS
Subscribe to email updates
Our development blog has moved to GetHifi.com, a website dedicated
to our new HiFi web platform.
Visit GetHifi.com »
Comments
Leave a Commentzorg
August 24, 2009 12:10 PM | Permalink
How long before you blow the stack ?
no TCO in PHP, Scheme wins !
adorton
August 24, 2009 1:05 PM | Permalink
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
August 24, 2009 1:58 PM | Permalink
PHP has goto. Let me say it again: PHP has goto. What was this article about again?
Kris Jordan
August 24, 2009 2:01 PM | Permalink
@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
August 24, 2009 2:15 PM | Permalink
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
August 24, 2009 2:59 PM | Permalink
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
August 25, 2009 3:56 PM | Permalink
Have you heard of the array_map method in PHP? Or array_reduce? Just wondering.
Kris Jordan
August 25, 2009 4:05 PM | Permalink
@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
August 25, 2009 5:15 PM | Permalink
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
May 23, 2010 8:23 PM | Permalink
Looking for contributors on PHP Map/Reduce project
http://anton.vedeshin.com/articles/php-mapreduce-similar-implementation-draft
Leave a Comment