2010-06-11 3 views
39

Отвечая на вопрос this question, я понял, что не был уверен, что Perl's map можно считать циклом или нет?Является ли «карта» петлей?

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

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

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

+0

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

+11

«Loop» не имеет точного универсального определения, поэтому это строго семантика: ответ заключается в том, что 'map' является циклом тогда и только тогда, когда кто-то, кого вы признаете авторитетным (например, Ларри Уолл, или консенсус Perl сообщество) говорит, что это так. –

+1

@j_random - Это то, что я имел в виду ... кто-то предоставлял некоторые «официальные» формулировки (например, скажем, из книги О'Рейли или perlfaq или perldoc), или ответ от кого-то, глубоко связанного с внутренними элементами Perl (IIRC Larry Wall не входит в /. но Рэндал Шварц и несколько перлов-носильщиков) – DVK

ответ

3

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

30

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

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

+5

perl рассматривает карту структуры управления. это LOGOP mapwhile, который является ветвлением управления op –

+0

с учетом результата 'map {$ i ++} @ a', я должен сказать, что первая цитата применима больше к« карте »Перла, чем вторая цитата (одна о" на всех этих предметах), нет? – DVK

+0

@ Эрик - теперь это сильный аргумент ... хотелось бы видеть его в качестве реального ответа! – DVK

2

«Loop» - это скорее термин CS, а не язык. Вы можете быть уверенны в призыве что-то цикл, если он обладает такими характеристиками:

  • перебирает элементы
  • делает то же самое каждый раз, когда
  • является O(n)

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

+0

Цикл не обязательно должен перебирать элементы ... Или делать то же самое каждый раз ... Или быть O (n) в зависимости от того, что находится в цикле –

+0

@Carson Myers: Можете ли вы привести пример цикла невырожденного случая, который не перебирает ничего ? Я не могу придумать никакого контрпримера , Кроме того, вся точка _point_ цикла состоит в том, чтобы выполнять набор команд снова и снова, поэтому я также не согласен с вашей второй точкой. –

+1

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

25

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

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

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

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

19

С учётной точки зрения, случай может быть выполнен как в зависимости от того, как определяется карта. Если он всегда выполняет итерацию по порядку, то цикл 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 
10

карты является higher-order function. То же самое относится к grep. Книга Higher-Order Perl подробно объясняет эту идею.

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

+1

+1 для HOP ... Я рассмотрю это объяснение. – DVK

3

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

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

    return unless @_; 

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

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

Но рекурсия - это всего лишь один из способов реализации цикла. Не все циклы являются итеративными. –

+0

Ну, «петля» здесь действительно должна рассматриваться как структура управления. Рекурсия - математический термин. Правильно определенная «карта» представляет собой математическую абстракцию, а не структуру управления. И в любом случае этот конкретный «цикл» является хвостовым рекурсивным и, следовательно, итеративным! –

+0

Это не итеративно в Perl 5 (вам нужна вспомогательная функция и вспомогательная версия 'goto' для оптимизации хвостовой рекурсии в Perl 5). Вы можете реализовать все структуры управления как функции, не делает ли они больше не управлять структурами? Является ли 'if (cond, f1, f2)' как-то меньше выражения if, чем 'if (cond) {f1} else {f2}'? Если 'map' ответил на операторы управления циклом и разрешил установку метки цикла, я бы сказал, что это цикл. –

1

Это все зависит от того, как вы смотрите на это ...

С одной стороны, в Perl map можно рассматривать как цикл, хотя бы потому, что он реализован в (текущих версиях) Perl.

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

+0

+1 - Мне нравится эта точка зрения (а также быть реалистом :)) – DVK

12

Функция 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 

I Думайте, трансформация - лучшее название для конструкций вроде 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 фактически делает define the word 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 и его родня определяются как loop control statements и они не могут контролировать 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($_)} = $_; 
       } 

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

+0

есть ли какое-либо (полу) -официальное заявление, требующее следующего/повторного/последнего для работы в «официальном» цикле Perl? Или это чисто личное предпочтение? – DVK

+2

@DVK 'next',' redo' и 'last' определяются как операторы управления контуром. Это означает, что все, что является циклом, может контролироваться ими. Но дьявол находится здесь в определении. См. Дополнительную информацию, которую я добавляю к ответу. –

+0

=> но 'next',' redo' и 'last' также работают с незакрытыми блоками и подпрограммами. ни один из них не является циклом. –

11

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

  • контура управления: Chas. Owens makes a strong case, что циклы Perl подлежат управления петлевых как next и last, в то время как map нет.
  • Возвращаемые значения: его стоимость равна map; с петлями, не так много.

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

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

Если я услышу слово итератор, я буду подавлен весь день. У меня было достаточно C++ вчера, спасибо очень много! – DVK

+5

@ DVK: вы спросили! карта действительно является итератором в большинстве чувств этого слова, поскольку она псевдонизирует элементы списка '$ _'. – Ether

+1

****** вздох ****** – DVK

1

Я думаю, что карта более сродна оператору, например, умножению. Вы даже можете думать о целочисленном умножении как о петле дополнений :). Конечно, это не цикл, даже если бы это было глупо реализовано именно так. Аналогично я вижу карту.

+0

То, о чем вы говорите, является концепцией «уменьшить». Это обсуждалось относительно карты в другом аспекте этого Q. – DVK

4

Ответы FM и Dave Sherohman довольно хорошие, но позвольте мне добавить дополнительный способ взглянуть на карту.

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

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

0

Карта в Perl - это функция более высокого порядка, которая применяет данную функцию ко всем элементам массива и возвращает измененный массив.

Независимо от того, выполняется ли это с использованием итеративного цикла или путем рекурсии или каким-либо другим способом, это не имеет значения и не указывается.

Таким образом, карта не является циклом, хотя она может быть реализована с использованием цикла.

0

Карта выглядит только как петля, если вы игнорируете значение lvalue. Вы не можете сделать это с циклом:

print join ' ', map { $_ * $_ } (1 .. 5) 
1 4 9 16 25 
Смежные вопросы