Algorithm-Loops

 view release on metacpan or  search on metacpan

lib/Algorithm/Loops.pm  view on Meta::CPAN

    my @list= sort getList();
    do {
        usePermutation( @list );
    } while(  NextPermute( @list )  );

    my $len= @ARGV ? $ARGV[0] : 3;
    my @list= NestedLoops(
        [  ( [ 1..$len ] ) x $len  ],
        sub { "@_" },
    );

If you want working sample code to try, see below in the section specific
to the function(s) you want to try.  The above samples only give a
I<feel> for how the functions are typically used.

=head1 FUNCTIONS

Algorithm::Loops provides the functions listed below.  By default, no
functions are exported into your namespace (package / symbol table) in
order to encourage you to list any functions that you use in the C<use
Algorithm::Loops> statement so that whoever ends up maintaining your code
can figure out which module you got these functions from.

=over 4

=item Filter

Similar to C<map> but designed for use with s/// and other reflexive
operations.  Returns a modified copy of a list.

=item MapCar, MapCarU, MapCarE, and MapCarMin

All similar to C<map> but loop over multiple lists at the same time.

=item NextPermute and NextPermuteNum

Efficiently find all (unique) permutations of a list, even if it contains
duplicate values.

=item NestedLoops

Simulate C<foreach> loops nested arbitrarily deep.

=back

=head2 Filter(\&@)

=head3 Overview

Produces a modified copy of a list of values.  Ideal for use with s///.
If you find yourself trying to use s/// or tr/// inside of map (or grep),
then you should probably use Filter instead.

For example:

    use Algorithm::Loops qw( Filter );

    @copy = Filter { s/\\(.)/$1/g } @list;
    $text = Filter { s/^\s+// } @lines;

The same process can be accomplished using a careful and more complex
invocation of map, grep, or foreach.  However, many incorrect ways to
attempt this seem rather seductively appropriate so this function helps
to discourage such (rather common) mistakes.

=head3 Usage

Filter has a prototype specification of (\&@).

This means that it demands that the first argument that you pass to it be
a CODE reference.  After that you can pass a list of as many or as few
values as you like.

For each value in the passed-in list, a copy of the value is placed into
$_ and then your CODE reference is called.  Your subroutine is expected
to modify $_ and this modified value is then placed into the list of
values to be returned by Filter.

If used in a scalar context, Filter returns a single string that is the
result of:

    $string= join "", @results;

Note that no arguments are passed to your subroutine (so don't bother
with @_) and any value C<return>ed by your subroutine is ignored.

Filter's prototype also means that you can use the "map BLOCK"-like
syntax by leaving off the C<sub> keyword if you also leave off the
comma after the block that defines your anonymous subroutine:

        my @copy= Filter sub {s/\s/_/g}, @list;
  # becomes:            v^^^       v   ^
        my @copy= Filter {s/\s/_/g} @list;

Most of our examples will use this shorter syntax.

Note also that by importing Filter via the C<use> statement:

    use Algorithm::Loops qw( Filter );

it gets declared before the rest of our code is compiled so we don't have
to use parentheses when calling it.  We I<can> if we want to, however:

        my @copy= Filter( sub {s/\s/_/g}, @list );

=head3 Note on "Function BLOCK LIST" bugs

Note that in at least some versions of Perl, support for the "Filter
BLOCK ..." syntax is somewhat fragile.  For example:

    ... Filter( {y/aeiou/UAEIO/} @list );

may give you this error:

    Array found where operator expected

which can be fixed by dropping the parentheses:

    ... Filter {y/aeiou/UAEIO/} @list;

So if you need or want to use parentheses when calling Filter, it is best

lib/Algorithm/Loops.pm  view on Meta::CPAN

        my @lines= <STDIN>;
        chomp( @lines );
  # or
        chomp( my @lines= <STDIN> );

And what you might expect to work (but doesn't):

        my @lines= chomp( <STDIN> );  # Wrong

And what you can now use instead:

        my @lines= Filter {chomp} <STDIN>;

Here are some examples of ways to use map/grep correctly to get Filter's
functionality:

        Filter { CODE } @list
  # vs
        join "", map { local($_)= $_; CODE; $_ } @list
  # vs
        join "", grep { CODE; 1 } @{ [@list] }

Not horribly complex, but enough that it is very easy to forget part of
the solution, making for easy mistakes.  I see mistakes related to this
quite frequently and have made such mistakes myself several times.

Some (including me) would even consider the last form above to be an
abuse (or misuse) of C<grep>.

You can also use C<for>/C<foreach> to get the same results as Filter:

        my @copy= Filter { CODE } @list;
  # vs
        STATEMENT  foreach  my @copy= @list;
  # or
        my @copy= @list;
        foreach(  @copy  ) {
            CODE;
        }

=head2 MapCar*

=over 4

=item MapCar(\&@)

=item MapCarU(\&@)

=item MapCarE(\&@)

=item MapCarMin(\&@)

=back

=head3 Usage

The MapCar* functions are all like C<map> except they each loop over more
than one list at the same time.

[ The name "mapcar" comes from LISP. As I understand it, 'car' comes from
the acronym for a register of the processor where LISP was first
developed, one of two registers used to implement lists in LISP.  I only
mention this so you won't waste too much time trying to figure out what
"mapcar" is supposed to mean. ]

The MapCar* functions all have prototype specifications of (\&@).

This means that they demand that the first argument that you pass be a
CODE reference.  After that you should pass zero or more array references.

Your subroutine is called (in a list context) and is passed the first
element of each of the arrays whose references you passed in (in the
corresponding order).  Any value(s) returned by your subroutine are
pushed onto an array that will eventually be returned by MapCar*.

Next your subroutine is called and is passed the B<second> element of
each of the arrays and any value(s) returned are pushed onto the results
array.  Then the process is repeated with the B<third> elements.

This continues until your subroutine has been passed all elements [except
for some cases with MapCarMin()].  If the longest array whose reference
you passed to MapCar() or MapCarU() contained $N elements, then your
subroutine would get called $N times.

Finally, the MapCar* function returns the accumulated list of values.  If
called in a scalar context, the MapCar* function returns a reference to
an array containing these values.

[ I feel that having C<map> return a count when called in a scalar
context is quite simply a mistake that was made when this feature was
copied from C<grep> without properly considering the consequences.
Although it does make for the impressive and very impractical golf
solution of:

    $sum=map{(1)x$_}@ints;

for adding up a list of natural numbers. q-: ]

=head3 Differences

The different MapCar* functions are only different in how they deal with
being pqssed arrays that are not all of the same size.

If not all of your arrays are the same length, then MapCarU() will pass
in C<undef> for any values corresponding to arrays that didn't have
enough values.  The "U" in "MapCarU" stands for "undef".

In contrast, MapCar() will simply leave out values for short arrays (just
like I left the "U" out of its name).

MapCarE() will croak without ever calling your subroutine unless all of
the arrays are the same length.  It considers it an Error if your arrays
are not of Equal length and so throws an Exception.

Finally, MapCarMin() only calls your subroutine as many times as there
are elements in the B<shortest> array.

In other words,

    MapCarU \&MySub, [1,undef,3], [4,5], [6,7,8]

returns

    ( MySub( 1, 4, 6 ),
      MySub( undef, 5, 7 ),
      MySub( 3, undef, 8 ),
    )

While

    MapCar \&MySub, [1,undef,3], [4,5], [6,7,8]

returns

    ( MySub( 1, 4, 6 ),
      MySub( undef, 5, 7 ),
      MySub( 3, 8 ),
    )

lib/Algorithm/Loops.pm  view on Meta::CPAN

Note that this particular use of a function prototype is one that I am
not completely comfortable with.  I am tempted to remove the prototype
and force you to create the reference yourself before/when calling these
functions:

    } while(  NextPermute( \@list )  );   # Wrong

because

=over 4

=item

It makes it obvious to the reader of the code that a reference to the
array is what is being used by the routine.  This makes the reader more
likely to realize/suspect that the array is being modified in-place.

=item

Many/most uses of Perl function prototypes are more trouble than they are
worth.  This makes using even the less problematic cases often not a good
idea.

=back

However, I have decided to use a prototype here because:

=item

Several other functions from this module already use prototypes to good
advantage, enough advantage that I'd hate to lose it.

=item

Removing the prototype would require the addition of argument-checking
code that would get run each time a permutation is computed, somewhat
slowing down what is currently quite fast.

=item

The compile-time checking provided by the prototype can save develop time
over a run-time check by pointing out mistakes sooner.

=back

=head3 Features

There are several features to NextPermute* that can be advantages over
other methods of finding permutations.

=over 4

=item Iterators - No huge memory requirements

Some permutation generators return the full set of all permutations (as a
huge list of lists).  Your input list doesn't have to be very big at all
for the resulting set to be too large to fit in your available memory.

So the NextPermute* routines return each permutation, one at a time, so
you can process them all (eventually) without the need for lots of memory.

A programming object that gives you access to things one-at-a-time is
called an "iterator".

=item No context - Hardly any memory required

The NextPermute* routines require no extra memory in the way of context
or lists to keep track of while constructing the permutations.

Each call to a NextPermute* routine shuffles the items in the list
B<in-place>, never making copies of more than a couple of values at a
time (when it swaps them).

[ This also means you don't have to bother with creating an object to do
the iterating. ]

=item Handles duplicate values

Unlike most permutation generators you are likely to find in Perl, both
NextPermute* routines correctly deal with lists containing duplicate
values.

The following example:

    my @list= ( 3, 3, 3, 3 );
    do {
        print "@list\n";
    } while(  NextPermute( @list )  );

will only print the one line, "3 3 3 3\n", because NextPermute() quickly
determines that there are no other unique permutations.

Try out the demonstration program included in the "ex" subdirectory of
the source distribution of this module:

    > perl ex/Permute.plx tool
    1: loot
    2: loto
    3: ltoo
    4: olot
    5: olto
    6: oolt
    7: ootl
    8: otlo
    9: otol
    10: tloo
    11: tolo
    12: tool

Most permutation generators would have listed each of those twice
(thinking that swapping an "o" with another "o" made a new permutation). 
Or consider:

    > perl ex/Permute.plx noon
    1: nnoo
    2: nono
    3: noon
    4: onno
    5: onon
    6: oonn