| 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'; |