6
\$\begingroup\$

PHP has closures, let's play around with them.

I have some arrays similar to, $wannabelist = array (1, 2, 3, 4, 5, 6).

I want to do this: compr( expression($params), $wannabelist, $wannabilist2 ...).

compr() should do the following:

  1. Take all the possible combinations of elements of the arrays given as parameters;
  2. Pass each of them to the expression passed as first parameter;
  3. Yield the result.

A particularly satisfying function will:

  1. Avoid changing the value of any variable;
  2. Be elegant;
  3. Contain an inordinate amount of nested parenthesis/brackets;
  4. Avoid foreach() loops.
\$\endgroup\$
  • \$\begingroup\$ Note that closures were introduced in PHP 5.3.0 . \$\endgroup\$ – Joey Adams Apr 4 '11 at 21:30
  • \$\begingroup\$ I wasn't implying it was breaking news ^^ \$\endgroup\$ – cbrandolino Apr 4 '11 at 21:50
  • 2
    \$\begingroup\$ After all the pessimists and nihilists, now we have wannabilists! \$\endgroup\$ – Timwi Apr 5 '11 at 16:53
11
\$\begingroup\$

First, a few neat things about list comprehensions, from a Haskell perspective:

  • The list monad in Haskell is set up so any list comprehension can be transformed into do notation rather easily:

    > [(i,j) | i <- [1..3], j <- [1..3]]
    [(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)]
    > do {i <- [1..3]; j <- [1..3]; return (i,j)}
    [(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)]
    
  • Haskell has a sequence function that takes a list of "actions" in a monad and returns a list of the results:

    > sequence [getLine, getLine, getLine]
    one
    two
    three
    ["one","two","three"]
    
  • Consequently, using sequence with the list monad gives you combinations for free:

    > do {i <- [1..3]; j <- [1..3]; return [i,j]}
    [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]
    > sequence [[1..3], [1..3]]
    [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]
    

Hence, the sequence function is very similar to the compr function asked for. It just needs to be wrapped and mapped a bit:

function compr()
{
    $args = func_get_args();
    $f = $args[0];
    $call_f = function($array) use ($f) {
        return call_user_func_array($f, $array);
    };
    return array_map($call_f, sequence(listMonad(), array_slice($args, 1)));
}

Now, without further ado, here is a nearly direct translation of the list monad and sequence function from Haskell to PHP:

# instance  Monad []  where
#     m >>= k          = concat (map k m)
#     return x         = [x]
#     fail s           = []
function listMonad()
{
    return (object) array(
        'bind'   => function($m, $k) {
            return call_user_func_array('array_merge', array_map($k, $m));
        },
        'return' => function($x) { return array($x); },
        'fail'   => function($s) { return array(); }
    );
}

# sequence       :: Monad m => [m a] -> m [a] 
# sequence       =  foldr mcons (return [])
#                     where mcons p q = p >>= \x -> q >>= \y -> return (x:y)
function sequence($monad, $list)
{
    $mcons =
        function($p, $q) use ($monad) {
            return call_user_func($monad->bind, $p,
                function($x) use ($monad, $q) {
                    return call_user_func($monad->bind, $q,
                        function($y) use ($monad, $x) {
                            return call_user_func($monad->return, cons($x, $y));});});};
    return foldr($mcons, call_user_func($monad->return, array()), $list);
}

# foldr            :: (a -> b -> b) -> b -> [a] -> b
# foldr f z []     =  z
# foldr f z (x:xs) =  f x (foldr f z xs)
function foldr($f, $z, $xs)
{
    if (empty($xs))
        return $z;
    return call_user_func($f, $xs[0], foldr($f, $z, array_slice($xs, 1)));
}

function cons($x, $xs)
{
    return array_merge(array($x), $xs);
}

I believe this meets all four of your criteria, especially the "inordinate amount of nested parenthesis/brackets" part.

Test code:

function printList($show, $list)
{
    echo showList($show, $list) . "\n";
}

function showList($show, $list)
{
    $str = "[";
    foreach($list as $x) {
        if ($str !== "[")
            $str .= ",";
        $str .= call_user_func($show, $x);
    }
    return $str . "]";
}

# Count in binary
printList('strval',
    compr(function($a, $b, $c, $d) {
        return "$a$b$c$d";
    }, array(0,1), array(0,1), array(0,1), array(0,1)));

# Combinations of items
printList(function($a) {return showList('strval', $a);},
    compr(function($a, $b, $c) {
        return array($a, $b, $c);
    }, array(1, 2), array(3, 4, 5), array(6, 7, 8, 9)));

Output:

[0000,0001,0010,0011,0100,0101,0110,0111,1000,1001,1010,1011,1100,1101,1110,1111]
[[1,3,6],[1,3,7],[1,3,8],[1,3,9],[1,4,6],[1,4,7],[1,4,8],[1,4,9],[1,5,6],[1,5,7],[1,5,8],[1,5,9],[2,3,6],[2,3,7],[2,3,8],[2,3,9],[2,4,6],[2,4,7],[2,4,8],[2,4,9],[2,5,6],[2,5,7],[2,5,8],[2,5,9]]
\$\endgroup\$
  • \$\begingroup\$ This is beautiful. You already had it or? \$\endgroup\$ – cbrandolino Apr 5 '11 at 20:42
  • 1
    \$\begingroup\$ @cbrandolino: I hacked this up in a few hours. However, it took me a long time to finally "get" how polymorphism is implemented in Haskell. Namely, it eliminates type classes by turning contexts (e.g. (Monad m) => or (Show a) =>) into parameters. I did this manually with the sequence and showList functions. Once type classes are gone, type information can be erased. Philip Wadler describes this in his talk Faith, Evolution, and Programming Languages . \$\endgroup\$ – Joey Adams Apr 5 '11 at 21:05
3
\$\begingroup\$

Implemented using simple modulus/division.

function compr() {
    $args = func_get_args();
    $callback = array_shift($args);

    $total_length = array_product(array_map(function($arr) {
        return count($arr);
    }, $args));

    $return = array();
    for ($i = 0; $i < $total_length; $i++) {
        $params = array();
        $_i = $i;
        for ($j = 0; $j < count($args); $j++) {
            $base = count($args[$j]);
            $params[] = $args[$j][$_i % $base];
            $_i /= $base;
        }
        $return [] = call_user_func_array($callback, $params);
    }

    return $return;
}

Test:

$array = compr(function($a, $b, $c) {
    return $a + $b + $c;
}, array(1, 2), array(3, 4, 5), array(6, 7, 8, 9));

print_r($array);

Output:

Array
(
    [0] => 10
    [1] => 11
    [2] => 11
    [3] => 12
    [4] => 12
    [5] => 13
    [6] => 11
    [7] => 12
    [8] => 12
    [9] => 13
    [10] => 13
    [11] => 14
    [12] => 12
    [13] => 13
    [14] => 13
    [15] => 14
    [16] => 14
    [17] => 15
    [18] => 13
    [19] => 14
    [20] => 14
    [21] => 15
    [22] => 15
    [23] => 16
)
\$\endgroup\$
  • \$\begingroup\$ Nice! Still a bit too many liar variables and loops, but it looks pretty lightweight - at least if compared with the implementation I had in mind. \$\endgroup\$ – cbrandolino Apr 4 '11 at 22:06
  • \$\begingroup\$ It can definitely be improved. I haven't refactored a single line after first getting it to work yet. Will update when I do. \$\endgroup\$ – Dogbert Apr 4 '11 at 23:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.