Является ли «карта» циклом? - PullRequest
39 голосов
/ 11 июня 2010

Отвечая на этот вопрос , я понял, что не уверен, можно ли считать Perl map циклом или нет?

С одной стороны, он крякает / ходиткак цикл (работает O (n), может быть легко переписан эквивалентным циклом, и в некотором роде соответствует общему определению = «последовательность инструкций, которая постоянно повторяется»).

Нас другой стороны, map обычно не указывается среди управляющих структур Perl, из которых циклы являются подмножеством.Например, http://en.wikipedia.org/wiki/Perl_control_structures#Loops

Итак, то, что я ищу, является формальной причиной, чтобы убедить одну сторону против другой.Пока что первое (это цикл) звучит для меня гораздо более убедительно, но меня беспокоит тот факт, что я никогда не видел "карту", упомянутую в списке циклов Perl.

Ответы [ 15 ]

30 голосов
/ 11 июня 2010

карта - это концепция более высокого уровня, чем циклы, заимствованные из функционального программирования.Он не говорит «вызывать эту функцию для каждого из этих элементов, один за другим, от начала до конца», он говорит «вызывать эту функцию для всех этих элементов».Он может быть реализован как цикл, но это не главное - он также может быть реализован асинхронно - он все равно будет отображаться.

Кроме того, это не совсем структура управления сама по себе - что если каждыйФункция perl, которая использовала цикл в своей реализации, была указана в разделе «циклы?»То, что что-то реализовано с использованием цикла, не означает, что его следует рассматривать как собственный тип цикла.

26 голосов
/ 11 июня 2010

Нет, с моей точки зрения, это не цикл.

Для петель (perl) характерно то, что они могут быть разбиты (last) или возобновлены (next, redo)).map не может:

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

Сообщение об ошибке предполагает, что perl сам не считает вычисленный блок блоком цикла .

19 голосов
/ 11 июня 2010

С академической точки зрения могут быть рассмотрены оба варианта в зависимости от того, как определена карта.Если он всегда повторяется по порядку, то цикл foreach может быть эмулирован с помощью map, что делает два эквивалента.Некоторые другие определения карты могут позволить выполнение списка по порядку для повышения производительности (разделение работы между потоками или даже отдельными компьютерами).То же самое можно сделать с помощью конструкции foreach.

Но что касается Perl 5, map всегда выполняется по порядку, что делает его эквивалентным циклу.Внутренняя структура выражения map $_*2, 1, 2, 3 приводит к следующим кодам операций порядка выполнения, которые показывают, что map встроен как while -подобная управляющая структура:

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 
12 голосов
/ 11 июня 2010

Функция map не является циклом в Perl.Это хорошо видно по отказу next, redo и last внутри map:

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

Чтобы достичь желаемого эффекта в map, вы должны вернуть пустой список:

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

Я думаю, что преобразование - лучшее название для таких конструкций, как map.Он превращает один список в другой.Функция, аналогичная map, равна List::Util::reduce, но вместо преобразования списка в другой список она преобразует список в скалярное значение.Используя преобразование слова, мы можем говорить об общих аспектах этих двух функций более высокого порядка.

Тем не менее, он работает, посещая каждого члена списка.Это означает, что он ведет себя очень похоже на цикл, и в зависимости от того, что вы определяете под «циклом», он может быть квалифицирован.Обратите внимание, мое определение означает, что в этом коде также нет цикла:

#!/usr/bin/perl

use strict;
use warnings;

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

Perl фактически определяет слово loop в своей документации:

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

По этому определению map является циклом, потому что он повторно преобразует свой блок;тем не менее, он также определяет «оператор управления циклом» и «метку цикла»:

   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.

Я считаю, что называть map цикл неточно, поскольку next и его род определены как операторы управления циклами и они не могут контролировать map.

Это все только игра слов.Описание map как петли - это совершенно верный способ познакомить кого-то с этим.Даже документация для map использует цикл foreach как часть своего примера:

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

           is just a funny way to write

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

Хотя все зависит от контекста.Полезно описывать умножение для кого-то как повторяющееся сложение, когда вы пытаетесь заставить его или ее понять концепцию, но вы не хотели бы, чтобы он или она продолжали думать об этом таким образом.Вы бы хотели, чтобы он или она выучил правила умножения, а не всегда переводил обратно на правила сложения.

11 голосов
/ 11 июня 2010

Ваш вопрос касается вопроса классификации.По крайней мере, в одной интерпретации, вопрос о том, является ли map циклом, похож на вопрос о том, является ли map подмножеством «цикла».Обрамленный таким образом, я думаю, что ответ - нет.Хотя map и Loop имеют много общего, между ними есть важные различия.

  • Элементы управления Loop : Час.Оуэнс убедительно доказывает , что циклы Perl подчиняются элементам управления цикла, таким как next и last, а map нет.
  • Возвращаемые значения : цельmap - это возвращаемое значение;с петлями, не так много.

Мы сталкиваемся с такими отношениями все время в реальном мире - вещи, которые имеют много общего друг с другом, но ни один из них не является идеальным подмножеством другого.

 -----------------------------------------
|Things that iterate?                     |
|                                         |
|      ------------------                 |
|     |map()             |                |
|     |                  |                |
|     |          --------|----------      |
|     |          |       |          |     |
|     |          |       |          |     |
|      ------------------           |     |
|                |                  |     |
|                |              Loop|     |
|                 ------------------      |
|                                         |
 -----------------------------------------
10 голосов
/ 11 июня 2010

карта - это функция высшего порядка .То же самое относится и к grep.Книга Perl высшего порядка объясняет идею в деталях.

Грустно видеть, что обсуждение перешло к деталям реализации, а не концепции.

4 голосов
/ 17 июня 2010

Ответы FM и Дейва Шерохмана довольно хороши, но позвольте мне добавить дополнительный способ просмотра карты.

map - это функция, которая гарантированно для просмотра каждый элемент структуры ровно один раз .И это не структура control , поскольку она сама является чистой функцией.Другими словами, инварианты , которые сохраняет карта, очень сильны, намного сильнее, чем «петля».Так что если вы можете использовать карту, это здорово, потому что вы получаете все эти инварианты «бесплатно», в то время как если вы используете (более общую!) Структуру управления, вам придется установить все эти инварианты самостоятельно, если выхочу быть уверенным, что ваш код верен.

И в этом и заключается прелесть многих из этих функций высшего порядка: вы получаете намного больше бесплатных инвариантов, так что вы, как программист, можете потратить свое драгоценное время на размышленияподдержание зависимых от приложения инвариантов вместо того, чтобы беспокоиться о низкоуровневых проблемах, связанных с реализацией.

3 голосов
/ 11 июня 2010

Вот определение карты как recurrence:

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

    return unless @_;

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

my @squares = _map { $_ ** 2 } 1..100;
3 голосов
/ 11 июня 2010

map сам обычно реализуется с использованием цикла некоторого вида (обычно для циклического перебора итераторов), но, поскольку это структура более высокого уровня, он часто не включается в списки нижнегоструктуры контроля уровня.

2 голосов
/ 20 июня 2010

Я думаю, карта соответствует определению Функтора .

...