# 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:

`<?phpvar_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

`<?phpvar_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 - xPrelude> 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:

`<?phpinterface 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 recursivefunction 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.phpint(2)int(-6)*/`
Advertisements