views:

929

answers:

13
+23  Q: 

Is "map" a loop?

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.

+3  A: 

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.

Amber
+19  A: 

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.

Carson Myers
perl considers map a control structure. it is the LOGOP mapwhile, which is a control branching op
Eric Strom
@Carson - considering the result of `map { $i++ } @a`, I must say that the first quote applies more to Perl's "map" than the second quote (the one about "on all these items), no?
DVK
@Eric - now THAT's a strong argument... would love to see it as an actual answer!
DVK
@DVK, I suppose you could say that, but I was more referring to the difference in abstraction between loops and map. Map is a functional programming concept that says (do this to these things), while a loop is a lower level control structure that could be used to implement map.
Carson Myers
+1  A: 

"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.

John Feminella
A loop doesn't necessarily have to iterate over elements... Or do the same thing each time... Or be O(n) depending on what is in the loop
Carson Myers
@Carson Myers: Can you give an example of a non-degenerate-case loop that's not iterating over anything? I can't think of any counterexample. Also, the entire _point_ of a loop is to execute a set of instructions over and over again, so I'd also disagree with your second point.
John Feminella
well, I guess counter controlled loops don't really iterate over anything, and loops with branch statements won't necessarily always do the same thing. In any case, I didn't down mod you, I was just nit-picking
Carson Myers
@John: a loop to compute the sequence involved in the Collatz conjecture starting from the number n is not O(n). Your other conditions don't say much either... if a loop contains a branch, is it "doing the same thing every time"? Are you just asserting that it's deterministic? This isn't the "formal reasoning" the OP asked for.
p00ya
@pOOya: as far as i know, the branch is part of the loop, so the loop executes the same body of instruction every time however taking different path inside this body.
Adrien Plisson
@Adrien: that's meaningless then, as any deterministic procedure "does the same thing each time". As to John's "iterating over elements", a busy-wait is a well-understood paradigm that doesn't do anything of the sort.
p00ya
Your suggested criteria for what constitutes a "loop" strike me as rather biased towards `for` loops. What about `while` loops? They may iterate over something, but frequently do not. "Does the same thing every time" is ill-defined; depending on whether you consider branching to be the same thing, this is either false (some loops do different things on different iterations) or an empty statement (**all** software, looped or not, does the same thing every time it is run). And `while` loops may not even have a clearly defined `n`, much less be `O(n)`.
Dave Sherohman
@pÔOya: the difference is in the way you understand "do the same thing each time". the body of the loop considered as a whole is always the same, the individual instructions performed when executing the body are different. anyway, you are still right about iterating over elements and being O(n)
Adrien Plisson
+16  A: 

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.

pilcrow
+12  A: 

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 
Eric Strom
+8  A: 

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.

zakovyrya
+1 for HOP... I'll look into that explanation.
DVK
+3  A: 

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;
Pedro Silva
But recursion is just one way to implement a loop. Not all loops are iterative.
Chas. Owens
Well, 'loop' here should really be seen as a control structure. Recursion is a mathematical term. Properly defined, `map` is a mathematical abstraction, not a control structure. And in any case, this particular 'loop' is tail-call recursive, and hence iterative!
Pedro Silva
It isn't iterative in Perl 5 (you need a helper function and the sub version of `goto` to optimize tail recursion in Perl 5). You can implement all of the control structures as functions, does this make them not control structures anymore? Is `if(cond, f1, f2)` somehow less of an if statement than `if (cond) { f1 } else { f2 }`? If `map` responded to the loop control statements and allowed the setting of a loop label, I would say that is a loop.
Chas. Owens
+1  A: 

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...)

Dave Sherohman
+1 - I like that point of view (as well as being a realist :) )
DVK
+6  A: 

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.

Chas. Owens
@Chas - is there any (semi)-official statement necessitating next/redo/last to work in an "official" Perl loop? Or is that purely personal preference?
DVK
@DVK `next`, `redo`, and `last` are defined as loop control statements. This implies that anything that is a loop can be controlled by them. But the devil is in the definition here. See the extra information I am adding to the answer.
Chas. Owens
@Chas => but `next`, `redo`, and `last` also work on bare blocks and subroutines. neither of those is a loop.
Eric Strom
@Eric Storm, from the docs for `next` and friends: "Note that a block by itself is semantically identical to a loop that executes once." What makes you think they work with subroutines? If you use one of them to try to control a subroutine you get an error like `Can't "next" outside a loop block`.
Chas. Owens
+8  A: 

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|     |
|                 ------------------      |
|                                         |
 -----------------------------------------
FM
If I hear the word iterator, I'll be depressed for the entire day. I had enough of C++ yesterday, thankyouverymuch!
DVK
@DVK: you asked! map is indeed an iterator in most senses of the word, since it aliases list elements to `$_`.
Ether
******sigh******
DVK
+1  A: 

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.

frankc
What you're talking about is "reduce" concept. It was discussed in relation to map in a different asnwer to this Q.
DVK
+2  A: 

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.

Jacques Carette
+1  A: 

I think map fits the definition of a Functor.

Sinan Ünür