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

Эта статья в значительной степени или полностью основана на одном источнике . Соответствующее обсуждение можно найти на странице обсуждения . Пожалуйста, помогите улучшить эту статью , добавив ссылки на дополнительные источники .
Поиск источников: функция высшего порядка «Карта» - новости · газеты · книги · ученый · JSTOR ( ноябрь 2012 г. )

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

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

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

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

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

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

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

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

Наглядный пример [ править ]

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

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

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

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

map  ::  ( a  ->  b )  ->  [ a ]  ->  [ b ] map  _  []  =  [] map  f  ( x  :  xs )  =  f  x  :  map  f  xs

Обобщение [ править ]

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

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

instance  Functor  []  где  fmap  =  map

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

- простое двоичное дерево данных  Tree  a  =  Leaf  a  |  Вилка  ( Дерево  а )  ( Дерево  а )экземпляр  Functor  Tree,  где  fmap  f  ( Leaf  x )  =  Leaf  ( f  x )  fmap  f  ( Fork  l  r )  =  Fork  ( fmap  f  l )  ( fmap  f  r )

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

>>>  fmap  square  ( Fork  ( Fork  ( Leaf  1 )  ( Leaf  2 ))  ( Fork  ( Leaf  3 )  ( Leaf  4 ))) Fork  ( Fork  ( Leaf  1 )  ( Leaf  4 ))  ( Fork  ( Leaf  9 )  ( Leaf  16 ))

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

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

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

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

Более того, если $F$ и $G$ - два функтора, естественное преобразование - это функция полиморфного типа, которая уважает $fmap$ : ${\ displaystyle h: \ forall TF (T) \ to G (T)}$

{\ displaystyle h_ {Y} \ circ \ operatorname {fmap} (f) = \ operatorname {fmap} (f) \ circ h_ {X}}

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

{\ displaystyle f: X \ to Y}

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

Оптимизация [ править ]

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

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

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

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

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

reverseMap  f  =  foldl  ( \ ys  x  ->  f  x  :  ys )  []

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

Сравнение языков [ править ]

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

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

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

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

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

( maplist  ( лямбда  ( l )  ( sqr  ( car  l )))  ' ( 1  2  3  4  5 ))

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

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

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

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

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

Карта на разных языках
Язык	карта	Карта 2 списков	Сопоставить n списков	Примечания	Работа со списками разной длины
APL	`func list`	`list1 func list2`	`func/ list1 list2 list3 list4`	Возможности обработки массивов APL делают такие операции, как map, неявными	ошибка длины, если длина списка не равна или 1
Common Lisp	`(mapcar func list)`	`(mapcar func list1 list2)`	`(mapcar func list1 list2 ...)`		останавливается после длины самого короткого списка
C ++	`std::transform(begin, end, result, func)`	`std::transform(begin1, end1, begin2, result, func)`		в заголовке <алгоритм> begin , end и result - итераторы, результат записывается, начиная с результата
C #	`ienum.Select(func)` или раздел select	`ienum1.Zip(ienum2, func)`		`Select`- это метод расширения. ienum. IEnumerable `Zip`представлен в .NET 4.0. Аналогично во всех языках .NET.	останавливается после окончания самого короткого списка
CFML	`obj.map(func)`			Где `obj`массив или структура. `func`получает в качестве аргументов значение каждого элемента, его индекс или ключ и ссылку на исходный объект.
Clojure	`(map func list)`	`(map func list1 list2)`	`(map func list1 list2 ...)`		останавливается после окончания самого короткого списка
D	`list.map!func`	`zip(list1, list2).map!func`	`zip(list1, list2, ...).map!func`		Указывается для архивирования с помощью StoppingPolicy: short ,est, or requireSameLength
Erlang	`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)`		останавливается после окончания самого короткого списка
F #	`List.map func list`	`List.map2 func list1 list2`		Функции существуют для других типов ( Seq и Array )	Выбрасывает исключение
Groovy	`list.collect(func)`	`[list1 list2].transpose().collect(func)`	`[list1 list2 ...].transpose().collect(func)`
Haskell	`map func list`	`zipWith func list1 list2`	`zipWithn func list1 list2 ...`	`n`соответствует количеству списков; предопределено до`zipWith7`	останавливается после окончания самого короткого списка
Haxe	`array.map(func)` `list.map(func) Lambda.map(iterable, func)`
J	`func list`	`list1 func list2`	`func/ list1, list2, list3 ,: list4`	Возможности обработки массивов J делают такие операции, как map, неявными	ошибка длины, если длины списков не равны
Java 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)`		ОШИБКА: несоответствие размеров
Logtalk	`map(Closure, List)`	`map(Closure, List1, List2)`	`map(Closure, List1, List2, List3, ...) (up to seven lists)`	Должен быть создан только аргумент Closure .	Отказ
Mathematica	`func /@ list Map[func, list]`	`MapThread[func, {list1, list2}]`	`MapThread[func, {list1, list2, ...}]`		Списки должны быть одинаковой длины
Максима	`map(f, expr₁, ..., expr_n) maplist(f, expr₁, ..., expr_n)`			map возвращает выражение, ведущий оператор которого совпадает с оператором выражений; maplist возвращает список
OCaml	`List.map func list Array.map func array`	`List.map2 func list1 list2`			вызывает исключение Invalid_argument
PARI / GP	`apply(func, list)`				N / A
Perl	`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, ...).`	Аргументы списка являются входными, выходными или и тем, и другим. Subsumes также zipWith, unzip, all	Тихий сбой (не ошибка)
Python	`map(func, list)`	`map(func, list1, list2)`	`map(func, list1, list2, ...)`	Возвращает список в Python 2 и итератор в Python 3.	`zip()`и `map()`(3.x) останавливается после окончания самого короткого списка, тогда как `map()`(2.x) и `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`	останавливается после окончания более короткого списка
S - R	`lapply(list, func)`	`mapply(func, list1, list2)`	`mapply(func, list1, list2, ...)`		Более короткие списки прокручиваются
Scala	`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`элементе контекста `.`хранится текущее значение	останавливается после окончания самого короткого списка

См. Также [ править ]

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

Ссылки [ править ]

^ «Слияние карт: ускорение Haskell на 225%»
^ Дж. Маккарти, К. Мэлинг, С. Рассел, Н. Рочестер, С. Голдберг, Дж. Слэгл. Руководство программиста LISP. Март-апрель 1959 г.
^ Дж. Маккарти: Символ манипулирования языком - пересмотры языка. Записка AI № 4, октябрь 1958 г.
^ Функция MAPC, MAPCAR, MAPCAN, MAPL, MAPLIST, MAPCON в ANSI Common Lisp

[1] «Слияние карт: ускорение Haskell на 225%»

[2] Дж. Маккарти, К. Мэлинг, С. Рассел, Н. Рочестер, С. Голдберг, Дж. Слэгл. Руководство программиста LISP. Март-апрель 1959 г.

[3] Дж. Маккарти: Символ манипулирования языком - пересмотры языка. Записка AI № 4, октябрь 1958 г.

[4] Функция MAPC, MAPCAR, MAPCAN, MAPL, MAPLIST, MAPCON в ANSI Common Lisp