Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw

nested maps

by jczeus (Monk)
on Apr 26, 2007 at 12:43 UTC ( #612182=perlmeditation: print w/replies, xml ) Need Help??

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;

This produces aa, ab, ba, bb.

Adding characters is easy:

my @a = qw( a b c );

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;

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; }

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; }

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
Re: nested maps
by Limbic~Region (Chancellor) on Apr 26, 2007 at 13:28 UTC
      Many thanks to you and bobf for these links.

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


Re: nested maps
by Fletch (Chancellor) 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.

      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.

Re: nested maps
by DrHyde (Prior) on Apr 27, 2007 at 08:48 UTC

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://612182]
Approved by marto
Front-paged by grinder
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (5)
As of 2017-10-23 09:52 GMT
Find Nodes?
    Voting Booth?
    My fridge is mostly full of:

    Results (279 votes). Check out past polls.