FAQ 4.47 How do I handle circular lists?
PerlFAQ Server
comes with the standard Perl distribution. These postings aim to
reduce the number of repeated questions as well as allow the community
to review and update the answers. The latest version of the complete
perlfaq is at http://faq.perl.org .
--------------------------------------------------------------------
4.47: How do I handle circular lists?
Circular lists could be handled in the traditional fashion with linked
lists, or you could just do something like this with an array:
unshift(@array, pop(@array)); # the last shall be first
push(@array, shift(@array)); # and vice versa
You can also use "Tie::Cycle":
use Tie::Cycle;
tie my $cycle, 'Tie::Cycle', [ qw( FFFFFF 000000 FFFF00 ) ];
print $cycle; # FFFFFF
print $cycle; # 000000
print $cycle; # FFFF00
--------------------------------------------------------------------
The perlfaq-workers, a group of volunteers, maintain the perlfaq. They
are not necessarily experts in every domain where Perl might show up,
so please include as much information as possible and relevant in any
corrections. The perlfaq-workers also don't have access to every
operating system or platform, so please include relevant details for
corrections to examples that do not work on particular platforms.
Working code is greatly appreciated.
If you'd like to help maintain the perlfaq, see the details in
perlfaq.pod.
shei...@my-deja.com
> --------------------------------------------------------------------
>
> 4.47: How do I handle circular lists?
>
> Circular lists could be handled in the traditional fashion with linked
> lists, or you could just do something like this with an array:
>
> unshift(@array, pop(@array)); # the last shall be first
> push(@array, shift(@array)); # and vice versa
>
>
As the modulo operator provides a simple way to address an array in a
circular fashion, which is maybe not obvious to the less experienced,
I think it should be mentioned here.
my @Colours = qw( FFFFFF 000000 FFFF00 );
my $asize = @Colours;
my $index = 0;
for (1..10) {
print $Colours[$index], "\n";
$index = ++$index % $asize;
}
# or shorter, with an ever growing $index though:
$index = 0;
for (1..10) {
print $Colours[$index++ % $asize], "\n";
}
steffen
brian d foy
<437ac873-a0a5-4186...@k37g2000hsf.googlegroups.com>,
<shei...@my-deja.com> wrote:
> On May 12, 9:03 pm, PerlFAQ Server <br...@stonehenge.com> wrote:
> > --------------------------------------------------------------------
> >
> > 4.47: How do I handle circular lists?
> >
> > Circular lists could be handled in the traditional fashion with linked
> > lists, or you could just do something like this with an array:
> >
> > unshift(@array, pop(@array)); # the last shall be first
> > push(@array, shift(@array)); # and vice versa
> >
> >
>
> As the modulo operator provides a simple way to address an array in a
> circular fashion, which is maybe not obvious to the less experienced,
> I think it should be mentioned here.
That's a good idea. I should also mention Tie::Cycle.
I'll update the answer. Thanks. :)
szr
Tie::Cycle /is/ mentioned in this FAQ :-)
--
szr
John W. Krahn
> On May 12, 9:03 pm, PerlFAQ Server <br...@stonehenge.com> wrote:
>> --------------------------------------------------------------------
>>
>> 4.47: How do I handle circular lists?
>>
>> Circular lists could be handled in the traditional fashion with linked
>> lists, or you could just do something like this with an array:
>>
>> unshift(@array, pop(@array)); # the last shall be first
>> push(@array, shift(@array)); # and vice versa
>>
>>
>
> As the modulo operator provides a simple way to address an array in a
> circular fashion, which is maybe not obvious to the less experienced,
> I think it should be mentioned here.
>
> my @Colours = qw( FFFFFF 000000 FFFF00 );
>
> my $asize = @Colours;
> my $index = 0;
>
> for (1..10) {
> print $Colours[$index], "\n";
>
> $index = ++$index % $asize;
perldoc perlop
[ SNIP ]
Note that just as in C, Perl doesn’t define when the variable is
incremented or decremented. You just know it will be done sometime
before or after the value is returned. This also means that
modifying a variable twice in the same statement will lead to
undefined behaviour. Avoid statements like:
$i = $i ++;
print ++ $i + $i ++;
Perl will not guarantee what the result of the above statements is.
So don't do that. Do this instead:
$index = ( $index + 1 ) % $asize;
John
--
Perl isn't a toolbox, but a small machine shop where you
can special-order certain sorts of tools at low cost and
in short order. -- Larry Wall
shei...@my-deja.com
I've been reading that as 'sometime before' in case of a preincrement,
'after' for a postincrement.
In which case my
$index = ++$index % $asize;
looks fairly safe.
IMHO the expression above can result in an error only, if the
increment is first computed and returned and is assigned to $index
only after the modulo operation or even after the explicit assignment.
You may be right in that this can really happen. But then it's a very
strange behaviour indeed.
I've been using the autoincrement out of habit and for performance
considerations but agree that your suggestion certainly leaves no room
for error and is more readable anyway.
Cheers, Steffen
Peter J. Holzer
> On May 13, 3:11 pm, "John W. Krahn" <some...@example.com> wrote:
>> sheinr...@my-deja.com wrote:
>> > $index = ++$index % $asize;
>>
>> perldoc perlop
>>
>> [ SNIP ]
>>
>> Note that just as in C, Perl doesn’t define when the variable is
>> incremented or decremented. You just know it will be done sometime
>> before or after the value is returned. This also means that
>> modifying a variable twice in the same statement will lead to
>> undefined behaviour. Avoid statements like:
>>
>> $i = $i ++;
>> print ++ $i + $i ++;
>>
>> Perl will not guarantee what the result of the above statements is.
>>
>> So don't do that. Do this instead:
>>
>> $index = ( $index + 1 ) % $asize;
>>
>
> returned."
>
> I've been reading that as 'sometime before' in case of a preincrement,
> 'after' for a postincrement.
>
> In which case my
> $index = ++$index % $asize;
>
> looks fairly safe.
It may not be.
> IMHO the expression above can result in an error only, if the
> increment is first computed and returned and is assigned to $index
> only after the modulo operation or even after the explicit assignment.
Right. The compiler could produce something like:
$tmp1 = $index + 1
$tmp2 = $tmp1 % $asize
$index = $tmp2
$index = $tmp1
> You may be right in that this can really happen. But then it's a very
> strange behaviour indeed.
Not that strange for compilers which produce code for real CPUs (which
often have very strange timing requirements). I wouldn't really expect
it from a simple bytecode-generating compiler like perl's.
The warning that the execution order is undefined comes from C. But in C
this is a consequence of the concept of "sequence points". The language
defines certain points (e.g., the end of each statement, each function
call, etc.) where each previous operation must be finished and no
subsequent operation must have begun. between two sequence points the
compiler can reorder operations at will. There are two rules about
modifying values:
1) You can modify an object[1] only once between two sequence points
2) If you modify an object, you can only read it to compute the new
value.
But Perl doesn't have the concept of sequence points, and there is no
general prohibition agains modifying the same object twice in a
statement, just against using the increment and decrement operators.
That does stand out as an odd exception. IMHO Perl should either define
an execution order (which could be a partial order) or adopt a more
generic concept like that of C.
>
> I've been using the autoincrement out of habit and for performance
> considerations
Surprisingly,
$index = ++$index % $asize;
is really about 40 % faster than
$index = ( $index + 1 ) % $asize;
I had not expected this. Apparently creating a constant IV is a
relatively expensive operation (well, it takes about 36 nanoseconds on
my PC, so "relatively expensive" is, er, relative).
hp
shei...@my-deja.com
> On 2008-05-14 09:09, sheinr...@my-deja.com <sheinr...@my-deja.com> wrote:
>
> >> [ SNIP ]
And the restriction seems particularly odd for a language that
otherwise allows constructs like
@array[$k, $l] = @array[$l, $k];
Reading from the above, it probably wouldn't help to introduce some
strategical brackets, or would it?
$index = (++$index) % $asize;
Thank you,
Steffen
Dr.Ruud
> the restriction seems particularly odd for a language that
> otherwise allows constructs like
> @array[$k, $l] = @array[$l, $k];
>
> Reading from the above, it probably wouldn't help to introduce some
> strategical brackets, or would it?
> $index = (++$index) % $asize;
What don't you understand about "Note that just as in C, Perl doesn't
define when the variable is incremented or decremented. You just know it
will be done sometime before or after the value is returned. This also
means that modifying a variable twice in the same statement will lead to
undefined behaviour."?
--
Affijn, Ruud
"Gewoon is een tijger."
shei...@my-deja.com
> sheinr...@my-deja.com schreef:
You didn't read the thread, did you?
Above I wrote in answer to John:
> "You just know it will be done sometime before or after the value is
> returned."
>
> I've been reading that as 'sometime before' in case of a preincrement,
> 'after' for a postincrement.
From what the doc says it is quite understandable why the given
examples
$i = $i ++;
print ++ $i + $i ++;
should be avoided.
However, it is not so clear and at least can be subject of debate, if
the outcome of
$index = ++$index % $asize;
is also indeterminate.
"This also means that modifying a variable twice in the same statement
will lead to undefined behaviour."
This of course sounds prohibitive, easy enough. But does it hold true?
As I read it from Peter's contribution, some doubt about perl adopting
the intrinsic problems from the C legacy is quite reasonable.
Steffen
Dr.Ruud
> From what the doc says it is quite understandable why the given
> examples
> $i = $i ++;
> print ++ $i + $i ++;
> should be avoided.
> However, it is not so clear and at least can be subject of debate, if
> the outcome of
> $index = ++$index % $asize;
> is also indeterminate.
No, the issue is clear, so there is no use debating that:
"modifying a variable twice in the same statement will lead to undefined
behaviour".
Take care: "undefined behaviour" and "indeterminate" don't mean the
same.
The example
$i = $i ++;
looks very similar to
$index = ++$index % $asize;
so I can not fathom how that can confuse you.
All these examples don't matter when you have read and understood this:
"modifying a variable twice in the same statement will lead to undefined
behaviour".
This "undefined" includes that it can behave differently on different
platforms.
Peter J. Holzer
> shei...@my-deja.com schreef:
>
>> From what the doc says it is quite understandable why the given
>> examples
>> $i = $i ++;
>> print ++ $i + $i ++;
>> should be avoided.
>> However, it is not so clear and at least can be subject of debate, if
>> the outcome of
>> $index = ++$index % $asize;
>> is also indeterminate.
>
> No, the issue is clear, so there is no use debating that:
> "modifying a variable twice in the same statement will lead to undefined
> behaviour".
That sentence is very clear when taken out of context. Unfortunately, it
is much less clear in the context of perlop. Firstly, it is in the
section "Auto-increment and Auto-decrement", not in the section
"Assignment Operators". So does it only apply to ++ and -- or is
($i = 1) + ($i = 2)
also undefined? (it is in C)
Also what is "You just know it will be done sometime before or after the
value is returned." supposed to mean? Sometime between program start and
program end? Or maybe something more specific like sometime between
start and end of the current statement. And what is the current
statement anyway, if that can contain code blocks? If you allow
out-of-order execution in a programming language you need to be very
precise about the rules. Perlop is not precise. As a specification, it
is unusable (in this respect).
> Take care: "undefined behaviour" and "indeterminate" don't mean the
> same.
>
> The example
> $i = $i ++;
> looks very similar to
> $index = ++$index % $asize;
> so I can not fathom how that can confuse you.
He already wrote (twice!) that he understood "sometime before or after"
as "sometime before for the pre operators and sometime after for the
post operators". Given this misunderstanding it quite clear why he
believed that the second is well-defined but the first is not:
In the second case, the subexpression (++$index) assigns to index. But
that assignment occurs "sometime before" the result of the subextression
is returned. Since that value is needed to compute the value of
((++$index) % $asize) there is a clear and defined order of the two
assignments and the result is well-defined.
In the first case, the assignment of ($i ++) happens "sometime after"
the value is returned (this is stupid, of course and might have given a
hint that this interpretation was not the intended one). And of course
the assignment of the value of the subexpression to $i also happens
after that value has been determined. So the order of the two
assignments is undefined.
hp
szr
> On 2008-05-18 15:15, Dr.Ruud <rvtol...@isolution.nl> wrote:
>> shei...@my-deja.com schreef:
> That sentence is very clear when taken out of context. Unfortunately,
> it is much less clear in the context of perlop. Firstly, it is in the
> section "Auto-increment and Auto-decrement", not in the section
> "Assignment Operators". So does it only apply to ++ and -- or is
>
> ($i = 1) + ($i = 2)
>
> also undefined? (it is in C)
This seems quite defined to me; assignments occur first, going left to
right, so $i becomes 2 (ok, it becomes 1 and then immediately becomes
2), and then you add (+), resulting in 2 + 2, which of course is 4. This
seems to hold true across the board:
$ perl5.10.0 -Mstrict -we 'my $i=5; print(($i = 1) + ($i = 2), "\n")'
4
$ perl5.8.8 -Mstrict -we 'my $i=5; print(($i = 1) + ($i = 2), "\n")'
4
$ perl5.8.2 -Mstrict -we 'my $i=5; print(($i = 1) + ($i = 2), "\n")'
4
$ perl5.8.0 -Mstrict -we 'my $i=5; print(($i = 1) + ($i = 2), "\n")'
4
$ perl5.6.1 -Mstrict -we 'my $i=5; print(($i = 1) + ($i = 2), "\n")'
4
There seems to be no reason that this would be undefined.
--
szr
Ben Morrow
Quoth "szr" <sz...@szromanMO.comVE>:
> Peter J. Holzer wrote:
> > On 2008-05-18 15:15, Dr.Ruud <rvtol...@isolution.nl> wrote:
> >> shei...@my-deja.com schreef:
> [...]
> > That sentence is very clear when taken out of context. Unfortunately,
> > it is much less clear in the context of perlop. Firstly, it is in the
> > section "Auto-increment and Auto-decrement", not in the section
> > "Assignment Operators". So does it only apply to ++ and -- or is
> >
> > ($i = 1) + ($i = 2)
> >
> > also undefined? (it is in C)
>
> This seems quite defined to me; assignments occur first, going left to
> right, so $i becomes 2 (ok, it becomes 1 and then immediately becomes
> 2), and then you add (+), resulting in 2 + 2, which of course is 4. This
> seems to hold true across the board:
That's not the correct interpretation. Assignments happen as they are
needed, with the whole expression being evaluated in order of
precedence. What's weird is that ($i = 1) doesn't return 1, it returns
an alias to $i (presumably so expressions like
($i = "x") =~ s/x/y/;
can work correctly), which means sometimes assignments appear to
have happened earlier than they actually did. (This leads to the
bizarre fact that
($i = 1) = 2;
is valid Perl, whereas it certainly isn't valid C.)
For instance, this
~% perl -le'print +($i = 1) + ($i = 2) + ($i = 3)'
7
at first makes no sense, until you realise the order of evaluation is
1: $i = 1 # returns an alias to $i
2: $i = 2 # returns another alias to $i
3: add #1 and #2 # since $i is now 2, this returns 4
4: $i = 3 # returns another alias to $i
5: add #3 and #4 # since $i is now 3, this returns 7
It's important to realise that 'undefined' doesn't mean the same thing
in the Perl docs as it does in the C standard. In C, 'undefined'
basically means 'different implementations are allowed to do different
things'; since Perl only has one implementation, that doesn't apply. In
Perl, it means something more like 'perl's behaviour here is somewhat
subtle, and we don't promise not to change it'. Treating the perldocs as
a specification you can wave at people is rather silly: when perl's
behaviour doesn't match the docs, it's not given which will be treated
as 'correct'.
Ben
--
Every twenty-four hours about 34k children die from the effects of poverty.
Meanwhile, the latest estimate is that 2800 people died on 9/11, so it's like
that image, that ghastly, grey-billowing, double-barrelled fall, repeated
twelve times every day. Full of children. [Iain Banks] b...@morrow.me.uk
Peter J. Holzer
> Peter J. Holzer wrote:
>> On 2008-05-18 15:15, Dr.Ruud <rvtol...@isolution.nl> wrote:
>>> shei...@my-deja.com schreef:
> [...]
>> That sentence is very clear when taken out of context. Unfortunately,
>> it is much less clear in the context of perlop. Firstly, it is in the
>> section "Auto-increment and Auto-decrement", not in the section
>> "Assignment Operators". So does it only apply to ++ and -- or is
>>
>> ($i = 1) + ($i = 2)
>>
>> also undefined? (it is in C)
>
> This seems quite defined to me; assignments occur first, going left to
> right,
Where is this defined?
> so $i becomes 2 (ok, it becomes 1 and then immediately becomes
> 2), and then you add (+), resulting in 2 + 2, which of course is 4.
Which is something I would *not* have expected and reeks strongly of
undefined behaviour.
> This
> seems to hold true across the board:
>
> $ perl5.10.0 -Mstrict -we 'my $i=5; print(($i = 1) + ($i = 2), "\n")'
> 4
>
> $ perl5.8.8 -Mstrict -we 'my $i=5; print(($i = 1) + ($i = 2), "\n")'
> 4
>
> $ perl5.8.2 -Mstrict -we 'my $i=5; print(($i = 1) + ($i = 2), "\n")'
> 4
>
> $ perl5.8.0 -Mstrict -we 'my $i=5; print(($i = 1) + ($i = 2), "\n")'
> 4
>
> $ perl5.6.1 -Mstrict -we 'my $i=5; print(($i = 1) + ($i = 2), "\n")'
> 4
Irrelevant. Just because all implementations you have access to behave
the same doesn't mean the behaviour is defined.
hp
John W. Krahn
> Quoth "szr" <sz...@szromanMO.comVE>:
>> Peter J. Holzer wrote:
>>> On 2008-05-18 15:15, Dr.Ruud <rvtol...@isolution.nl> wrote:
>>>> shei...@my-deja.com schreef:
>> [...]
>>> That sentence is very clear when taken out of context. Unfortunately,
>>> it is much less clear in the context of perlop. Firstly, it is in the
>>> section "Auto-increment and Auto-decrement", not in the section
>>> "Assignment Operators". So does it only apply to ++ and -- or is
>>>
>>> ($i = 1) + ($i = 2)
>>>
>>> also undefined? (it is in C)
>> This seems quite defined to me; assignments occur first, going left to
>> right, so $i becomes 2 (ok, it becomes 1 and then immediately becomes
>> 2), and then you add (+), resulting in 2 + 2, which of course is 4. This
>> seems to hold true across the board:
>
> That's not the correct interpretation. Assignments happen as they are
> needed, with the whole expression being evaluated in order of
> precedence.
I've had this discussion on c.l.p.misc before and it has been (rightly)
pointed out to me that precedence does not determine order of evaluation.
Ben Morrow
Quoth "John W. Krahn" <kra...@telus.net>:
> Ben Morrow wrote:
> >
> > That's not the correct interpretation. Assignments happen as they are
> > needed, with the whole expression being evaluated in order of
> > precedence.
>
> I've had this discussion on c.l.p.misc before and it has been (rightly)
> pointed out to me that precedence does not determine order of evaluation.
Can you give me an example? I can't really see how the yacc parser can
produce anything else...
Ben
--
I have two words that are going to make all your troubles go away.
"Miniature". "Golf".
[b...@morrow.me.uk]
Michael Carman
> Peter J. Holzer wrote:
>>
>> ($i = 1) + ($i = 2)
>>
>> also undefined? (it is in C)
>
> This seems quite defined to me; assignments occur first, going left to
> right, so $i becomes 2 (ok, it becomes 1 and then immediately becomes
> 2), and then you add (+), resulting in 2 + 2, which of course is 4.
AFAIK nothing defines which assignment happens first so this could just
as easily result in a value of 2.
-mjc
Michael Carman
>> pointed out to me that precedence does not determine order of evaluation.
>
> Can you give me an example? I can't really see how the yacc parser can
> produce anything else...
Roughly speaking: Precedence defines the order in which operations are
performed. Order of evaluation defines the order in which the operands
are evaluated. Even if the parser always returns a particular order an
optimizing stage could decide to reorder things.
So in "f() + g() * h()" precedence says that the multiplication happens
before the addition but it does not dictate which order the functions
are called in. That's determined by the order of evaluation. If the
three functions are independent it doesn't matter, but if they have side
effects (like modifying shared global data) it could.
-mjc
Ben Morrow
Quoth Michael Carman <mjca...@mchsi.com>:
Yes, I understand the concept in general. I meant a specific example of
when *perl* reorders operations like that, since I don't believe it ever
does.
Ben
--
We do not stop playing because we grow old;
we grow old because we stop playing.
b...@morrow.me.uk
Michael Carman
> Yes, I understand the concept in general. I meant a specific example of
> when *perl* reorders operations like that, since I don't believe it ever
> does.
I was afraid of that. ;) I don't know enough about the internals to know
whether or not it does. I suppose the order could change between
versions of Perl, although that doesn't seem likely as it could break
existing code.
-mjc
David Combs
Not only for the less-experienced, but for *everyone* -- that
is, if you're doing a *lot* of them. Why?
Because having the one fixed-in-memory array with an index
running back and forth within it involves ZERO garbage-collection
overhead. Allocate the thing once, and it's done.
Now, if the thing has to grow from time to time, then the
push and pop ptrs (indices) (unbalanced) run into each other,
and you have to grow the array, maybe double (or some other function)
its size, do you don't do this growing (eg gc-causing) at every
"push".
In fact, write a simple fcn "verifySizeOk" (ary, desired-next-index
to use) and let it do whatever's needed as the need occurs.
Anyway, pushes are nice, but the gc's can eat you alive.
[of course, probably lists are internally allocated er grown
*already* by some such scheme!]
David
David Combs
So that means that you have to REMEMBER which funcs have (unexpected or unobvious)
side-effects. Meaning you gotta have a func-name-suffix "SE" or the like
to remind you.
Well, there is someone else who knows, or could easily know, who has
side effects, and can propogate that knowledge (well, infection) to
calling funcs, and warn us of such potentially dangerous (and *horribly*
difficult to track-down) uses within expressions.
Who might that be? THE COMPILER, OF COURSE!
(maybe including the runtime-loader of other modules?)
Wouldn't it be reasonable to have the compiler (-w) warn of this
stuff?
(Presumably, it already does!)
David
PS: even in cases where you can prove that there's no problem,
due to some if-sequence guaranteeing that certain problems
cannot occur -- eliminating such uses wouild be a huge help
to those who follow and have to *maintain* such code!
Just think to that date-2k problem, with the discovery of all
those 30-year-old COBOL still very much in critical use!
David
Jürgen Exner
>So that means that you have to REMEMBER which funcs have (unexpected or unobvious)
>side-effects.
Well, no. That is why software engineering principles recommend to avoid
side effects and require to document(!) those odd behaviours.
>Meaning you gotta have a func-name-suffix "SE" or the like
>to remind you.
Should be spelled out in big bold red letters in the documentation.
>Well, there is someone else who knows, or could easily know, who has
>side effects, and can propogate that knowledge (well, infection) to
>calling funcs, and warn us of such potentially dangerous (and *horribly*
>difficult to track-down) uses within expressions.
>
>Who might that be? THE COMPILER, OF COURSE!
Nope. The compiler can only guess that a side effect may occur. If it
actually does happen is unknown at compile time and therefore equivalent
to solving the halting problem.
>Wouldn't it be reasonable to have the compiler (-w) warn of this
>stuff?
>
>(Presumably, it already does!)
Mabye. But it is always problematic trying to enforce best practises by
technology. It rarely works because people are very inventive when it
comes to circumventing restrictions.
jue