Is "map" a loop?

Question

While answering this question, I came to realize that I was not sure whether Perl's map can be considered a loop or not?

On one hand, it quacks/walks like a loop (does O(n) work, can be easily re-written by an equivalent loop, and sort of fits the common definition = "a sequence of instructions that is continually repeated").

On the other hand, map is not usually listed among Perl's control structures, of which loops are a subset of. E.g. http://en.wikipedia.org/wiki/Perl_control_structures#Loops

So, what I'm looking for is a formal reason to be convinced of one side vs. the other. So far, the former (it is a loop) sounds a lot more convincing to me, but I'm bothered by the fact that I never saw "map" mentioned in a list of Perl loops.

Answer 1

map is a higher level concept than loops, borrowed from functional programming. It doesn't say "call this function on each of these items, one by one, from beginning to end," it says "call this function on all of these items." It might be implemented as a loop, but that's not the point -- it also might be implemented asynchronously -- it would still be map.

Additionally, it's not really a control structure in itself -- what if every perl function that used a loop in its implementation were listed under "loops?" Just because something is implemented using a loop, doesn't mean it should be considered its own type of loop.

Answer 2

No, it is not a loop, from my perspective.

Characteristic of (perl) loops is that they can be broken out of (last) or resumed (next, redo). map cannot:

map { last } qw(stack overflow);  # ERROR!  Can't "last" outside a loop block

The error message suggests that perl itself doesn't consider the evaluated block a loop block.

Answer 3

From an academic standpoint, a case can be made for both depending on how map is defined. If it always iterates in order, then a foreach loop could be emulated by map making the two equivalent. Some other definitions of map may allow out of order execution of the list for performance (dividing the work amongst threads or even separate computers). The same could be done with the foreach construct.

But as far as Perl 5 is concerned, map is always executed in order, making it equivalent to a loop. The internal structure of the expression map $_*2, 1, 2, 3 results in the following execution order opcodes which show that map is built internally as a while-like control structure:

OP  enter
COP nextstate
OP  pushmark
SVOP const IV 1
SVOP const IV 2
SVOP const IV 3
LISTOP mapstart
LOGOP (0x2f96150) mapwhile  <-- while still has items, shift one off into $_
    PADOP gvsv GV *_            
    SVOP const IV 2             loop body
    BINOP multiply              
    goto LOGOP (0x2f96150)  <-- jump back to the top of the loop
LISTOP leave 

Answer 4

The map function is not a loop in Perl. This can be clearly seen by the failure of next, redo, and last inside a map:

perl -le '@a = map { next if $_ %2; } 1 .. 5; print for @a'
Can't "next" outside a loop block at -e line 1.

To achieve the desired affect in a map, you must return an empty list:

perl -le '@a = map { $_ %2 ? () : $_ } 1 .. 5; print for @a'
2
4

I think transformation is better name for constructs like map. It transforms one list into another. A similar function to map is List::Util::reduce, but instead of transforming a list into another list, it transforms a list into a scalar value. By using the word transformation, we can talk about the common aspects of these two higher order functions.

That said, it works by visiting every member of the list. This means it behaves much like a loop, and depending on what your definition of "a loop" is it might qualify. Note, my definition means that there is no loop in this code either:

#!/usr/bin/perl

use strict;
use warnings;

my $i = 0;
FOO:
    print "hello world!\n";
goto FOO unless ++$i == 5;

Perl actually does define the word loop in its documentation:

   loop
       A construct that performs something repeatedly, like a roller
       coaster.

By this definition, map is a loop because it preforms its block repeatedly; however, it also defines "loop control statement" and "loop label":

   loop control statement
       Any statement within the body of a loop that can make a loop
       prematurely stop looping or skip an "iteration".  Generally you
       shouldn't try this on roller coasters.

   loop label
       A kind of key or name attached to a loop (or roller coaster) so
       that loop control statements can talk about which loop they want to
       control.

I believe it is imprecise to call map a loop because next and its kin are defined as loop control statements and they cannot control map.

This is all just playing with words though. Describing map as like-a-loop is a perfectly valid way of introducing someone to it. Even the documentation for map uses a foreach loop as part of its example:

               %hash = map { get_a_key_for($_) => $_ } @array;

           is just a funny way to write

               %hash = ();
               foreach (@array) {
                   $hash{get_a_key_for($_)} = $_;
               }

It all depends on the context though. It is useful to describe multiplication to someone as repeated addition when you are trying to get him or her to understand the concept, but you wouldn't want him or her to continue to think of it that way. You would want him or her to learn the rules of multiplication instead of always translating back to the rules of addition.

Answer 5

Your question turns on the issue of classification. At least under one interpretation, asking whether map is a loop is like asking whether map is a subset of "Loop". Framed in this way, I think the answer is no. Although map and Loop have many things in common, there are important differences.

• Loop controls: Chas. Owens makes a strong case that Perl loops are subject to loop controls like next and last, while map is not.
• Return values: the purpose of map is its return value; with loops, not so much.

We encounter relationships like this all the time in the real world -- things that have much in common with each other, but with neither being a perfect subset of the other.

 -----------------------------------------
|Things that iterate?                     |
|                                         |
|      ------------------                 |
|     |map()             |                |
|     |                  |                |
|     |          --------|----------      |
|     |          |       |          |     |
|     |          |       |          |     |
|      ------------------           |     |
|                |                  |     |
|                |              Loop|     |
|                 ------------------      |
|                                         |
 -----------------------------------------

Answer 6

map is a higher-order function. The same applies to grep. Book Higher-Order Perl explains the idea in full details.

It's sad to see that discussion moved towards implementation details, not the concept.

Answer 7

FM's and Dave Sherohman's answers are quite good, but let me add an additional way of looking at map.

map is a function which is guaranteed to look at every element of a structure exactly once. And it is not a control structure, as it (itself) is a pure function. In other words, the invariants that map preserves are very strong, much stronger than 'a loop'. So if you can use a map, that's great, because you then get all these invariants 'for free', while if you're using a (more general!) control structure, you'll have to establish all these invariants yourself if you want to be sure your code is right.

And that's really the beauty of a lot of these higher-order functions: you get many more invariants for free, so that you as a programmer can spend your valuable thinking time maintaining application-dependent invariants instead of worrying about low-level implementation-dependent issues.

Answer 8

map itself is generally implemented using a loop of some sort (to loop over iterators, typically), but since it is a higher-level structure, it's often not included in lists of lower-level control structures.

Answer 9

Here is a definition of map as a recurrence:

sub _map (&@) {
    my $f = shift;

    return unless @_;

    return $f->( local $_ = shift @_ ),
           _map( $f, @_ );
}

my @squares = _map { $_ ** 2 } 1..100;

Answer 10

"Loop" is more of a CS term rather than a language-specific one. You can be reasonably confident in calling something a loop if it exhibits these characteristics:

• iterates over elements
• does the same thing every time
• is O(n)

map fits these pretty closely, but it's not a loop because it's a higher-level abstraction. It's okay to say it has the properties of a loop, even if it itself isn't a loop in the strictest, lowest-level sense.

Answer 11

I think map fits the definition of a Functor.

Answer 12

It all depends on how you look at it...

On the one hand, Perl's map can be considered a loop, if only because that's how it's implemented in (current versions of) Perl.

On the other, though, I view it as a functional map and choose to use it accordingly which, among other things, includes only making the assumption that all elements of the list will be visited, but not making any assumptions about the order in which they will be visited. Aside from the degree of functional purity this brings and giving map a reason to exist and be used instead of for, this also leaves me in good shape if some future version of Perl provides a parallelizable implementation of map. (Not that I have any expectation of that ever happening...)

Answer 13

I think of map as more akin to an operator, like multiplication. You could even think of integer multiplication as a loop of additions :). It's not a loop of course, even if it were stupidly implemented that way. I see map similarly.

Answer 14

A map in Perl is a higher order function that applies a given function to all elements of an array and returns the modified array.

Whether this is implemented using an iterative loop or by recursion or any other way is not relevant and unspecified.

So a map is not a loop, though it may be implemented using a loop.

Answer 15

Map only looks like a loop if you ignore the lvalue. You can't do this with a for loop:

print join ' ', map { $_ * $_ } (1 .. 5)
1 4 9 16 25