blib/lib/List/Gen/Cookbook.pm untested

filter: Statementstmt 0.0% 0 / 7 Branchbran 0.0% 0 / 2 Conditioncond n/a MC/DCmcdc n/a Subroutinesub 0.0% 0 / 2 Podpod n/a totaltotal 0.0% 0 / 11 SCAR 6.9
CC
1
Cov
0%
BEGIN
2.0
BEGIN
2.0
CRAP 2.0
1 package List::Gen::Cookbook;
2 use warnings;
3 use strict;
4
5 =head1 NAME
6
7 List::Gen::Cookbook - how to get the most out of L<List::Gen>
8
9 =head1 COOKBOOK
10
11 this document contains tips and tricks for working with and combining generators
12
13 =head2 iteration
14
15 given the generator C< my $gen = gen {2**$_} 100; > which computes the first
16 hundred powers of two, here are a few was to iterate over it (that all maintain
17 lazy evaluation):
18
19 for (@$gen) {...} # no need to reset generator between calls
20 for my $p (@$gen) {...}
21 ... for @$gen;
22
23 while (<$gen>) {...} # iterated generators must be reset with `$gen->reset`
24 ... while <$gen> # before each loop, also be sure to `local $_` before
25 # while loops that modify `$_`
26 while (my $p = <$gen>) {...}
27 while (defined(my $p = $gen->())) {...}
28 while ($gen->more) {do something with $gen->next}
29
30 since all of these iteration examples remain lazy (only generating values on
31 demand), you can C< last > at any time to break out of the loop.
32
33 you can also use the C< do > method:
34
35 $gen->do(sub {...}); # which calls sub on every element of $gen
36
37 =head2 list creation
38
39 you can dereference finite length generators to pass all of their elements to
40 a function:
41
42 say sum @$gen;
43
44 but it is usually faster to write it this way:
45
46 say sum $gen->all;
47
48 generators interpolate in strings like normal arrays:
49
50 say "@$gen[0 .. 10]";
51
52 do not call C<< ->all >> or use array dereferencing on infinite generators. in
53 some places you may get an error, others, it will loop forever (and probably run
54 out of memory at some point).
55
56 =head2 inline generators
57
58 the generators without code blocks, C< range > and C< glob >, can be directly
59 dereferenced with C< @{...} >
60
61 for (@{range 0.345, -21.5, -0.5}) {...}
62
63 for (@{< 1 .. 10 by 2 >}) {...}
64
65 for those with code blocks, perl needs a little help to figure out whats going
66 on:
67
68 for (@{ +gen {$_**2} 1, 10 }) {...} # a '+' or ';' before it does the trick
69
70 =head2 normal generators
71
72 the C< range > and C< makegen > functions are the most primitive generators,
73 C< range > producing a lazy list, and C< makegen > wrapping a perl array.
74
75 you build upon these with the other generator functions/methods. many
76 generator functions will pass their arguments along to C< range > or
77 C< makegen > as needed, so you rarely need to use them directly.
78
79 gen {$_**2} 100 ~~ gen {$_**2} range 0, 100
80
81 my @names = qw/bob alice eve/;
82 gen {"hello $_!"} \@names ~~ gen {"hello $_!"} makegen @names
83
84 those were two examples of C< gen >, the generator equivalent of C< map > that
85 attaches a code block to a generator.
86
87 =head2 iterative generators
88
89 there is one other primitive generator type, the C< iterate > generator, which
90 is used when your algorithm is iterative in nature. iterative generators come
91 in two flavors, single element per iteration, and multi element per iteration.
92
93 my $fib = do {
94 my ($an, $bn) = (0, 1);
95 iterate {
96 my $return = $an;
97 ($an, $bn) = ($bn, $an + $bn);
98 $return
99 }
100 };
101
102 my $multi = do {
103 my $var;
104 iterate_multi {
105 my @return = ...;
106 }
107 }
108
109 you can also use the C<< ->from >> method to write an iterator that builds
110 from an initial value:
111
112 say iterate{$_*2}->from(1)->str(10); # 1 2 4 8 16 32 64 128 256 512
113
114 the iterative generators have some syntactic sugar you can use, in the form of
115 C< gather {...} > and C< take(...) >:
116
117 my $fib = do {
118 my ($x, $y) = (0, 1);
119 gather {
120 ($x, $y) = ($y, take($x) + $y)
121 }
122 };
123
124 don't confuse this implementation of C< gather/take > with the perl6
125 implementation, or the implementation of C< yield > in python. since perl5 does
126 not have continuations, C< take > can't pause the execution of the gather block.
127 instead, it saves the value passed to it, and the gather block returns it when
128 the block ends. you can use C< gather_multi > to C< take > multiple times.
129
130 all iterative generators implicitly cache their generated elements in an
131 internal array. this allows random access within the generator. unlike other
132 caching generators, you can not purge the iterator's cache (except by letting
133 all references to the generator fall out of scope, like a normal variable).
134 if you want an iterator that throws its values away, just write a subroutine:
135
136 my $fib = do {
137 my ($an, $bn) = (0, 1);
138 sub {
139 my $return = $an;
140 ($an, $bn) = ($bn, $an + $bn);
141 $return
142 }
143 };
144
145 say $fib->() for 1 .. 10;
146
147
148 =head2 composite generators
149
150 there are many ways to modify generators.
151
152 my $odd = filter {$_ % 2};
153 my $squares_of_odd = gen {$_**2} $odd;
154
155 my $less_than_1000 = While {$_ < 1000} $squares_of_odd;
156
157 say for @$less_than_1000;
158
159 my $this_is_same = While {$_ < 1000} gen {$_**2} filter {$_ % 2};
160
161 say for @$this_is_same;
162
163 here is a sub that returns a generator producing the fibonacci sequence to a
164 given magnitude:
165
166 sub fibonacci {
167 my $limit = 10**shift;
168 my ($x, $y) = (0, 1);
169
170 While {$_ < $limit} gather {
171 ($x, $y) = ($y, take($x) + $y)
172 }
173 }
174
175 say for @{fibonacci 15};
176
177
178 =head2 variable length generators
179
180 to implement C< grep > (as C< filter >) or C< while > (as C< While >) on a
181 generator means that the generator no longer knows its exact size at all times.
182 care has been taken to make sure that this doesn't bite you too much.
183
184 my $pow = While {$_ < 20} gen {$_**2};
185
186 say for @$pow; # checks size on every iteration, works fine
187 say while <$pow>; # also works
188 say $pow->all; # ok too
189
190 each prints:
191
192 0
193 1
194 4
195 9
196 16
197
198 but, if instead of C< say for @$pow > you had written C< map {say} @$pow >, perl
199 will try to expand C< @$pow > in list context, and it will not know when to
200 stop, since it only checks at the beginning. the solution, in short, is to only
201 dereference variable length generators in slice C< @$gen[0 .. 10] > or iterator
202 C< ... for @$gen; > context, and never in list context.
203
204 in general, it makes more sense (and is faster) to build your constraint into
205 the calling code:
206
207 my $pow = gen {$_**2};
208 for (@$gen) {
209 last if $_ > 20;
210 say;
211 }
212
213
214 =head2 recursive generators
215
216 the fibonacci sequence can be generated from the following definition:
217
218 f[0] = 0;
219 f[1] = 1;
220 f[n] = f[n-1] + f[n-2];
221
222 here are a few ways to write that definition as a generator:
223
224 my $fib; $fib = cache gen {$_ < 2 ? $_ : $$fib[$_ - 1] + $$fib[$_ - 2]};
225
226 my $fib = gen {$_ < 2 ? $_ : self($_ - 1) + self($_ - 2)}
227 ->cache
228 ->recursive;
229
230 my $fib; $fib = gen {$fib->($_ - 1) + $fib->($_ - 2)}
231 ->overlay( 0 => 0, 1 => 1 )
232 ->cache;
233
234 my $fib; $fib = gen {$$fib[$_ - 1] + $$fib[$_ - 2]}->cache->overlay;
235 @$fib[0, 1] = (0, 1);
236
237 bringing all those techniques together:
238
239 my $fib = gen {self($_ - 1) + self($_ - 2)}
240 ->overlay( 0 => 0, 1 => 1 )
241 ->cache
242 ->recursive;
243
244 the C< cache > function is used in each example because the recursive definition
245 of the fibonacci sequence would generate an exponentially increasing number of
246 calls to itself as the list grows longer. C< cache > prevents any index from
247 being calculated more than once.
248
249 =head3 more ways to write the fibonacci sequence
250
251 my $fib = <0, 1, *+*...>; >>
252
253 my $fib = <0, 1, {$^a + $^b}...>; >>
254
255 my $fib = ([0, 1] + iterate {sum self($_, $_ + 1)})->rec; >>
256
257 my $fib = ([0, 1] + iterate {sum fib($_, $_ + 1)})->rec('fib'); >>
258
259 my $fib = (iterate {$_ < 2 ? $_ : sum self($_ - 1, $_ - 2)})->rec; >>
260
261 my $fib; $fib = cache gen {$_ < 2 ? $_ : sum $fib->($_ - 1, $_ - 2)}; >>
262
263 =head3 a few ways to write the factorial sequence
264
265 my $fac = <[*..] 1, 1..>;
266
267 my $fac = <1, 1..>->scan('*');
268
269 my $fac = 1 + repeat(1)->scan('+')->scan('*');
270
271 my $fac = <1, **_...>;
272
273 =head2 stream generators
274
275 here is an example of a sieve of eratosthenes implemented with generators:
276
277 my $primes = do {
278 my $src = <2..>;
279 iterate {
280 my ($x, $xs) = $src->x_xs;
281 $src = $xs->grep_stream(sub {$_ % $x});
282 $x
283 }
284 };
285
286 in this example, the list is filtered with C< grep_stream/filter_stream > since
287 the algorithm only reads the source once, and reads it in order. a regular
288 C< filter/grep > call could be used, but it would unnecessarily use up a lot
289 of memory since each call would have to build up a new random-access cache.
290
291 the inefficiency addressed above could also be fixed by modifying the filtering
292 function itself:
293
294 my $primes = do {
295 my @p;
296 <2..>->grep(sub {
297 my $i = $_;
298 $i % $_ or return for @p;
299 push @p, $i;
300 })
301 };
302
303 of course if you want prime numbers, just use the C< primes > function:
304
305 my $primes = List::Gen::primes;
306
307 which is implemented as a precomputed sieve of eratosthenes in a string buffer.
308 initially it is ready to test the primality of numbers below 1000. if a higher
309 number is checked, the sieve will grow to 10 times larger than that value.
310 beyond 1e7 primes are checked with simple trial division.
311
312 =head2 printing generators
313
314 there are a variety of methods available for printing out the contents of a
315 generator:
316
317 my $gen = <1..5>;
318
319 say $gen->str; # 1 2 3 4 5
320 $gen->say; # 1 2 3 4 5
321 $gen->print; # same as: print $gen;
322
323 say $gen->perl; # [1, 2, 3, 4, 5]
324 $gen->dump; # [1, 2, 3, 4, 5]
325
326 if your generator is longer than you would like to print, such as an infinite
327 generator, passing a number to any of the methods above will limit the number
328 of elements printed.
329
330 <1..>->say(5); # 1 2 3 4 5
331
332 which is the same as
333
334 <1..>->take(5)->say; # 1 2 3 4 5
335
336 if passed an additional argument, that string will be included in the output
337 whenever the printing method needs to truncate a generator.
338
339 say <1..>->perl(5, '...'); # [1, 2, 3, 4, 5, ...]
340
341 these methods are recursive and will expand elements that are generators or
342 array references.
343
344 list(<1..>, <a..>, <A..>)->dump(3, '...');
345
346 # [[1, 2, 3, ...], ['a', 'b', 'c', ...], ['A', 'B', 'C', ...]]
347
348 <1..>->tuples(<a..>)->dump(3); # [[1, 'a'], [2, 'b'], [3, 'c']]
349
350 a target file handle can be passed as the first argument:
351
352 <1..>->dump(*STDERR, 5);
353
354 the C<say>, C<print>, and C<dump> methods all return the generator they were
355 called on for easy chaining.
356
357 <1..>->say(5)->map('**2')->say(5);
358 # 1 2 3 4 5
359 # 1 4 9 16 25
360
361 =head2 debugging generators
362
363 in addition to the methods to print generators, there are several methods
364 dedicated to debugging:
365
366 <0..>->debug;
367 # debug: List::Gen::erator::_20=ARRAY(0x2d07bfc)
368 # type: List::Gen::Range
369 # source: none
370 # mutable: no
371 # stream: no
372 # range: [0 .. inf]
373 # index: 0
374 # perl: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...]
375 # at file.pl line 12
376
377 pass C< debug > a number to control how many elements are printed.
378
379 my $gen = <0..>->watch('range')
380 ->grep('even')->watch('grep')
381 ->map('**2')->watch('map')
382 ->map('"[$_]"');
383
384 local $\ = ', '; # watch ends lines with $\ if defined or with $/
385
386 say $gen->(0); # range: 0, range: 1, range: 2, grep: 0, map: 0, [0]
387 say $gen->(1); # range: 3, range: 4, grep: 2, map: 4, [4]
388 say $gen->(2); # range: 5, range: 6, grep: 4, map: 16, [16]
389
390 C<watch> can also be passed a file handle to print to.
391
392 =head1 AUTHOR
393
394 Eric Strom, C<< <asg at cpan.org> >>
395
396 =head1 COPYRIGHT & LICENSE
397
398 copyright 2009-2011 Eric Strom.
399
400 this program is free software; you can redistribute it and/or modify it under
401 the terms of either: the GNU General Public License as published by the Free
402 Software Foundation; or the Artistic License.
403
404 see http://dev.perl.org/licenses/ for more information.
405
406 =cut
407
408
409 __PACKAGE__ if 'first require';