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

filter: Statementstmt 0.0% 0 / 233 Branchbran 0.0% 0 / 98 Conditioncond 0.0% 0 / 66 MC/DCmcdc n/a Subroutinesub 0.0% 0 / 23 Podpod 0.0% 0 / 15 totaltotal 0.0% 0 / 435 SCAR 75.9
CC
44
Cov
0%
fn
240.0
lazyflatten
210.0
lazypipe
72.0
CRAP 1980.0
1 package List::Gen::Lazy;
2 use lib '../../';
3 use List::Gen ();
4 for my $method (qw(import VERSION)) {
5 *$method = sub {
6 splice @_, 0, 1, 'List::Gen';
7 goto &{List::Gen->can($method)}
8 }
9 }
10
11 package
12 List::Gen;
13 use strict;
14 use warnings;
15 use Scalar::Util 'set_prototype';
16 our $LOOKAHEAD = 0;
17 push our @lazy_export, qw (lazy L lazyx Lx Lazy Lazyx lazypipe lazyflatten fn now stream);
18 push our (@EXPORT_OK), @lazy_export;
19 $List::Gen::EXPORT_TAGS{':lazy'} = \@lazy_export;
20 no if $] > 5.012, warnings => 'illegalproto';
21
22
23 =head1 NAME
24
25 List::Gen::Lazy - perl6 / haskell like laziness in perl5
26
27 =head1 SYNOPSIS
28
29 this module provides tools to implement perl6/haskell style lazy programming
30 in perl5.
31
32 this module is a mixin to L<List::Gen> that adds functions to C< List::Gen's >
33 namespace and exportable function list
34
35 =head1 FUNCTIONS
36
37 =over 8
38
39 =item lazypipe C< LIST >
40
41 C< lazypipe > provides a lazy list implementation that will expand generators.
42
43 two methods are provided, C<< ->next >> which returns the next item from the
44 pipe, and C<< ->more >> which returns true if there are more items in the pipe.
45 the pipe works with aliases to its argument list, and never touches or copies
46 any items until it has to.
47
48 C< lazypipe > provides the behavior of the C< lazy > generator.
49
50 =item lazyflatten C< LIST >
51
52 C< lazyflatten > is just like C< lazypipe > except it will also expand array
53 references and subroutines.
54
55 C< lazyflatten > provides the behavior of the C< lazyx > generator.
56
57 =item lazy C< LIST >
58
59 =item L C< LIST >
60
61 C< lazy > is a C< lazypipe > wrapped inside of an iterative generator.
62 if C< LIST > is one item, and is already a generator, that generator is
63 returned unchanged.
64
65 =item lazyx C< LIST >
66
67 =item Lx C< LIST >
68
69 C< lazyx > is a C< lazyflatten > wrapped inside of an iterative generator.
70 if C< LIST > is one item, and is already a generator, that generator is
71 returned unchanged.
72
73 =item fn C< CODE [ARITY] [RETURNS] >
74
75 C< fn > converts a subroutine into a subroutine with partial application and
76 lazy evaluation.
77
78 my $add3 = fn {$_[0] + $_[1] + $_[2]} 3;
79 my $add2 = $add3->(my $first);
80 my $add1 = $add2->(my $second);
81
82 my $sum1 = $add1->(4);
83 my $sum2 = $add1->(8);
84 $first = 10;
85 $second = 100;
86 say $sum1; # prints 114
87
88 $second = 800;
89 say $sum1; # still prints 114
90 say $sum2; # prints 818
91
92 C< fn > supports subroutine prototypes, and can determine C< ARITY > from them.
93 C< ARITY > defaults to 1, with a prototype of C< (@) >. C< ARITY > can be given
94 as a prototype string C< '&@' > or an integer.
95
96 the C< RETURNS > defaults to 1, and specifies the number of values that will
97 be returned by the function (the number of thunk accessors to create). for
98 example, the C< splitAt > function in L<List::Gen::Haskell> is implemented as:
99
100 *splitAt = fn {take(@_), drop(@_)} 2, 2;
101
102 my ($xs, $ys) = splitAt(3, <1..>); # 2 thunk accessors are created but
103 # take() and drop() have not been called
104 say $xs->str; # 1 2 3
105 say $ys->str(5); # 4 5 6 7 8
106
107 due to partial application, you can even call subs in a way that looks a bit
108 like the haskell type signature, should you so desire.
109
110 my ($xs, $ys) = splitAt -> (3) -> (<1..>);
111
112 most of the functions in L<List::Gen::Haskell> are implemented with C< fn >
113
114 =item now C< LIST >
115
116 sometimes the return values of C< fn {...} > are too lazy. C< now > will force
117 the values in C< LIST > to evaluate, and will return the new list.
118
119 now(...) ~~ grep {!$_ or 1} ...
120
121 =item methods of C< fn {...} > functions
122
123 return values of C< fn {...} > have the following overloaded behaviors and
124 methods
125
126 $fn . $code $fn->compose($code) sub {$fn->(&$code)}
127 $fn << $val $fn->curry($val) sub {$fn->($val, @_)}
128 $fn >> $val $fn->rcurry($val) sub {$fn->(@_, $val)}
129 ~$fn $fn->flip sub {$fn->(@_[reverse 0 .. $#_])}
130
131 some more complex examples, assuming the functions from L<List::Gen::Haskell>
132
133 my $second = \&head . \&tail;
134
135 my $third = \&head . \&tail . \&tail;
136
137 my $join = \&foldl << sub {$_[0] . $_[1]};
138
139 my $ucjoin = sub {uc $_[0]} . $join;
140
141 my $cycle = \&cycle << '[' >> ']';
142
143 my $joined_cycle = $ucjoin . take(18) . $cycle;
144
145 say $joined_cycle->(qw(1 a 2 b)); # '[1A2B][1A2B][1A2B]'
146
147 the overloaded operators for functions do not seem to work properly in perl's
148 before 5.10. the corresponding methods can be used instead.
149
150 =cut
151
152
153 sub lazypipe {
154 my ($pipe, $pos, $size) = (\@_, 0, 0);
155 my ($fetch, $src, $mutable);
156 curse {
157 next => sub {
158 top: until ($size) {
159 @$pipe or return;
160 $src = shift @$pipe;
161 $src = $$src->() if ref $src eq 'List::Gen::Thunk';
162 ($size, $fetch) = isagen($src) ? do {
163 $mutable = $src->is_mutable && tied(@$src)->can('fsize');
164 ($src->size, tied(@$src)->can('FETCH'))
165 } : (1, undef)
166 }
167 if ($fetch) {
168 my $got = cap $fetch->(undef, $pos);
169 $size = $mutable->() if $mutable;
170 if ($size <= $pos) {
171 $size = $pos = 0;
172 goto top;
173 }
174 $size = $pos = 0 if ++$pos >= $size;
175 return wantarray ? @$got : pop @$got;
176 } else {
177 $size = 0;
178 return $src
179 }
180 },
181 more => sub {@$pipe or $pos < $size},
182 } => 'List::Gen::Pipe'
183 }
184
185 sub lazyflatten {
186 my ($pipe, $pos, $size) = (\@_, 0, 0);
187 my ($type, $src, $ref, $mutable);
188 my $next = sub {
189 shift_pipe: until ($size) {
190 @$pipe or return;
191 $src = shift @$pipe;
192 $src = $$src->() if ref $src eq 'List::Gen::Thunk';
193 ($size, $type) = do {
194 if ($ref = ref $src) {
195 if ($ref eq 'ARRAY') {
196 (0 + @$src, 'array')
197 }
198 elsif (List::Gen::isagen $src) {
199 $mutable = tied(@$src)->mutable;
200 ($src->size, 'gen')
201 }
202 elsif (eval {$src->isa('List::Gen::Pipe')}) {
203 ($src->more, 'pipe')
204 }
205 else {1}
206 }
207 else {1}
208 }
209 }
210 my $got;
211 if ($type) {
212 if ($type eq 'array') {
213 $got = \$$src[$pos]
214 }
215 elsif ($type eq 'gen') {
216 $got = \$src->get($pos);
217 $size = $src->size if $mutable;
218 if ($pos >= $size) {
219 goto shift_pipe
220 }
221 }
222 else {
223 $got = \$src->next;
224 $size = $src->more
225 }
226 } else {
227 if ($ref eq 'CODE') {
228 defined ${$got = \$src->()}
229 ? $pos--
230 : do {
231 $pos = $size = 0;
232 goto shift_pipe
233 }
234 }
235 else {$got = \$src}
236 }
237 if (++$pos >= $size) {
238 $pos = $size = 0
239 }
240 $$got
241 };
242 curse {
243 next => $next,
244 more => sub {@$pipe or $pos < $size},
245 } => 'List::Gen::Pipe'
246 }
247
248 my $lazy = sub {
249 my $pipe = shift;
250 $pipe->more or return empty;
251 iterate_multi {
252 my $x = cap $pipe->next;
253 $pipe->more or @$x ? done @$x : done;
254 @$x
255 }
256 };
257
258 sub lazy {
259 if (@_ == 1 and ref $_[0]) {
260 return $_[0] if isagen $_[0];
261 return &makegen($_[0]) if ref $_[0] eq 'ARRAY';
262 }
263 $lazy->(&lazypipe)
264 }
265
266 sub lazyx {@_ == 1 && ref $_[0] && isagen($_[0]) or $lazy->(&lazyflatten)}
267 BEGIN {
268 *L = *lazy;
269 *Lx = *lazyx;
270 }
271 sub Lazy {$lazy->(&lazypipe)}
272 sub Lazyx {$lazy->(&lazyflatten)}
273
274 my $set_proto = sub {bless set_prototype(\&{$_[1]}, $_[0]), 'List::Gen::Function'};
275
276 my $fn = \&fn;
277 my ($proto_init, $proto_tail, $will_return);
278 our $proto_split;
279 {
280 my %will_return;
281 my $proto_chunk = qr/ \\? (?: [\%\@\*\$\&_]| \[ [^\]]+ \] ) /x;
282
283 $proto_tail = sub {(my $proto = $_[0]) =~ s/^$proto_chunk//; $proto};
284 $proto_init = sub {
285 my ($head, $tail) = $_[0] =~ /^([^;]*)(;.*)?$/;
286 $head =~ s/($proto_chunk)$//;
287
288 (($1 eq '@' and substr($head, -1) ne '@') or $1 eq '%')
289 ? $_[0]
290 : join('', grep defined, $head, $tail)
291 };
292 $proto_split = sub {$_[0] =~ /$proto_chunk/go};
293 $will_return = sub {$will_return{$_[0]} or 1};
294
295 sub fn (&@) {
296 my $code = shift;
297 my $proto = prototype($code) || '@';
298
299 my $need;
300 if (@_) {
301 if (defined $_[0] and $_[0] =~ /^\d+$/) {
302 $need = shift;
303 } else {
304 $proto = shift || '@';
305 }
306 }
307
308 my $returns = @_ ? shift : $will_return{$code} || 1;
309
310 my ($head) = $proto =~ /^([^;]*)(?:;.*)?$/
311 or carp "unsupported prototype: $proto";
312
313 unless (defined $need) {
314 $need = (()= $head =~ /$proto_chunk/go);
315 }
316 if ($need > 1 and $proto eq '@') {
317 $proto = ('@' x $need)
318 }
319 (my $next_proto = $proto) =~ s/^$proto_chunk//o;
320
321 my $self;
322 $self = my $ret = $set_proto->($proto, sub {
323 return $self unless @_;
324 my $args = \@_;
325
326 if (@_ < $need) {
327 &fn ($set_proto->($next_proto,
328 sub {$code->(@$args, @_)}
329 ), $need - @_, $returns)
330 }
331 elsif (@_ >= $need) {
332 my $thunk = sub {$code->(@$args)};
333 my $data;
334 if ($returns == 1) {
335 bless \sub {
336 unless ($data) {
337 $data = \scalar $thunk->();
338 $data = \$$$data->() if ref $$data eq 'List::Gen::Thunk';
339 undef $thunk;
340 }
341 $$data
342 } => 'List::Gen::Thunk'
343 } else {
344 map {
345 my $n = $_ - 1;
346 bless \sub {
347 unless ($data) {
348 $data = sub {\@_}->(map {
349 ref eq 'List::Gen::Thunk' ? $$_->() : $_
350 } $thunk->());
351 undef $thunk;
352 }
353 $$data[$n]
354 } => 'List::Gen::Thunk'
355 } 1 .. $returns
356 }
357 }
358 });
359 Scalar::Util::weaken($self);
360 if ($returns > 1) {
361 $will_return{$ret} = $returns;
362 }
363 $ret
364 }
365 }
366
367 {package
368 List::Gen::Function;
369 use overload fallback => 1,
370 '.' => \&compose,
371 '~' => \&flip,
372 (map {$_ => \& curry} qw(< <<)),
373 (map {$_ => \&rcurry} qw(> >>));
374
375 my $wrap = do {
376 sub {
377 my $src_fn = shift;
378 unless (ref $src_fn eq 'List::Gen::Bare::Function') {
379 push @_, $will_return->($src_fn);
380 goto &$fn;
381 }
382 my ($code, $proto) = @_;
383 $proto ||= '@';
384 bless Scalar::Util::set_prototype(\&$code, $proto), 'List::Gen::Bare::Function';
385 }
386 };
387
388 sub compose {
389 my ($x, $y) = @_;
390 ($x, $y) = ($y, $x) if $_[2];
391
392 $wrap->($x, sub {$x->(&$y)}, prototype $y)
393 }
394 sub curry {
395 my $x = shift;
396 my $y = \$_[0];
397 my $proto = prototype $x;
398 my $new_proto = $proto =~ /^\@(?!\@)/ ? $proto : $proto_tail->($proto);
399
400 $wrap->($x, sub {$x->($$y, @_)}, $new_proto);
401 }
402 sub rcurry {
403 my $x = shift;
404 my $y = \$_[0];
405 $wrap->($x, sub {$x->(@_, $$y)}, $proto_init->(prototype $x));
406 }
407 sub flip {
408 my $x = shift;
409 my ($head, $tail) = (prototype($x) || '@') =~ /^([^;]+)(.*)/;
410 my $new_proto = (join '' => reverse $proto_split->($head)).$tail;
411
412 $wrap->($x, sub {$x->(@_[reverse 0 .. $#_])}, $new_proto);
413 }
414 }
415
416 {package
417 List::Gen::Bare::Function;
418 our @ISA = 'List::Gen::Function';
419 }
420
421 {package
422 List::Gen::Thunk;
423 use overload fallback => 1,
424 '&{}' => sub {
425 $_[0] = ${$_[0]}->();
426 List::Gen::isagen($_[0]) ? $_[0]->_overloader : $_[0]
427 },
428 map {$_ => sub {$_[0] = ${$_[0]}->()}} qw( bool "" 0+ @{} %{} *{} );
429
430 sub DESTROY {}
431 sub AUTOLOAD {
432 my $method = substr our $AUTOLOAD, 2 + length __PACKAGE__;
433 if (defined wantarray and not wantarray) {
434 my $args = \@_;
435 bless \sub {
436 $$args[0] = ${$$args[0]}->() if ref $$args[0] eq 'List::Gen::Thunk';
437 print "lazy call: $$args[0]\->$method(@$args[1..$#$args])\n"
438 if List::Gen::DEBUG;
439 my $code = $$args[0]->can($method) or Carp::croak("no method '$method'");
440 $code->(splice @$args);
441 }
442 } else {
443 $_[0] = ${$_[0]}->();
444 goto & {$_[0]->can($method) or Carp::croak("no method '$method'")}
445 }
446 }
447 }
448
449 sub now {
450 for (@_) {
451 $_ = $$_->() while ref eq 'List::Gen::Thunk'
452 }
453 wantarray ? @_ : pop
454 }
455
456
457 =back
458
459 =head1 AUTHOR
460
461 Eric Strom, C<< <asg at cpan.org> >>
462
463 =head1 BUGS
464
465 report any bugs / feature requests to C<bug-list-gen at rt.cpan.org>, or through
466 the web interface at L<http://rt.cpan.org/NoAuth/ReportBug.html?Queue=List-Gen>.
467
468 comments / feedback / patches are also welcome.
469
470 =head1 COPYRIGHT & LICENSE
471
472 copyright 2009-2011 Eric Strom.
473
474 this program is free software; you can redistribute it and/or modify it under
475 the terms of either: the GNU General Public License as published by the Free
476 Software Foundation; or the Artistic License.
477
478 see http://dev.perl.org/licenses/ for more information.
479
480 =cut
481
482
483 'List::Gen::Lazy' if 'first require';