Карта (функция высшего порядка)
Эта статья в значительной степени или полностью опирается на один источник . ( ноябрь 2012 г. ) |
Во многих языках программирования карта — это функция высшего порядка , которая применяет заданную функцию к каждому элементу коллекции , например списку или множеству , возвращая результаты в коллекцию того же типа. Его часто называют «применить ко всем», если рассматривать его в функциональной форме .
Концепция карты не ограничивается списками: она работает для последовательных контейнеров , древовидных контейнеров или даже абстрактных контейнеров, таких как фьючерсы и промисы .
Примеры: сопоставление списка
[ редактировать ]Предположим, у нас есть список целых чисел [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'
согласно функции :
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
это член Functor
класс типа является объектной частью такого функтора, и fmap :: (a -> b) -> F a -> F b
является частью морфизма. Описанные выше законы функтора являются в точности теоретико-категорными аксиомами функтора для этого функтора.
Функторы также могут быть объектами категорий с «морфизмами», называемыми естественными преобразованиями . Учитывая два функтора , естественная трансформация состоит из набора морфизмов , по одному на каждый объект категории , которые являются «естественными» в том смысле, что они действуют как «преобразование» между двумя функторами, не принимая во внимание объекты, к которым эти функторы применяются. Естественным преобразованиям соответствуют функции вида eta :: F a -> G a
, где a
— это переменная универсального кванторного типа — eta
ничего не знает о типе, который обитает a
. Аксиома естественности таких функций автоматически выполняется, поскольку это так называемая свободная теорема, зависящая от того, что она параметрически полиморфна . [1] Например, 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
привести к тому же результату; то есть, . Однако вторая форма более эффективна для вычисления, чем первая, поскольку каждая map
требует восстановления всего списка с нуля. Поэтому компиляторы попытаются преобразовать первую форму во вторую; этот тип оптимизации известен как объединение карт и является функциональным аналогом объединения циклов . [2]
Функции отображения могут быть и часто определяются в терминах складки , например foldr
, что означает, что можно выполнить слияние карт : foldr f z . map g
эквивалентно foldr (f . g) z
.
Реализация приведенной выше карты для односвязных списков не является хвостовой рекурсивной , поэтому при вызове с большим списком она может накапливать много кадров в стеке. Многие языки поочередно предоставляют функцию «обратного отображения», которая эквивалентна обращению сопоставленного списка, но является хвостовой рекурсией. Вот реализация, которая использует функциюfold -left.
обратная карта f = foldl ( \ ys x -> f x : ys ) []
Поскольку обращение односвязного списка также является хвостовой рекурсией, можно составить обратную карту и обратную карту для выполнения карты нормалей хвостовой рекурсией, хотя для этого потребуется выполнить два прохода по списку.
Сравнение языков
[ редактировать ]Функция карты возникла в функциональных языках программирования.
В языке Lisp появилась функция отображения, называемая maplist
[3] в 1959 году, а несколько иные версии появились уже в 1958 году. [4] Это оригинальное определение понятия maplist
, отображая функцию на последовательные списки отдыха:
Maplist[x;f] = [null[x] -> NIL;T -> cons[f[x];maplist[cdr[x];f]]]
Функция maplist
по-прежнему доступен в более новых Lisp, таких как Common Lisp , [5] хотя функции вроде mapcar
или более общий map
было бы предпочтительнее.
Возведение элементов списка в квадрат с помощью maplist
будет записано в нотации S-выражения следующим образом:
( список карт ( лямбда ( l ) ( sqr ( car l ))) ' ( 1 2 3 4 5 ))
Использование функции mapcar
, приведенный выше пример будет записан так:
( mapcar ( функция sqr ) ' ( 1 2 3 4 5 ))
Сегодня функции отображения поддерживаются (или могут быть определены) во многих процедурных , объектно-ориентированных и мультипарадигмальных языках: в C++ они стандартной библиотеке называются std::transform
, в C# (3.0) он предоставляется как метод расширения, называемый библиотеке LINQ Select
. Map также часто используемая операция в языках высокого уровня, таких как язык разметки 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( | std::transform( | в заголовке <алгоритм> начало , конец и результат являются итераторами результат записывается начиная с результата | ||
С# | 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] | [list1 list2 ...] | ||
Хаскелл | map func list | zipWith func list1 list2 | zipWithn func list1 list2 ... | n соответствует количеству списков; предопределено до zipWith7 | останавливается после того, как заканчивается кратчайший список |
Смешанный | array.map(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) { | List1.map(function (elem1, 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 | MapThread[func, {list1, list2}] | MapThread[func, {list1, list2, ...}] | Списки должны быть одинаковой длины | |
Максима | map(f, expr1, ..., exprn) | карта возвращает выражение, ведущий оператор которого тот же, что и в выражениях; Maplist возвращает список | |||
OCaml | List.map func list | List.map2 func list1 list2 | вызывает исключение Invalid_argument | ||
ПАРИ/ГП | apply(func, list) | — | |||
Перл | map block 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} | enum1.zip(enum2) | enum1.zip(enum2, ...) | 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) | (list1, list2, list3) | примечание: более 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) | Для карты с двумя аргументами 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
- Бесплатный моноид
- Функциональное программирование
- Функция высшего порядка
- Понимание списка
- Карта (параллельный шаблон)
Ссылки
[ редактировать ]- ^ В нестрогом языке , допускающем общую рекурсию, таком как Haskell, это верно только в том случае, если первый аргумент
fmap
является строгим. Уодлер, Филип (сентябрь 1989 г.). Теоремы бесплатно! (PDF) . 4-й международный симпозиум по функциональным языкам программирования и компьютерной архитектуре. Лондон: Ассоциация вычислительной техники . - ^ «Слияние карт: Haskell становится на 225% быстрее»
- ^ Дж. Маккарти, К. Малинг, С. Рассел, Н. Рочестер, С. Голдберг, Дж. Слэгл. Руководство программиста LISP. Март-апрель 1959 г.
- ^ Дж. Маккарти: Язык манипулирования символами - Изменения языка. Памятка AI № 4, октябрь 1958 г.
- ^ Функции MAPC, MAPCAR, MAPCAN, MAPL, MAPLIST, MAPCON в ANSI Common Lisp