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)
*/