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