Recursive generators in PHP

问题:

Introduction

Since version 5.5 in PHP there's such great thing as generators. I will not repeat official manual page, but they are great thing for short definition of iterators. The most-known sample is:

function xrange($from, $till, $step)
{
   if ($from>$till || $step<=0)
   {
      throw new InvalidArgumentException('Invalid range initializers');
   }

   for ($i = $from; $i < $till; $i += $step)
   {
      yield $i;
   }
}

//...

foreach (xrange(2, 13, 3) as $i)
{
   echo($i.PHP_EOL); // 2,5,8,11
}

and generator is actually not a function, but an instance of a concrete class:

get_class(xrange(1, 10, 1)); // Generator

The problem

Done with RTM stuff, now moving on to my question. Imagine that we want to create generator of Fibonacci numbers. Normally, to get those, we can use simple function:

function fibonacci($n)
{
   if(!is_int($n) || $n<0)
   {
      throw new InvalidArgumentException('Invalid sequence limit');
   }
   return $n < 2 ? $n : fibonacci($n-1) + fibonacci($n-2);
}

var_dump(fibonacci(6)); // 8

Let's transform this into something, that holds sequence and not only it's last member:

function fibonacci($n)
{
   if (!is_int($n) || $n<0)
   {
      throw new InvalidArgumentException('Invalid sequence limit');
   }
   if ($n<2)
   {
      return range(0, $n);
   }
   $n1 = fibonacci($n-1);
   $n2 = fibonacci($n-2);
   return array_merge($n1, [array_pop($n1)+array_pop($n2)]);
}

//...

foreach (fibonacci(6) as $i)
{
   echo($i.PHP_EOL); // 0,1,1,2,3,5,8
}

We have now a function that returns array with full sequence

The question

Finally, the question part: how can I transform my latest fibonacci function so it will yield my values, not holding them in an array? My $n can be big, so I want to use benefits of generators, like in xrange sample. Pseudo-code will be:

function fibonacci($n)
{
   if (!is_int($n) || $n<0)
   {
      throw new InvalidArgumentException('Invalid sequence limit');
   }

   if ($n<2)
   {
      yield $n;
   }

   yield fibonacci($n-2) + fibonacci($n-1);
}

But this, obviously, is crap since we can't handle with it like this way because recursion will cause object of class Generator and not int value.

Bonus: getting fibonacci sequence is just a sample for more general question: how to use generators with recursion in common case? Of course, I can use standard Iterator for that or re-write my function to avoid recursion. But I want to achieve that with generators. Is this possible? Does this worth efforts to use this such way?

回答1:

I've finally identified a real-world use for recursive generators.

I've been exploring QuadTree datastructures recently. For those not familiar with QuadTrees, they're a tree-based datastructure use for geospatial indexing, and allowing a fast search lookup of all points/locations within a defined bounding box. Each node in the QuadTree represents a segment of the mapped region, and acts as a bucket in which locations are stored... but a bucket of restricted size. When a bucket overflows, the QuadTree node splits off 4 child nodes, representing the North-west, North-east, South-west and South-east areas of the parent node, and starts to fill those.

When searching for locations falling within a specified bounding box, the search routine starts at the top-level node, testing all the locations in that bucket; then recurses into the child nodes, testing whether they intersect with the bounding box, or are encompassed by the bounding box, testing each QuadTree node within that set, then recursing again down through the tree. Each node may return none, one or many locations.

I implemented a basic QuadTree in PHP, designed to return an array of results; then realised that it might be a valid use case for a recursive generator, so I implemented a GeneratorQuadTree that can be accessed in a foreach() loop yielding a single result each iteration.

It seems a much more valid use-case for recursive generators because it is a truly recursive search function, and because each generator may return none, one or many results rather than a single result. Effectively, each nested generator is handling a part of the search, feeding its results back up through the tree through its parent.

The code is rather too much to post here; but you can take a look at the implementation on github.

It's fractionally slower than the non-generator version (but not significantly): the main benefit is reduction in memory because it isn't simply returning an array of variable size (which can be a significant benefit depending on the number of results returned). The biggest drawback is the fact that the results can't easily be sorted (my non-generator version does a usort() on the results array after it's returned).

回答2:

So the issue I ran into when attempting to create a recursive generator function, is that once you go past your first depth level each subsequent yield is yielding to its parent call rather than the iteration implementation (the loop).

As of php 7 a new feature has been added that allows you to yield from a subsequent generator function. This is the new Generator Delegation feature: https://wiki.php.net/rfc/generator-delegation

This allows us to yield from subsequent recursive calls, which means we can now efficiently write recursive functions with the use of generators.

$items = ['what', 'this', 'is', ['is', 'a', ['nested', 'array', ['with', 'a', 'bunch',  ['of', ['values']]]]]];

function processItems($items)
{
    foreach ($items as $value)
    {
        if (is_array($value))
        {
            yield from processItems($value);
            continue;
        }
        yield $value;
    }
}

foreach (processItems($items) as $item)
{
    echo $item . "\n";
}

This gives the following output..

what
this
is
is
a
nested
array
with
a
bunch
of
values

回答3:

function fibonacci($n)
{
    if($n < 2) {
        yield $n;
    }

    $x = fibonacci($n-1);
    $y = fibonacci($n-2);
    yield $x->current() + $y->current();
}


for($i = 0; $i <= 10; $i++) {
    $x = fibonacci($i);
    $value = $x->current();
    echo $i , ' -> ' , $value, PHP_EOL;
}

回答4:

If you first want to make a generator you might as well use the iterative version of fibonacci:

function fibonacci ($from, $to)
{
  $a = 0;
  $b = 1;
  $tmp;
  while( $to > 0 ) {
    if( $from > 0 )
      $from--;
    else
      yield $a;

    $tmp = $a + $b;
    $a=$b;
    $b=$tmp;
    $to--;
  }
}

foreach( fibonacci(10,20) as $fib ) {  
    print "$fib "; // prints "55 89 144 233 377 610 987 1597 2584 4181 " 
}

回答5:

Here's a recursive generator for combinations (order unimportant, without replacement):

<?php

function comb($set = [], $size = 0) {
    if ($size == 0) {
        // end of recursion
        yield [];
    }
    // since nothing to yield for an empty set...
    elseif ($set) {
        $prefix = [array_shift($set)];

        foreach (comb($set, $size-1) as $suffix) {
            yield array_merge($prefix, $suffix);
        }

        // same as `yield from comb($set, $size);`
        foreach (comb($set, $size) as $next) {
            yield $next;
        }
    }
}

// let's verify correctness
assert(iterator_to_array(comb([0, 1, 2, 3, 4], 3)) == [
    [0, 1, 2], [0, 1, 3], [0, 1, 4], [0, 2, 3], [0, 2, 4],
    [0, 3, 4], [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]
]);

foreach (comb([0, 1, 2, 3], 3) as $combination) {
    echo implode(", ", $combination), "\n";
}

Outputs:

0, 1, 2
0, 1, 3
0, 2, 3
1, 2, 3

Same thing non-yielding.

回答6:

Recently ran into a problem that needed 'recursive' generators or generator delegation. I ended up writing a little function that converts delegated generators calls into a single generator.

I turned it into a package so you could just require it with composer, or checkout the source here: hedronium/generator-nest.

Code:

function nested(Iterator $generator)
{
    $cur = 0;
    $gens = [$generator];

    while ($cur > -1) {
        if ($gens[$cur]->valid()) {
            $key = $gens[$cur]->key();
            $val = $gens[$cur]->current();
            $gens[$cur]->next();
            if ($val instanceof Generator) {
                $gens[] = $val;
                $cur++;
            } else {
                yield $key => $val;
            }
        } else {
            array_pop($gens);
            $cur--;
        }
    }
}

You use it like:

foreach (nested(recursive_generator()) as $combination) {
    // your code
}

Checkout that link above. It has examples.

回答7:

Short answer: recursive generators are simple. Example for walking through tree:

class Node {

    public function getChildren() {
        return [ /* array of children */ ];
    }

    public function walk() {
        yield $this;

        foreach ($this->getChildren() as $child) {
            foreach ($child->walk() as $return) {
                yield $return;
            };
        }
    }
}

It's all.

Long answer about fibonacci:

Generator is something that is used with foreach (generator() as $item) { ... }. But OP wants fib() function to return int, but at the same time he wants it to return generator to be used in foreach. It is very confusing.

It is possible to implement recursive generator solution for fibonacci. We just need to put somewere inside fib() function a loop that will indeed yield each member of the sequence. As generator is supposed to be used with foreach, it looks really wierd, and I do not think it is effective, but here it is:

function fibGenerator($n) {
    if ($n < 2) {
        yield $n;
        return;
    }

    // calculating current number
    $x1 = fibGenerator($n - 1);
    $x2 = fibGenerator($n - 2);
    $result = $x1->current() + $x2->current();

    // yielding the sequence
    yield $result;
    yield $x1->current();
    yield $x2->current();

    for ($n = $n - 3; $n >= 0; $n--) {
        $res = fibGenerator($n);
        yield $res->current();
    }
}

foreach (fibGenerator(15) as $x) {
    echo $x . " ";
}

回答8:

I am offering two solution for Fibonacci number, with and without recursion:

function fib($n)
{
    return ($n < 3) ? ($n == 0) ? 0 : 1 : fib($n - 1) + fib($n - 2);
}
function fib2()
{
    $a = 0;
    $b = 1;
    for ($i = 1; $i <= 10; $i++)
    {
        echo $a  . "\n";
        $a = $a + $b;
        $b = $a - $b;
    }
}

for ($i = 0; $i <= 10; $i++)
{
    echo fib($i) . "\n";
}

echo fib2();