Est-ce que “map” est une boucle?

En répondant à cette question , j’ai réalisé que je n’étais pas sûr que la map de Perl puisse être considérée comme une boucle ou non?

D’un côté, il charrie comme une boucle (est-ce que O (n) fonctionne, peut être facilement réécrit par une boucle équivalente et correspond en quelque sorte à la définition commune = “une séquence d’instructions répétées continuellement”).

D’autre part, la map n’est généralement pas répertoriée parmi les structures de contrôle de Perl, dont les boucles sont un sous-ensemble de. Par exemple, http://en.wikipedia.org/wiki/Perl_control_structures#Loops

Donc, ce que je recherche est une raison formelle d’être convaincu d’un côté ou de l’autre. Jusqu’à présent, le premier (c’est une boucle) me semble beaucoup plus convaincant, mais je suis dérangé par le fait que je n’ai jamais vu “map” dans une liste de boucles Perl.

map est un concept de plus haut niveau que les boucles, emprunté à la functional programming. Il ne dit pas “appeler cette fonction sur chacun de ces éléments, un par un, du début à la fin”, il est dit “appeler cette fonction sur tous ces éléments”. Il pourrait être implémenté comme une boucle, mais ce n’est pas le cas – il pourrait également être implémenté de manière asynchrone – ce serait toujours la carte.

De plus, ce n’est pas vraiment une structure de contrôle en elle-même – et si toutes les fonctions perl qui utilisaient une boucle dans son implémentation étaient listées sous “boucles”? Ce n’est pas parce que quelque chose est implémenté en utilisant une boucle que cela doit être considéré comme son propre type de boucle.

Non, ce n’est pas une boucle, de mon sharepoint vue.

La caractéristique des boucles (perl) est qu’elles peuvent être extraites de ( last ) ou resockets ( next , redo ). map ne peut pas:

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

Le message d’erreur suggère que Perl lui-même ne considère pas le bloc évalué comme un bloc de boucle .

D’un sharepoint vue académique, un cas peut être fait pour les deux en fonction de la définition de la carte. Si elle itère toujours dans l’ordre, une boucle foreach peut être émulée par une map faisant les deux équivalents. Certaines autres définitions de map peuvent autoriser l’exécution de la liste en cas de panne (en divisant le travail entre les threads ou même des ordinateurs distincts). La même chose pourrait être faite avec la construction de foreach .

Mais en ce qui concerne Perl 5, la map est toujours exécutée dans l’ordre, ce qui la rend équivalente à une boucle. La structure interne de l’expression map $_*2, 1, 2, 3 traduit par les opcodes d’ordre d’exécution suivants qui montrent que la map est générée en interne en tant while structure de contrôle tout-en-un:

 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 

La fonction map n’est pas une boucle en Perl. Cela peut être clairement vu par l’échec de next , redo et last intérieur d’une map :

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

Pour obtenir l’effet désiré dans une map , vous devez retourner une liste vide:

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

Je pense que la transformation est un meilleur nom pour les constructions comme la map . Il transforme une liste en une autre. Une fonction similaire à la map est List::Util::reduce , mais au lieu de transformer une liste en une autre liste, elle transforme une liste en une valeur scalaire. En utilisant le mot transformation, nous pouvons parler des aspects communs de ces deux fonctions d’ordre supérieur.

Cela dit, cela fonctionne en visitant chaque membre de la liste. Cela signifie qu’il se comporte comme une boucle, et en fonction de votre définition de “boucle”, cela pourrait être considéré. Notez que ma définition signifie qu’il n’y a pas de boucle dans ce code:

 #!/usr/bin/perl use ssortingct; use warnings; my $i = 0; FOO: print "hello world!\n"; goto FOO unless ++$i == 5; 

Perl définit effectivement la boucle de mots dans sa documentation:

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

Par cette définition, la map est une boucle car elle préforme son bloc à plusieurs resockets; Cependant, il définit également “instruction de contrôle de boucle” et “libellé de boucle”:

  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. 

Je pense qu’il est imprécis d’appeler map a loop car next et ses proches sont définis comme des instructions de contrôle de boucle et ils ne peuvent pas contrôler la map .

C’est tout simplement jouer avec les mots si. Décrire la map comme une boucle est une manière parfaitement valable de lui présenter quelqu’un. Même la documentation de map utilise une boucle foreach dans le cadre de son exemple:

  %hash = map { get_a_key_for($_) => $_ } @array; is just a funny way to write %hash = (); foreach (@array) { $hash{get_a_key_for($_)} = $_; } 

Tout dépend du contexte cependant. Il est utile de décrire la multiplication à quelqu’un en tant qu’addition répétée lorsque vous essayez de le faire comprendre le concept, mais vous ne voudriez pas qu’il continue à penser de cette façon. Vous voudriez qu’il apprenne les règles de la multiplication au lieu de toujours traduire les règles d’addition.

Votre question porte sur la question de la classification. Au moins sous une seule interprétation, demander si la map est une boucle revient à demander si la map est un sous-ensemble de “Loop”. Encadré de cette manière, je pense que la réponse est non. Bien que la map et la boucle aient beaucoup de points communs, il y a des différences importantes.

  • Commandes de boucle : Chas. Owens fait valoir que les boucles Perl sont soumises à des contrôles de boucle comme next et last , alors que map ne l’est pas.
  • Valeurs de retour : l’object de la map est sa valeur de retour; avec des boucles, pas tellement.

Nous rencontrons des relations comme celle-ci tout le temps dans le monde réel – des choses qui ont beaucoup en commun, mais dont aucune n’est un sous-ensemble parfait de l’autre.

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

la carte est une fonction d’ordre supérieur . La même chose s’applique à grep. Book Higher-Order Perl explique l’idée en détail.

C’est sortingste de voir que la discussion a évolué vers les détails de la mise en œuvre, pas le concept.

Les réponses de FM et Dave Sherohman sont plutôt bonnes, mais permettez-moi d’append une autre façon de regarder la carte.

map est une fonction qui permet de regarder chaque élément d’une structure exactement une fois . Et ce n’est pas une structure de contrôle , car elle est une fonction pure. En d’autres termes, les invariants conservés sur la carte sont très forts, beaucoup plus forts qu’une «boucle». Donc, si vous pouvez utiliser une carte, c’est bien, car vous obtenez alors tous ces invariants «gratuitement», alors que si vous utilisez une structure de contrôle (plus générale!), Vous devrez établir tous ces invariants si vous voulez être sûr que votre code est correct.

Et c’est vraiment la beauté de beaucoup de ces fonctions d’ordre supérieur: vous obtenez beaucoup plus d’invariants gratuitement, de sorte que vous, en tant que programmeur, pouvez consacrer votre temps de reflection précieux aux invariants dépendants des applications au lieu problèmes.

map elle-même est généralement implémentée en utilisant une boucle quelconque (pour boucler les iterators, en général), mais comme il s’agit d’une structure de niveau supérieur, elle n’est souvent pas incluse dans les listes des structures de contrôle de niveau inférieur.

Voici une définition de la carte comme une recurrence :

 sub _map (&@) { my $f = shift; return unless @_; return $f->( local $_ = shift @_ ), _map( $f, @_ ); } my @squares = _map { $_ ** 2 } 1..100; 

“Loop” est plus un terme CS que spécifique à une langue. Vous pouvez être raisonnablement confiant en appelant quelque chose une boucle si elle présente ces caractéristiques:

  • itère sur des éléments
  • fait la même chose à chaque fois
  • est O(n)

map correspond bien à cela, mais ce n’est pas une boucle car c’est une abstraction de haut niveau. Il est acceptable de dire qu’il a les propriétés d’une boucle, même si elle ne constitue pas une boucle dans le sens le plus ssortingct et le plus ssortingct.

Je pense que la carte correspond à la définition d’un foncteur .

Tout dépend de la façon dont vous le regardez …

D’une part, la map de Perl peut être considérée comme une boucle, ne serait-ce que parce qu’elle est implémentée dans (les versions actuelles de) Perl.

D’autre part, je le vois comme une map fonctionnelle et choisit de l’utiliser en conséquence, ce qui inclut, entre autres choses, de supposer que tous les éléments de la liste seront visités, sans faire d’hypothèses sur l’ordre dans lequel ils seront visités. Mis à part le degré de pureté fonctionnelle que cela apporte et donnant à la map une raison d’exister et d’être utilisée au lieu de, cela me laisse également en forme si une future version de Perl fournit une implémentation parallélisable de map . (Non pas que je m’attends à ce que cela se produise …)

Je pense que la carte ressemble davantage à un opérateur, comme la multiplication. Vous pourriez même penser à la multiplication d’entiers comme une boucle d’ajouts :). Ce n’est pas une boucle bien sûr, même si elle a été bêtement mise en œuvre de cette manière. Je vois la carte de la même manière.

Une carte dans Perl est une fonction d’ordre supérieur qui applique une fonction donnée à tous les éléments d’un tableau et renvoie le tableau modifié.

Que cela soit implémenté en utilisant une boucle itérative ou par récursivité ou de toute autre manière n’est pas pertinent et non spécifié.

Donc, une carte n’est pas une boucle, bien qu’elle puisse être implémentée en utilisant une boucle.

La carte ne ressemble à une boucle que si vous ignorez la valeur. Vous ne pouvez pas faire cela avec une boucle for:

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