view release on metacpan or  search on metacpan

lib/FAST/List/Gen/Cookbook.pm  view on Meta::CPAN

            ($x, $y) = ($y, take($x) + $y)
        }
    }

    say for @{fibonacci 15};


=head2 variable length generators

to implement C< grep > (as C< filter >) or C< while > (as C< While >) on a
generator means that the generator no longer knows its exact size at all times.
care has been taken to make sure that this doesn't bite you too much.

    my $pow = While {$_ < 20} gen {$_**2};

    say for @$pow;     # checks size on every iteration, works fine
    say while <$pow>;  # also works
    say $pow->all;     # ok too

each prints:

    0
    1
    4
    9
    16

but, if instead of C< say for @$pow > you had written C< map {say} @$pow >, perl
will try to expand C< @$pow > in list context, and it will not know when to
stop, since it only checks at the beginning.  the solution, in short, is to only
dereference variable length generators in slice C< @$gen[0 .. 10] > or iterator
C< ... for @$gen; > context, and never in list context.

in general, it makes more sense (and is faster) to build your constraint into
the calling code:

    my $pow = gen {$_**2};
    for (@$gen) {
        last if $_ > 20;
        say;
    }


=head2 recursive generators

the fibonacci sequence can be generated from the following definition:

    f[0] = 0;
    f[1] = 1;
    f[n] = f[n-1] + f[n-2];

here are a few ways to write that definition as a generator:

    my $fib; $fib = cache gen {$_ < 2  ? $_ : $$fib[$_ - 1] + $$fib[$_ - 2]};

    my $fib = gen {$_ < 2 ? $_ : self($_ - 1) + self($_ - 2)}
              ->cache
              ->recursive;

    my $fib; $fib = gen {$fib->($_ - 1) + $fib->($_ - 2)}
                  ->overlay( 0 => 0, 1 => 1 )
                  ->cache;

    my $fib; $fib = gen {$$fib[$_ - 1] + $$fib[$_ - 2]}->cache->overlay;
    @$fib[0, 1] = (0, 1);

bringing all those techniques together:

    my $fib = gen {self($_ - 1) + self($_ - 2)}
            ->overlay( 0 => 0, 1 => 1 )
            ->cache
            ->recursive;

the C< cache > function is used in each example because the recursive definition
of the fibonacci sequence would generate an exponentially increasing number of
calls to itself as the list grows longer.  C< cache > prevents any index from
being calculated more than once.

=head3 more ways to write the fibonacci sequence

    my $fib = <0, 1, *+*...>; >>

    my $fib = <0, 1, {$^a + $^b}...>; >>

    my $fib = ([0, 1] + iterate {sum self($_, $_ + 1)})->rec; >>

    my $fib = ([0, 1] + iterate {sum fib($_, $_ + 1)})->rec('fib'); >>

    my $fib = (iterate {$_ < 2 ? $_ : sum self($_ - 1, $_ - 2)})->rec; >>

    my $fib; $fib = cache gen {$_ < 2 ? $_ : sum $fib->($_ - 1, $_ - 2)}; >>

=head3 a few ways to write the factorial sequence

    my $fac = <[*..] 1, 1..>;

    my $fac = <1, 1..>->scan('*');

    my $fac = 1 + repeat(1)->scan('+')->scan('*');

    my $fac = <1, **_...>;

=head2 stream generators

here is an example of a sieve of eratosthenes implemented with generators:

    my $primes = do {
        my $src = <2..>;
        iterate {
            my ($x, $xs) = $src->x_xs;
            $src = $xs->grep_stream(sub {$_ % $x});
            $x
        }
    };

in this example, the list is filtered with C< grep_stream/filter_stream > since
the algorithm only reads the source once, and reads it in order.  a regular
C< filter/grep > call could be used, but it would unnecessarily use up a lot
of memory since each call would have to build up a new random-access cache.

the inefficiency addressed above could also be fixed by modifying the filtering
function itself:

    my $primes = do {
        my @p;
        <2..>->grep(sub {
            my $i = $_;
            $i % $_ or return for @p;
            push @p, $i;
        })