nested maps

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?

Comment on nested maps Select or Download Code

Replies are listed 'Best First'.
Re: nested maps by bobf (Monsignor) on Apr 26, 2007 at 13:20 UTC
A similar question was asked in Trying to construct all possible strings from 4 bases [ATCG]. In addition to loops and recursion, the responses to that post include solutions that use the following: glob String::Combination Set::CrossProduct Algorithm::Loops Math::BaseCalc	[reply]
Re: nested maps by Limbic~Region (Chancellor) on Apr 26, 2007 at 13:28 UTC
jczeus, In addition to the great links previously provided, see also: NestedLoops and the Odometer Model Arbitrarily Nested Loops Cheers - L~R	[reply]
Re^2: nested maps by jczeus (Monk) on Apr 26, 2007 at 15:12 UTC
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]
Re^2: nested maps by jczeus (Monk) on Apr 26, 2007 at 14:49 UTC
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
`map { my $x = $_; map { $x . $_ } @a; } @a;` [download] Nasty temporary variableses! NestedMap	[reply] [d/l]
Re^2: nested maps by raygun (Scribe) on Sep 20, 2020 at 00:25 UTC
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]
Re^3: nested maps by LanX (Saint) on Sep 20, 2020 at 18:14 UTC
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]
Re^4: nested maps by LanX (Saint) on Sep 21, 2020 at 11:37 UTC
Re^5: nested maps by tobyink (Canon) on Sep 21, 2020 at 13:18 UTC
Some notes below your chosen depth have not been shown here


Perl-Sensitive Sunglasses
	PerlMonks