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

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 3

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 4

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 5

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 6

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;