Permalink
Fetching contributors…
Cannot retrieve contributors at this time
423 lines (308 sloc) 13.1 KB
=begin pod
=TITLE role Iterator
=SUBTITLE Generic API for producing a sequence of values
=for code :skip-test<compile time error>
constant IterationEnd
role Iterator { }
A C<Iterator> is an object that can generate or provide elements of a
sequence. Users usually don't have to care about iterators, their usage
is hidden behind iteration APIs such as C<for @list { }>, L<map>,
L<grep>, L<head>, L<tail>, L<skip> and list indexing with C<.[$idx]>.
The main API is the C<pull-one> method, which either returns the next
value, or the sentinel value C<IterationEnd> if no more elements are
available. Each class implementing C<Iterator> B<must> provide a
C<pull-one> method. All other non-optional Iterator API methods are
implemented in terms of C<pull-one>, but can also be overridden by
consuming classes for performance or other reasons. There are also
optional Iterator API methods that will only be called if they are
implemented by the consuming class: these are B<not> implemented by the
Iterator role.
X<|IterationEnd>
=head1 IterationEnd
Iterators only allow one iteration over the entire sequence. It's
forbidden to make attempts to fetch more data, once C<IterationEnd> has
been generated, and behavior for doing so is undefined. For example, the
following L<Seq> will not cause the L<die> to be called under normal
use, because L<pull-one> will never be called after it returns
C<IterationEnd>:
=begin code
class SkippingArray is Array {
# skip all undefined values while iterating
method iterator {
class :: does Iterator {
has $.index is rw = 0;
has $.array is required;
method pull-one {
$.index++ while !$.array.AT-POS($.index).defined && $.array.elems > $.index;
$.array.elems > $.index ?? $.array.AT-POS($.index++) !! IterationEnd
}
}.new(array => self)
}
}
my @a := SkippingArray.new;
@a.append: 1, Any, 3, Int, 5, Mu, 7;
for @a -> $a, $b {
say [$a, $b];
}
# OUTPUT: «[1 3]␤[5 7]␤»
=end code
The only valid use of the sentinel value C<IterationEnd> in a program is
identity comparison (using C<=:=>) with the result of a method in the
iterator API. Any other behavior is undefined and implementation
dependent.
Please bear in mind that C<IterationEnd> is a constant, so if you are
going to compare it against the value of a variable, this variable will
have to be bound, not assigned. Comparing directly to the output of
C<pull-one> will work.
=begin code
my $it = (1,2).iterator;
$it.pull-one for ^2;
say $it.pull-one =:= IterationEnd; # OUTPUT: «True␤»
=end code
However, if we use a variable we and we assign it, the result will be
incorrect:
=begin code
my $it = (1,2).iterator;
$it.pull-one for ^2;
my $is-it-the-end = $it.pull-one;
say $is-it-the-end =:= IterationEnd; # OUTPUT: «False␤»
=end code
So we'll have to bind the variable to make it work:
=begin code :preamble<my $it>
my $is-it-the-end := $it.pull-one;
say $is-it-the-end =:= IterationEnd; # OUTPUT: «True␤»
=end code
=head1 Methods
=head2 method pull-one
Defined as:
method pull-one(Iterator:D: --> Mu)
This method stub ensures that classes implementing the C<Iterator> role
provide a method named C<pull-one>.
The C<pull-one> method is supposed to produce and return the next value if
possible, or return the sentinel value C<IterationEnd> if no more values could
be produced.
my $i = (1 .. 3).iterator;
say $i.pull-one; # OUTPUT: «1␤»
say $i.pull-one; # OUTPUT: «2␤»
say $i.pull-one; # OUTPUT: «3␤»
say $i.pull-one.perl; # OUTPUT: «IterationEnd␤»
As a more illustrative example of its use, here is a count down iterator along with
a simplistic subroutine re-implementation of the C<for> loop.
# works the same as (10 ... 1, 'lift off')
class CountDown does Iterator {
has Int:D $!current = 10;
method pull-one ( --> Mu ) {
my $result = $!current--;
if $result == 0 { return 'lift off' }
if $result == -1 { return IterationEnd }
# calling .pull-one again after it returns IterationEnd is undefined
if $result <= -2 {
# so for fun we will give them nonsense data
return (1..10).pick;
}
return $result;
}
}
sub for( Iterable:D $sequence, &do --> Nil ) {
my Iterator:D $iterator = $sequence.iterator;
loop {
# must bind the result so that =:= works
my Mu $pulled := $iterator.pull-one;
# always check the result and make sure that .pull-one
# is not called again after it returns IterationEnd
if $pulled =:= IterationEnd { last }
do( $pulled );
}
}
for( Seq.new(CountDown.new), &say ); # OUTPUT: «10␤9␤8␤7␤6␤5␤4␤3␤2␤1␤lift off␤»
It would be more idiomatic to use C<while> or C<until>, and a sigilless variable.
=begin code :preamble<my $iterator = ().iterator; my &do = &say>
until IterationEnd =:= (my \pulled = $iterator.pull-one) {
do( pulled );
}
=end code
=head2 method push-exactly
Defined as:
method push-exactly(Iterator:D: $target, int $count --> Mu)
Should produce C<$count> elements, and for each of them, call
C<$target.push($value)>.
If fewer than C<$count> elements are available from the iterator, it
should return the sentinel value C<IterationEnd>. Otherwise it should return
C<$count>.
my @array;
say (1 .. ∞).iterator.push-exactly(@array, 3); # OUTPUT: «3␤»
say @array; # OUTPUT: «[1 2 3]␤»
The Iterator role implements this method in terms of C<pull-one>. In general,
this is a method that is not intended to be called directly from the end user
who, instead, should implement it in classes that mix the iterator role. For
instance, this class implements that role:
=begin code
class DNA does Iterable does Iterator {
has $.chain;
has Int $!index = 0;
method new ($chain where {
$chain ~~ /^^ <[ACGT]>+ $$ / and
$chain.chars %% 3 } ) {
self.bless( :$chain );
}
method iterator( ){ self }
method pull-one( --> Mu){
if $!index < $.chain.chars {
my $codon = $.chain.comb.rotor(3)[$!index div 3];
$!index += 3;
return $codon;
} else {
return IterationEnd;
}
}
method push-exactly(Iterator:D: $target, int $count --> Mu) {
return IterationEnd if $.chain.elems / 3 < $count;
for ^($count) {
$target.push: $.chain.comb.rotor(3)[ $_ ];
}
}
};
my $b := DNA.new("AAGCCT");
for $b -> $a, $b, $c { say "Never mind" }; # Does not enter the loop
my $þor := DNA.new("CAGCGGAAGCCT");
for $þor -> $first, $second {
say "Coupled codons: $first, $second";
# OUTPUT: «Coupled codons: C A G, C G G␤Coupled codons: A A G, C C T␤»
}
=end code
This code, which groups DNA chains in triplets (usually called I<codons>)
returns those codons when requested in a loop; if too many are requested, like
in the first case C«for $b -> $a, $b, $c», it simply does not enter the loop
since C<push-exactly> will return C<IterationEnd> since it is not able to serve
the request for exactly 3 codons. In the second case, however, it requests
exactly two codons in each iteration of the loop; C<push-exactly> is being
called with the number of loop variables as the C<$count> variable.
=head2 method push-at-least
Defined as:
method push-at-least(Iterator:D: $target, int $count --> Mu)
Should produce at least C<$count> elements, and for each of them, call
C<$target.push($value)>.
If fewer than C<$count> elements are available from the iterator, it
should return the sentinel value C<IterationEnd>. Otherwise it should return
C<$count>.
Iterators with side effects should produce exactly C<$count> elements;
iterators without side effects (such as L<Range|/type/Range> iterators) can
produce more elements to achieve better performance.
my @array;
say (1 .. ∞).iterator.push-at-least(@array, 10); # OUTPUT: «10␤»
say @array; # OUTPUT: «[1 2 3 4 5 6 7 8 9 10]␤»
The Iterator role implements this method in terms of C<pull-one>. In
general, it is also not intended to be called directly as in the example
above. It can be implemented, if unhappy with this default
implementation, by those using this role. See
L<the documentation for C<push-exactly>|/type/Iterator#method_push-exactly>
for an example implementation.
=head2 method push-all
Defined as:
method push-all(Iterator:D: $target)
Should produce all elements from the iterator and push them to C<$target>.
my @array;
say (1 .. 1000).iterator.push-all(@array); # All 1000 values are pushed
The Iterator role implements this method in terms of C<push-at-least>. As in the
case of the other C<push-*> methods, it is mainly intended for developers
implementing this role. C<push-all> is called when assigning an object with this
role to an array, for instance, like in this example:
=begin code
class DNA does Iterable does Iterator {
has $.chain;
has Int $!index = 0;
method new ($chain where {
$chain ~~ /^^ <[ACGT]>+ $$ / and
$chain.chars %% 3 } ) {
self.bless( :$chain );
}
method iterator( ){ self }
method pull-one( --> Mu){
if $!index < $.chain.chars {
my $codon = $.chain.comb.rotor(3)[$!index div 3];
$!index += 3;
return $codon;
} else {
return IterationEnd;
}
}
method push-all(Iterator:D: $target) {
for $.chain.comb.rotor(3) -> $codon {
$target.push: $codon;
}
}
};
my $b := DNA.new("AAGCCT");
my @dna-array = $b;
say @dna-array; # OUTPUT: «[(A A G) (C C T)]␤»
=end code
The C<push-all> method implemented pushes to the target iterator in lists of
three aminoacid representations; this is called under the covers when we assign
C<$b> to C<@dna-array>.
=head2 method push-until-lazy
Defined as:
method push-until-lazy(Iterator:D: $target --> Mu)
Should produce values until it considers itself to be lazy, and push them onto
C<$target>.
The Iterator role implements this method as a no-op if C<is-lazy> returns
a True value, or as a synonym of C<push-all> if not.
This matters mostly for iterators that have other iterators embedded, some of
which might be lazy, while others aren't.
=head2 method is-lazy
Defined as:
method is-lazy(Iterator:D: --> Bool:D)
Should return C<True> for iterators that consider themselves lazy, and C<False>
otherwise.
Built-in operations that know that they can produce infinitely many values
return C<True> here, for example C<(1..6).roll(*)>.
say (1 .. 100).is-lazy; # OUTPUT: «False␤»
say (1 .. ∞).is-lazy; # OUTPUT: «True␤»
The Iterator role implements this method returning C<False>, indicating a
non-lazy iterator.
=head2 method sink-all
Defined as:
method sink-all(Iterator:D: --> IterationEnd)
Should exhaust the iterator purely for the side-effects of producing the
values, without actually saving them in any way. Should always return
C<IterationEnd>. If there are no side-effects associated with producing a
value, then it can be implemented by a consuming class to be a virtual no-op.
say (1 .. 1000).iterator.sink-all; # OUTPUT: «IterationEnd␤»
The Iterator role implements this method as a loop that calls C<pull-one>
until it is exhausted.
=head2 method skip-one
Defined as:
method skip-one(Iterator:D: $target --> Mu)
Should skip producing one value. The return value should be truthy if the skip
was successful and falsy if there were no values to be skipped:
my $i = <a b>.iterator;
say $i.skip-one; say $i.pull-one; say $i.skip-one
# OUTPUT: «1␤b␤0␤»
The Iterator role implements this method as a call C<pull-one> and returning
whether the value obtained was not C<IterationEnd>.
=head2 method skip-at-least
Defined as:
method skip-at-least(Iterator:D: $target, int $to-skip --> Mu)
Should skip producing C<$to-skip> values. The return value should be truthy if
the skip was successful and falsy if there were not enough values to be skipped:
my $i = <a b c>.iterator;
say $i.skip-at-least(2); say $i.pull-one; say $i.skip-at-least(20);
# OUTPUT: «1␤c␤0␤»
The Iterator role implements this method as a loop calling C<skip-one> and
returning whether it returned a truthy value sufficient number of times.
=head2 method skip-at-least-pull-one
Defined as:
method skip-at-least-pull-one(Iterator:D: $target, int $to-skip --> Mu)
Should skip producing C<$to-skip> values and if the iterator is still not
exhausted, produce and return the next value. Should return C<IterationEnd>
if the iterator got exhausted at any point:
my $i = <a b c>.iterator;
say $i.skip-at-least-pull-one(2);
say $i.skip-at-least-pull-one(20) =:= IterationEnd;
# OUTPUT: «c␤True␤»
The Iterator role implements this method as calling C<skip-at-least> and
then calling C<pull-one> if it was not exhausted yet.
=head1 Predictive iterators
Please see the L<PredictiveIterator> role if your C<Iterator> can know
how many values it can still produce without actually producing them.
=end pod
# vim: expandtab softtabstop=4 shiftwidth=4 ft=perl6