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

Информацию об абстрактном типе данных с тем же именем см. в разделе Карта (структура данных) .

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

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

Примеры: сопоставление списка

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

квадрат   х   =   х   *   х 

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

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

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

Визуальный пример

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

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

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

карта   ::   (  a   ->   b  )   ->   [  a  ]   ​​->   [  b  ] 
 карта   _   []         =   [] 
 карта   f   (  x   :   xs  )   =   f   x   :   карта   f   xs 

Обобщение

См. Также: Теория функторов и категорий.

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

Конструктор типов списков [] может быть определен как экземпляр Functor введите класс, используя map функция из предыдущего примера:

экземпляр   Functor   []   где 
   fmap   =   карта 

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

-- простое двоичное дерево 
 данных   Tree   a   =   Leaf   a   |   Fork   (  Tree   a  )   (  Tree   a  ) 

  Экземпляр   Functor   Tree   где   
   fmap   f   (  Leaf   x  )   =   Leaf   (  f   x  ) 
   fmap   f   (  Fork   l   r  )   =   Fork   (  fmap   f   l  )   (  fmap   f   r  ) 

Отображение дерева дает:

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

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

fmap   id        ≡   id                закон 
 fmap   (  f.g   )   идентичности  —   ≡   fmap   f   .    fmap   g   -- закон композиции 

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

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

Теоретико-категорный фундамент

В категорий функтор теории $F:C\rightarrow D$ состоит из двух карт: одна, которая отправляет каждый объект $A$ категории на другой объект $FA$и тот, который отправляет каждый морфизм $f:A\rightarrow B$ к другому морфизму $Ff:FA\rightarrow FB$, который действует как гомоморфизм категорий (т.е. соблюдает аксиомы категорий). Интерпретация вселенной типов данных как категории $Type$, где морфизмы являются функциями, то конструктор типа F это член Functor класс типа является объектной частью такого функтора, и fmap :: (a -> b) -> F a -> F bявляется частью морфизма. Описанные выше законы функтора являются в точности теоретико-категорными аксиомами функтора для этого функтора.

Функторы также могут быть объектами категорий с «морфизмами», называемыми естественными преобразованиями . Учитывая два функтора $F,G:C\rightarrow D$, естественная трансформация $\eta :F\rightarrow G$ состоит из набора морфизмов $\eta _{A}:FA\rightarrow GA$, по одному на каждый объект $A$ категории $D$, которые являются «естественными» в том смысле, что они действуют как «преобразование» между двумя функторами, не принимая во внимание объекты, к которым эти функторы применяются. Естественным преобразованиям соответствуют функции вида eta :: F a -> G a, где a — это переменная универсального кванторного типа — eta ничего не знает о типе, который обитает a. Аксиома естественности таких функций автоматически выполняется, поскольку это так называемая свободная теорема, зависящая от того, что она параметрически полиморфна . Например, reverse :: List a -> List a, который переворачивает список, является естественным преобразованием, как и flattenInorder :: Tree a -> List a, который выравнивает дерево слева направо и даже sortBy :: (a -> a -> Bool) -> List a -> List a, который сортирует список на основе предоставленной функции сравнения.

Оптимизации

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

• (map f . map g) list и
• map (f . g) list

привести к тому же результату; то есть, $\operatorname {map} (f)\circ \operatorname {map} (g)=\operatorname {map} (f\circ g)$. Однако вторая форма более эффективна для вычисления, чем первая, поскольку каждая mapтребует восстановления всего списка с нуля. Поэтому компиляторы попытаются преобразовать первую форму во вторую; этот тип оптимизации известен как объединение карт и является функциональным аналогом объединения циклов .

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

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

обратная карта   f   =   foldl   (  \  ys   x   ->   f   x   :   ys  )   [] 

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

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

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

В языке Lisp появилась функция отображения, называемая maplist в 1959 году, а несколько иные версии появились уже в 1958 году. Это оригинальное определение понятия maplist, отображая функцию на последовательные списки отдыха:

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

Функция maplist по-прежнему доступен в более новых Lisp, таких как Common Lisp , хотя функции вроде mapcar или более общий map было бы предпочтительнее.

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

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

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

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

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

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

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

Карта на разных языках

Язык	карта	Список карт 2	Карта n списков	Примечания	Обработка списков разной длины
АПЛ	func list	list1 func list2	func/ list1 list2 list3 list4	Возможности обработки массивов APL делают такие операции, как отображение, неявными.	ошибка длины, если длина списка не равна или равна 1
Общий Лисп	(mapcar func list)	(mapcar func list1 list2)	(mapcar func list1 list2 ...)		останавливается после длины кратчайшего списка
С++	std::transform(begin, end, result, func)	std::transform(begin1, end1, begin2, result, func)		в заголовке <алгоритм> начало , конец и результат являются итераторами результат записывается начиная с результата
С#	ienum.Select(func) или The select пункт	ienum1.Zip(ienum2, func)		Select это метод расширения ienum — это IEnumerable Zip представлен в .NET 4.0 Аналогично во всех языках .NET.	останавливается после того, как заканчивается кратчайший список
CFML	obj.map(func)			Где obj представляет собой массив или структуру. func получает в качестве аргументов значение каждого элемента, его индекс или ключ и ссылку на исходный объект.
Кложур	(map func list)	(map func list1 list2)	(map func list1 list2 ...)		останавливается после того, как заканчивается кратчайший список
Д	list.map!func	zip(list1, list2).map!func	zip(list1, list2, ...).map!func		Указано для сжатия с помощью StoppingPolicy: самое короткое, самое длинное или requireSameLength.
Эрланг	lists:map(Fun, List)	lists:zipwith(Fun, List1, List2)	zipwith3 так же доступно		Списки должны быть одинаковой длины
Эликсир	Enum.map(list, fun)	Enum.zip(list1, list2) |> Enum.map(fun)	List.zip([list1, list2, ...]) |> Enum.map(fun)		останавливается после того, как заканчивается кратчайший список
Ф#	List.map func list	List.map2 func list1 list2		Существуют функции для других типов ( Seq и Array ).	Выдает исключение
классный	list.collect(func)	[list1 list2].transpose().collect(func)	[list1 list2 ...].transpose().collect(func)
Хаскелл	map func list	zipWith func list1 list2	zipWithn func list1 list2 ...	nсоответствует количеству списков; предопределено до zipWith7	останавливается после того, как заканчивается кратчайший список
Смешанный	array.map(func) list.map(func) Lambda.map(iterable, func)
Дж	func list	list1 func list2	func/ list1, list2, list3 ,: list4	Возможности J по обработке массивов делают такие операции, как отображение, неявными.	ошибка длины, если длины списка не равны
Ява 8+	stream.map(func)
JavaScript 1.6 ECMAScript 5	array#map(func)	List1.map(function (elem1, i) { return func(elem1, List2[i]); })	List1.map(function (elem1, i) { return func(elem1, List2[i], List3[i], ...); })	Array#map передает в функцию func 3 аргумента : элемент, индекс элемента и массив. Неиспользуемые аргументы могут быть опущены.	Останавливается в конце List1 расширяя более короткие массивы неопределенными , при необходимости элементами.
Юлия	map(func, list)	map(func, list1, list2)	map(func, list1, list2, ..., listN)		ОШИБКА: Несоответствие размеров
Логток	map(Closure, List)	map(Closure, List1, List2)	map(Closure, List1, List2, List3, ...) (up to seven lists)	только аргумента Closure Необходимо создать экземпляр .	Отказ
Математика	func /@ list Map[func, list]	MapThread[func, {list1, list2}]	MapThread[func, {list1, list2, ...}]		Списки должны быть одинаковой длины
Максима	map(f, expr1, ..., exprn) maplist(f, expr1, ..., exprn)			карта возвращает выражение, ведущий оператор которого тот же, что и в выражениях; Maplist возвращает список
OCaml	List.map func list Array.map func array	List.map2 func list1 list2			вызывает исключение Invalid_argument
ПАРИ/ГП	apply(func, list)				—
Перл	map block list map expr, list			В блоке или выражении специальная переменная $_ по очереди хранит каждое значение из списка.	Помощник List::MoreUtils::each_array объединяет более одного списка, пока не будет исчерпан самый длинный, заполняя остальные undef.
PHP	array_map(callable, array)	array_map(callable, array1,array2)	array_map(callable, array1,array2, ...)	Количество параметров для вызываемых должно соответствовать количеству массивов.	расширяет более короткие списки NULL элементами
Пролог	maplist(Cont, List1, List2).	maplist(Cont, List1, List2, List3).	maplist(Cont, List1, ...).	Аргументы списка являются входными, выходными или и тем, и другим. Включает также zipWith, unzip, all	Тихий сбой (не ошибка)
Питон	map(func, list)	map(func, list1, list2)	map(func, list1, list2, ...)	Возвращает список в Python 2 и итератор в Python 3.	zip() и map() (3.x) останавливается после окончания кратчайшего списка, тогда как map() (2.х) и itertools.zip_longest() (3.x) расширяет более короткие списки с помощью None предметы
Рубин	enum.collect {block} enum.map {block}	enum1.zip(enum2).map {block}	enum1.zip(enum2, ...).map {block} [enum1, enum2, ...].transpose.map {block}	enum is an Enumeration	останавливается в конце вызываемого объекта (первый список); если какой-либо другой список короче, он дополняется нулевыми элементами
Ржавчина	list1.into_iter().map(func)	list1.into_iter().zip(list2).map(func)		тот Iterator::map и Iterator::zipметоды одновременно берут на себя ответственность за исходный итератор и возвращают новый; тот Iterator::zip метод внутренне вызывает IntoIterator::into_iter метод на list2	останавливается после окончания более короткого списка
С - Р	lapply(list, func)	mapply(func, list1, list2)	mapply(func, list1, list2, ...)		Более короткие списки цикличны
Скала	list.map(func)	(list1, list2).zipped.map(func)	(list1, list2, list3).zipped.map(func)	примечание: более 3 невозможно.	останавливается после окончания более короткого списка
Схема (включая хитрость и рэкет )	(map func list)	(map func list1 list2)	(map func list1 list2 ...)		все списки должны иметь одинаковую длину (SRFI-1 расширяется, чтобы принимать списки разной длины)
Болтовня	aCollection collect: aBlock	aCollection1 with: aCollection2 collect: aBlock			Не удалось
Стандартный ML	map func list	ListPair.map func (list1, list2) ListPair.mapEq func (list1, list2)		Для карты с двумя аргументами func принимает аргументы в кортеже.	ListPair.map останавливается после окончания кратчайшего списка, тогда как ListPair.mapEq поднимает UnequalLengths исключение
Быстрый	sequence.map(func)	zip(sequence1, sequence2).map(func)			останавливается после того, как заканчивается кратчайший список
XPath 3 XQuery 3	list ! block for-each(list, func)	for-each-pair(list1, list2, func)		В block элемент контекста . сохраняет текущее значение	останавливается после того, как заканчивается кратчайший список

См. также

• Функтор (функциональное программирование)
• Архивирование (информатика) или zip, сопоставление «списка» с несколькими списками.
• Фильтр (функция высшего порядка)
• Сгиб (функция высшего порядка)
• цикл foreach
• Бесплатный моноид
• Функциональное программирование
• Функция высшего порядка
• Понимание списка
• Карта (параллельный шаблон)