Here is something interesting I found through playing around with map, my favorite Perl toy. I've not the faintest if this could be useful in a more general way or if it's just, well, interesting crap...

Here's how it emerged:

Just as an exercise, I wanted to generate a list of strings with a specific length from every possible combination of a list of characters.

But not with for loops, but with nested maps! In its simplest form, with 2 chars and strings with a length of two:

my @a = qw( a b );
my @b = map { my $x = $_;
              map { $x . $_ } @a;
            } @a;

[download]

This produces aa, ab, ba, bb.

Adding characters is easy:

my @a = qw( a b c );

[download]

This produces aa, ab, ac, ba, bb, bc, ca, cb, cc.

But increasing the length of the string is not so easy. I did this by adding another nested map:

my @b = map { my $x = $_;
              map { my $y = $_;
                    map { $x . $y . $_ } @a;
                  } @a;
            } @a;

[download]

which, with qw( a b ), produces aaa, aab, aba, abb, baa, bab, bba, bbb. This is, of course, stupid.

One way to solve this problem is with a recursive function:

sub f
{ my ( $n, @a ) = @_;
  croak "illegal value for n: $n" if $n < 1;
  return @a if $n == 1;
  map { my $x = $_;
        map { $x . $_ ) } f( $n - 1, @a );
      } @a;
}

[download]

Now you could make it more general by adding a coderef parameter, string concatenation being only a special case needed in the original example:

sub f
{ my ( $n, $g, @a ) = @_;
  croak "illegal value for n: $n" if $n < 1;
  return @a if $n == 1;
  map { my $x = $_;
        map { $g->( $x, $_ ) } f( $n - 1, $g, @a );
      } @a;
}

[download]

So we have a function f that produces a list b by applying a function g to all possible combinations of a list a by calling itself recursively n times.

Is this useful? Or could it be further transformed so that it yields something useful?

Replies are listed 'Best First'.
Re: nested maps
by bobf (Monsignor) on Apr 26, 2007 at 13:20 UTC
[reply]
Re: nested maps
by Limbic~Region (Chancellor) on Apr 26, 2007 at 13:28 UTC
[reply]
      Many thanks to you and bobf for these links.

      Algorithm::Loops is exactly what I was looking for.

      Cheers

[reply]
[d/l]
Re: nested maps
by Fletch (Bishop) on Apr 26, 2007 at 13:13 UTC

    It's so useful someone wrote a book on this kind of thing (well, many someones, many books; but one specifically on doing it in Perl): Higher Order Perl (ISBN 1558607013) by dominus.

[reply]
      Thanks for mentioning this book.

      I bought it immediately when it was released, and took several months trying to study it. Finally, in the chapter about parsers, I got the feeling of being overwhelmed. I simply couldn't understand what was going on when and why anymore.

      So I thought: this book is surely great for studying how to do this kind of stuff in Perl, but maybe not so great for teaching you this stuff if in general if you have no background other than procedural programming.

      So I decided to put it on the shelf for now and try to learn CL and Scheme first and maybe Mozart and/or Haskell later on. Currently I'm working through "Practical Common Lisp" and "The Little Schemer" and hope to get more comfortable with this approach to programming.

[reply]
Re: nested maps
by DrHyde (Prior) on Apr 27, 2007 at 08:48 UTC
[reply]
[d/l]
      But if there's only one such construction in a Perl program, which approach incurs more overhead?
      • the single nasty temporary variable, or
      • loading a CPAN module that is used only once, to replace that variable with, to be frank, somewhat clunky syntax for accessing the outer $_ in the inner map
      And are there two different answers if you define "overhead" in terms of the burden on Perl versus the burden on the human brain reading the code? (To reduce brain overhead, at least the temporary variable can be given a meaningful name, whereas the NestedMap::stack[] syntax is inherently meaningless as well as kind of ugly.)
[reply]
[d/l]
[select]
        I'd define my own custom sub cross(&@@) sub cross(&\@\@) which does the "nasty" stuff in the inside after calling cross {$a.$b} @a,@a

        Cheers Rolf
        (addicted to the Perl Programming Language :)
        Wikisyntax for the Monastery

[reply]
[d/l]
[select]

Back to Meditations