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.
Related Posts
Comments
Anton Vedeshin
Looking for contributors on PHP Map/Reduce project
http://anton.vedeshin.com/articles/php-mapreduce-similar-implementation-draft
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.
Kris Jordan
@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.
Tom Brearley
Have you heard of the array_map method in PHP? Or array_reduce? Just wondering.
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!).
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.
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);
Luke
PHP has goto. Let me say it again: PHP has goto. What was this article about again?
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.
zorg
How long before you blow the stack ?
no TCO in PHP, Scheme wins !
Leave a comment