Карта (функция высшего порядка) - Map (higher-order function)

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

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

Примеры: отображение списка

Предположим, у нас есть список целых чисел [1, 2, 3, 4, 5] и хотел бы вычислить квадрат каждого целого числа. Для этого мы сначала определяем функцию для квадрат одно число (показано здесь в Haskell ):

квадрат Икс = Икс * Икс

После мы можем позвонить

>>> карта квадрат [1, 2, 3, 4, 5]

что дает [1, 4, 9, 16, 25], демонстрируя, что карта просмотрел весь список и применил функцию квадрат к каждому элементу.

Наглядный пример

Ниже вы можете увидеть представление каждого шага процесса сопоставления для списка целых чисел. X = [0, 5, 8, 3, 2, 1] что мы хотим отобразить в новый список ИКС' согласно функции ${displaystyle f (x) = x + 1}$ :

применение шагов обработки функции карты

Просмотр этапов обработки при применении функции карты в списке

В карта предоставляется как часть базовой прелюдии Haskell (т.е. «стандартная библиотека») и реализована как:

карта :: (а -> б) -> [а] -> [б]карта _ []       = []карта ж (Икс : хз) = ж Икс : карта ж хз

Обобщение

В Haskell полиморфная функция map :: (a -> b) -> [a] -> [b] обобщается на разнотипная функция fmap :: Functor f => (a -> b) -> f a -> f b, что относится к любому типу, принадлежащему Функтор тип класс.

В конструктор типов списков [] можно определить как экземпляр Функтор type class с использованием карта функция из предыдущего примера:

пример Функтор [] где  fmap = карта

Другие примеры Функтор экземпляры включают деревья:

- простое двоичное дереводанные Дерево а = Лист а | Вилка (Дерево а) (Дерево а)пример Функтор Дерево где    fmap ж (Лист Икс) = Лист (ж Икс)  fmap ж (Вилка л р) = Вилка (fmap ж л) (fmap ж р)

Нанесение карты на дерево дает:

>>> fmap квадрат (Вилка (Вилка (Лист 1) (Лист 2)) (Вилка (Лист 3) (Лист 4)))Вилка (Вилка (Лист 1) (Лист 4)) (Вилка (Лист 9) (Лист 16))

Для каждого экземпляра Функтор тип класс, fmap является обязанный по контракту подчиняться законам функторов:

fmap я бы      ≡ я бы              - закон личностиfmap (ж . грамм) ≡ fmap ж . fmap грамм - закон состава

где . обозначает функциональная композиция в Haskell.

Помимо прочего, это позволяет определять поэлементные операции для различных типов коллекции.

Более того, если $F$ и $грамм$ два функтора, a естественная трансформация функция полиморфного типа ${displaystyle h: forall T.F (T) o G (T)}$ который уважает $fmap$ :

{displaystyle h_ {Y} circ имя оператора {fmap} (f) = имя оператора {fmap} (f) circ h_ {X}}

для любой функции

{displaystyle f: X o Y}

.

Если $час$ функция определяется параметрический полиморфизм как и в приведенном выше определении типа, эта спецификация всегда выполняется.

Оптимизация

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

(карта f. карта g) список и
map (f. g) список

приводят к такому же результату; это, ${displaystyle operatorname {map} (f) circ operatorname {map} (g) = operatorname {map} (fcirc g)}$ . Однако вторая форма более эффективна для вычислений, чем первая форма, потому что каждая карта требует перестройки всего списка с нуля. Следовательно, компиляторы попытаются преобразовать первую форму во вторую; этот тип оптимизации известен как слияние карт и это функциональный аналог петля слияния.^[1]

Функции карты могут быть и часто определяются в терминах складывать такие как складной, что означает, что можно слияние карт: foldr f z. карта g эквивалентно foldr (F. g) z.

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

reverseMap ж = складка (ys Икс -> ж Икс : ys) []

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

Сравнение языков

Функция карты возникла в функциональное программирование языков.

Язык Лисп представил функцию карты, называемую список карт^[2] в 1959 году, а в 1958 году уже появились несколько иные версии.^[3] Это исходное определение для список карт, сопоставляя функцию с последовательными списками отдыха:

maplist [x; f] = [null [x] -> NIL; T -> cons [f [x]; maplist [cdr [x]; f]]]

Функция список карт все еще доступен в новых Lisps, например Common Lisp,^[4] хотя функции как mapcar или более общий карта будет предпочтительнее.

Возведение элементов списка в квадрат с помощью список карт будет написано в S-выражение обозначения вроде этого:

(список карт (лямбда (л) (sqr (машина л))) '(1 2 3 4 5))

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

(mapcar (функция sqr) '(1 2 3 4 5))

Сегодня функции отображения поддерживаются (или могут быть определены) во многих процедурный, объектно-ориентированный, и мультипарадигма языки также: в C ++ с Стандартная библиотека шаблонов, это называется std :: transform, в C # (3.0) библиотека LINQ, она предоставляется как метод расширения, называемый Выбирать. Карта также является часто используемой операцией на языках высокого уровня, таких как Язык разметки ColdFusion (CFML), Perl, Python, и Рубин; операция называется карта на всех четырех языках. А собирать псевдоним для карта также предоставляется в Ruby (из Болтовня ). Common Lisp предоставляет семейство функций, подобных карте; тот, который соответствует описанному здесь поведению, называется mapcar (-машина указание доступа с помощью Работа в автомобиле ). Существуют также языки с синтаксическими конструкциями, обеспечивающими ту же функциональность, что и функция карты.

Map иногда обобщается, чтобы принимать двоичные (2-аргументные) функции, которые могут применять пользовательскую функцию к соответствующим элементам из двух списков. В некоторых языках для этого используются специальные имена, например map2 или zipWith. Языки, использующие явные вариативные функции могут иметь версии карты с переменной арность поддерживать переменная арность функции. Карта с 2 или более списками сталкивается с проблемой обработки, когда списки имеют разную длину. В этом разные языки различаются. Некоторые вызывают исключение. Некоторые останавливаются после длины самого короткого списка и игнорируют лишние элементы в других списках. Некоторые продолжают до длины самого длинного списка, а для списков, которые уже закончились, передают в функцию некоторое значение-заполнитель, указывающее на отсутствие значения.

На языках, поддерживающих первоклассные функции и карри, карта может быть частично применен к поднимать функция, которая работает только с одним значением, до поэлементного эквивалента, который работает со всем контейнером; Например, квадрат карты - это функция Haskell, которая возводит в квадрат каждый элемент списка.

Карта на разных языках
Язык	карта	Карта 2 списков	Сопоставить n списков	Примечания	Работа со списками разной длины
APL	`func список`	`list1 func list2`	`func/ list1 list2 list3 list4`	Возможности обработки массивов APL делают такие операции, как map, неявными	ошибка длины, если длина списка не равна или 1
Common Lisp	`(mapcar func список)`	`(mapcar func list1 list2)`	`(mapcar func list1 list2 ...)`		останавливается после длины самого короткого списка
C ++	`std :: transform (начинать, конец, результат, func)`	`std :: transform (begin1, конец1, begin2, результат, func)`		в заголовке <алгоритм> начинать, конец, и результат итераторы результат записывается начиная с результат
C #	`ienum.Выбирать(func)` или В `Выбрать` пункт	`ienum1.Zip (ienum2, func)`		`Выбирать` это метод расширения ienum это IEnumerable `Почтовый индекс` представлен в .NET 4.0 Аналогично на всех языках .NET	останавливается после окончания самого короткого списка
CFML	`obj.map (функция)`			Где `объект` это массив или структура. `func` получает в качестве аргументов значение каждого элемента, его индекс или ключ и ссылку на исходный объект.
Clojure	`(карта func список)`	`(карта func list1 list2)`	`(карта func list1 list2 ...)`		останавливается после окончания самого короткого списка
D	`список.карта!func`	`zip (list1, list2).карта!func`	`zip (list1, list2, ...).карта!func`		Указывается для архивирования с помощью StoppingPolicy: short ,est, or requireSameLength
Erlang	`списки: карта (Весело, Список)`	`списки: zipwith (Весело, Список1, Список2)`	`zipwith3` так же доступно		Списки должны быть одинаковой длины
Эликсир	`Enum.map (список, весело)`	`Enum.zip (list1, list2) \|> Enum.map (весело)`	`List.zip ([list1, list2, ...]) \|> Enum.map (весело)`		останавливается после окончания самого короткого списка
F #	`List.map func список`	`List.map2 func list1 list2`		Функции существуют для других типов (Seq и Массив)	Выбрасывает исключение
Groovy	`list.collect (функция)`	`[список1 список2].transpose ().collect (функция)`	`[список1 список2 ...].transpose ().collect (функция)`
Haskell	`карта func список`	`zipWith func list1 list2`	`zipWithп func list1 list2 ...`	`п` соответствует количеству списков; предопределено до `zipWith7`	останавливается после окончания самого короткого списка
Haxe	`множество.карта(func)` `список.карта(func) Лямбда.карта (повторяемый, func)`
J	`func список`	`list1 func list2`	`func/ list1, list2, list3 ,: list4`	Возможности обработки массивов J делают такие операции, как map, неявными	ошибка длины, если длины списков не равны
Ява 8+	`транслировать.карта(func)`
JavaScript 1.6 ECMAScript 5	`множество#карта(func)`	`Список1.map (функция (elem1, i) { вернуть func(elem1, Список2[я]); })`	`Список1.map (функция (elem1, i) { вернуть func(elem1, Список2[я], List3[i], ...); })`	Array # map передает 3 аргумента в func: элемент, индекс элемента и массив. Неиспользуемые аргументы можно не указывать.	Останавливается в конце Список1, расширяя более короткие массивы с помощью неопределенный предметы при необходимости.
Юля	`карта(func, список)`	`карта(func, список1, список2)`	`карта(func, список1, список2, ..., списокN)`		ОШИБКА: несоответствие размеров
Logtalk	`карта(Закрытие, Список)`	`карта(Закрытие, Список1, Список2)`	`карта(Закрытие, Список1, Список2, List3, ...) (до семи списков)`	Только Закрытие аргумент должен быть создан.	Отказ
Mathematica	`func /@ список Карта[func, список]`	`MapThread [func, {list1, list2}]`	`MapThread [func, {list1, list2, ...}]`		Списки должны быть одинаковой длины
Максима	`карта(ж, expr₁, ..., expr_п) список карт (ж, expr₁, ..., expr_п)`			map возвращает выражение, ведущий оператор которого совпадает с оператором выражений; maplist возвращает список
OCaml	`List.map func список Array.map func множество`	`List.map2 func list1 list2`			вызывает исключение Invalid_argument
PARI / GP	`подать заявление(func, список)`				Нет данных
Perl	`карта блокировать список карта expr, список`			В блокировать или expr специальная переменная $_ по очереди содержит каждое значение из списка.	Помощник `Список :: MoreUtils :: каждый_массив` объединяет более одного списка, пока не будет исчерпан самый длинный, заполняя остальные `undef.`
PHP	`array_map (вызываемый, множество)`	`array_map (вызываемый, array1,array2)`	`array_map (вызываемый, array1,array2, ...)`	Количество параметров для вызываемый должно соответствовать количеству массивов.	расширяет более короткие списки с НОЛЬ Предметы
Пролог	`список карт (Cont, Список1, Список2).`	`список карт (Cont, Список1, Список2, List3).`	`список карт (Cont, Список1, ...).`	Аргументы списка являются входными, выходными или обоими. Subsumes также zipWith, unzip, all	Тихий сбой (не ошибка)
Python	`карта(func, список)`	`карта(func, list1, list2)`	`карта(func, list1, list2, ...)`	Возвращает список в Python 2 и итератор в Python 3.	`zip ()` и `карта()` (3.x) останавливается после окончания самого короткого списка, тогда как `карта()` (2.x) и `itertools.zip_longest ()` (3.x) расширяет более короткие списки с помощью `Никто` Предметы
Рубин	`перечислить.собирать {блокировать} перечислить.карта {блокировать}`	`enum1.zip (enum2).карта {блокировать}`	`enum1.zip (enum2, ...).карта {блокировать} [enum1, enum2, ...].transpose.map {блокировать}`	`перечислить это перечисление`	останавливается в конце объекта, для которого он вызван (первый список); если какой-либо другой список короче, он дополняется ноль Предметы
Ржавчина	`list1.into_iter (). map (func)`	`list1.into_iter (). zip (list2).карта(func)`		то `Итератор :: карта` и `Итератор :: zip` оба метода становятся владельцем исходного итератора и возвращают новый; то `Итератор :: zip` метод внутренне вызывает `IntoIterator :: into_iter` метод на `list2`	останавливается после окончания более короткого списка
S -р	`лафский (список, func)`	`mapply (func, list1, list2)`	`mapply (func, list1, list2, ...)`		Более короткие списки прокручиваются
Scala	`список.карта(func)`	`(list1, list2).zipped.map (func)`	`(list1, list2, list3).zipped.map (func)`	примечание: более 3-х невозможно.	останавливается после окончания более короткого списка
Схема (включая Хитрость и Ракетка )	`(карта func список)`	`(карта func list1 list2)`	`(карта func list1 list2 ...)`		списки должны иметь одинаковую длину (SRFI-1 расширяется, чтобы принимать списки разной длины)
Болтовня	`Коллекция собирать: Блок`	`aCollection1 с: aCollection2 собирать: Блок`			Терпит неудачу
Стандартный ML	`карта func список`	`ListPair.map func (list1, list2) ListPair.mapEq func (list1, list2)`		Для карты с двумя аргументами func принимает свои аргументы в виде кортежа	`ListPair.map` останавливается после окончания самого короткого списка, тогда как `ListPair.mapEq` поднимает `Неравная длина` исключение
Быстрый	`последовательность.карта(func)`	`zip (последовательность1, последовательность2).карта(func)`			останавливается после окончания самого короткого списка
XPath 3 XQuery 3	`список ! блокировать` `для каждого (список, функция)`	`для каждой пары (список1, список2, функция)`		В `блокировать` элемент контекста `.` содержит текущее значение	останавливается после окончания самого короткого списка

Смотрите также

Свертка (информатика), также называемый Конв или застегивать
Фильтр (функция высшего порядка)
Сгиб (функция высшего порядка)
для каждого
Бесплатный моноид
Функциональное программирование
Функция высшего порядка
Понимание списка
Карта (параллельный узор)