Folds in imperative languages

Today I was again playing with folds, but this time implementing them in PHP.
So, consider the list [a, b, c]:
foldr f z [a,b,c] = a `f` (b `f` (c `f` z))
foldl f z [a,b,c] = (((a `f` b) `f` c) `f` z) = z `f` (c `f` (a `f` b))

Note the bolded parts of foldr and foldl. They look pretty same, just that the elements are kind of reversed (e.g. (0 – 1 – 2 – 3) against (3 – 2 – 1 – 0)).

Now consider we use array_reduce in PHP like this:


<?php
var_dump(array_reduce(array(1,2,3), function($x, $y) { return $x - $y; } ));

This will print “-6” as a result. And in Haskell:


Prelude> foldl (-) 0 [1,2,3]
-6

So it turns out we’re using a left fold. What can we do to make it a right fold?
What if we try something like


<?php
var_dump(array_reduce(array(1,2,3), function($x, $y) { return $y - $x; } ));

This one will print “2” as a result. Haskell says:


Prelude> foldr (-) 0 [1,2,3]
2

And in Haskell we can also do something like


Prelude> let f x y = y - x
Prelude> foldr f 0 [1,2,3]
-6

So, it’s interesting to play around with associativity of binary operators 🙂
But we don’t want to do it in a “hacky” way by changing the operands in the function. So we want foldr.
Here’s the full PHP code with foldr and foldl implemented:


<?php
interface iBinaryOperator {
public function calc($x, $y);
}

function foldr(iBinaryOperator $f, $z, array $xs) {
try {
$x = array_shift($xs);
if ($x == null) {
return $z;
}
return $f->calc($x, foldr($f, $z, $xs));
} catch (Exception $e) {
return "error";
}
}

// Foldl is tail recursive
function foldl(iBinaryOperator $f, $z, array $xs) {
try {
$x = array_shift($xs);
if ($x == null) {
return $z;
}
return foldl($f, $f->calc($z, $x), $xs);
} catch (Exception $e) {
return "error";
}
}

class Subtraction implements iBinaryOperator {
public function calc($x, $y) {
if (gettype($x) != "integer" || gettype($y) != "integer") {
throw new Exception("MathException");
}
return $x - $y;
}
/*
public function partial_calc($x) {
if (gettype($x) != "integer") {
throw new Exception("MathException");
}
return function ($y) use ($x) {
if (gettype($y) != "integer") {
throw new Exception("MathException");
}
return $x - $y;
};
}
*/
}

$x = new Subtraction();
var_dump(foldr($x, 0, array(1,2,3)));
var_dump(foldl($x, 0, array(1,2,3)));

/*
> php test.php
int(2)
int(-6)
*/
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s