Why does my function composition implemented by reduce returns a closure?

Admin 1
Viewed 221

I want to derive a composition function for n-functions from reduce/fold, but it doesn't work as expected:

$id = function ($x) {
  return $x;
};

$comp = function ($f) {
  return function ($g) use ($f) {
    return function ($x) use ($f, $g) {
      return $f($g($x));
    };
  };
};

$fold = function ($f, $acc) {
  return function ($xs) use ($f, &$acc) {
    return array_reduce($xs, $f, $acc);
  };
};

$compn = function($fs) {/* apply $fold here */};

$inc = function ($n) {
  return $n + 1;
};

$fold($comp, $id) ([$inc, $inc, $inc]) (0); // yields a closure instead of 3

I have the same function implemented in Javascript and it works. I use PHP 7.0.8 cli. I don't know much about PHP, so I am probably overlooking something.

function-composition reduce functional-programming php
2 Answers

I figured it out: array_reduce calls $f as a multi-argument function. So I have to introduce another anonymous function:

$id = function ($x) {
  return $x;
};

$comp = function ($f) {
  return function ($g) use ($f) {
    return function ($x) use ($f, $g) {
      return $f($g($x));
    };
  };
};

$fold = function ($f, $acc) {
  return function ($xs) use ($f, &$acc) {
    return array_reduce($xs, function ($acc_, $x) use ($f) {
//                           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
      return $f($acc_) ($x);
    }, $acc);
  };
};

$compn = function($fs) {/* apply $fold here */};

$inc = function ($n) {
  return $n + 1;
};

echo $fold($comp, $id) ([$inc, $inc, $inc]) (0); // yields 3

And here is the reduce/fold wrapper to get a nicer API:

$compn = function (...$fs) use ($fold, $comp, $id) {
  return $fold($comp, $id) ($fs);
};

$compn($inc, $inc, $inc) (0);
Admin1

Your $comp is curried, and of course you discovered PHP's native array_reduce expects the function to accept multiple parameters – a quick application of uncurry takes some of your pain away, but you'll need to read on if you want to see how this can be improved overall ...

in PHP's humble opinion...

Using uncurry does the trick, but you'll probably end up disliking your program if all the functions are defined as $-named variables – I foresee lots of little problems using that style.

PHP has a callable "type" which makes things a little more PHP-ish – user-defined functions (including higher-order functions) should be called using call_user_func and call_user_func_array

namespace my\module;

function identity ($x) {
  return $x;
}

function comp ($f) {
  return function ($g) use ($f) {
    return function ($x) use ($f, $g) {
      return call_user_func ($f, call_user_func ($g, $x));
    };
  };
}

function uncurry ($f) {
  return function ($x, $y) use ($f) {
    return call_user_func (call_user_func ($f, $x), $y);
  };
}

function fold ($f, $acc) {
  return function ($xs) use ($f, $acc) {
    return array_reduce ($xs, uncurry ($f), $acc);
  };
}

Now your compn with variadic interface works as expected

function compn (...$fs) {
  return fold ('comp', 'identity') ($fs);
}

function inc ($x) {
  return $x + 1;
}

echo compn ('inc', 'inc', 'inc') (0); // 3

But it works with anonymous functions too

$double = function ($x) { return $x + $x; };

echo compn ($double, $double, 'inc') (2); // 12

functional code, modular program

With your functions declared using function syntax, you can import them into other areas of your program

// single import
use function my\module\fold;

// aliased import
use function my\module\fold as myfold;

// multiple imports
use function my\module\{identity, comp, compn, fold};

And now you don't have to litter you code with use-blocks every time you want to use one of your functions

// before
$compn = function (...$fs) use ($fold, $comp, $id) {
  return $fold($comp, $id) ($fs);
};

// after
function compn (...$fs) {
  return fold ('comp', 'id') ($fs);
}

When it comes to debugging, undoubtedly the named functions will provide more helpful stack trace messages as well

relevant but unimportant

PHP has other reasons for adding the callable type, but ones I'm sure that don't concern you as they're OOP-related – eg,

class method calls

// MyClass::myFunc (1);
call_user_func (['MyClass', 'myFunc'], 1);

object method calls

// $me->myfunc (1);
call_user_func ([$me, 'myfunc'], 1);
user_6331830
Related