En muchos lenguajes de programación , map es una función de orden superior que aplica una función dada a cada elemento de una colección , por ejemplo, una lista o un conjunto , y devuelve los resultados en una colección del mismo tipo. A menudo se la denomina "aplicar a todos" cuando se la considera en forma funcional .
El concepto de mapa no se limita a las listas: funciona para contenedores secuenciales , contenedores tipo árbol o incluso contenedores abstractos como futuros y promesas .
Supongamos que hay una lista de números enteros [1, 2, 3, 4, 5]y queremos calcular el cuadrado de cada uno de ellos. Para ello, primero definamos una función para squareun único número (como se muestra aquí en Haskell ):
cuadrado x = x * x Luego llamar a:
>>> Mapa cuadrado [ 1 , 2 , 3 , 4 , 5 ] lo que produce [1, 4, 9, 16, 25], lo que demuestra que mapha recorrido toda la lista y ha aplicado la función squarea cada elemento.
A continuación, se muestra una vista de cada paso del proceso de mapeo para una lista de números enteros X = [0, 5, 8, 3, 2, 1]que se asignan a una nueva lista X'de acuerdo con la función :
Se mapproporciona como parte del preludio base de Haskell (es decir, la "biblioteca estándar") y se implementa como:
mapa : :( a -> b ) -> [ a ] -> [ b ] mapa _ [] = [] mapa f ( x : xs ) = f x : mapa f xs En Haskell, la función polimórfica map :: (a -> b) -> [a] -> [b] se generaliza a una función politípica fmap :: Functor f => (a -> b) -> f a -> f b , que se aplica a cualquier tipo que pertenezca a la clase de tipos .Functor
El constructor de tipos de listas []se puede definir como una instancia de la Functorclase de tipo utilizando la mapfunción del ejemplo anterior:
instancia Functor [] donde fmap = map Otros ejemplos de Functorinstancias incluyen árboles:
-- un árbol binario simple datos Árbol a = Hoja a | Bifurcación ( Árbol a ) ( Árbol a ) instancia Functor Árbol donde fmap f ( Hoja x ) = Hoja ( f x ) fmap f ( Horquilla l r ) = Horquilla ( fmap f l ) ( fmap f r ) Al mapear un árbol se obtiene lo siguiente:
>>> fmap cuadrado ( Horquilla ( Horquilla ( Hoja 1 ) ( Hoja 2 )) ( Horquilla ( Hoja 3 ) ( Hoja 4 ))) Horquilla ( Horquilla ( Hoja 1 ) ( Hoja 4 )) ( Horquilla ( Hoja 9 ) ( Hoja 16 )) Para cada instancia de la Functorclase tipo, fmapestá contractualmente obligado a obedecer las leyes de los funtores:
fmap id ≡ id -- ley de identidad fmap ( f . g ) ≡ fmap f . fmap g -- ley de composición donde .denota la composición de funciones en Haskell.
Entre otros usos, esto permite definir operaciones elemento por elemento para varios tipos de colecciones .
En teoría de categorías , un funtor consta de dos mapas: uno que envía cada objeto de la categoría a otro objeto , y uno que envía cada morfismo a otro morfismo , que actúa como un homomorfismo en categorías (es decir, respeta los axiomas de la categoría). Interpretando el universo de tipos de datos como una categoría , con morfismos siendo funciones, entonces un constructor de tipos que es miembro de la clase de tipos es la parte del objeto de tal funtor, y es la parte del morfismo. Las leyes del funtor descritas anteriormente son precisamente los axiomas del funtor de la teoría de categorías para este funtor.FFunctorfmap :: (a -> b) -> F a -> F b
Los funtores también pueden ser objetos en categorías, con "morfismos" llamados transformaciones naturales . Dados dos funtores , una transformación natural consiste en una colección de morfismos , uno para cada objeto de la categoría , que son 'naturales' en el sentido de que actúan como una 'conversión' entre los dos funtores, sin tener en cuenta los objetos a los que se aplican los funtores. Las transformaciones naturales corresponden a funciones de la forma , donde es una variable de tipo cuantificada universalmente – no sabe nada sobre el tipo que habita . El axioma de naturalidad de tales funciones se satisface automáticamente porque es un llamado teorema libre, dependiendo del hecho de que es paramétricamente polimórfico . [1] Por ejemplo, , que invierte una lista, es una transformación natural, como lo es , que aplana un árbol de izquierda a derecha, e incluso , que ordena una lista en función de una función de comparación proporcionada.eta :: F a -> G aaetaareverse :: List a -> List aflattenInorder :: Tree a -> List asortBy :: (a -> a -> Bool) -> List a -> List a
La base matemática de los mapas permite una serie de optimizaciones . La ley de composición garantiza que tanto
(map f . map g) listymap (f . g) listconducen al mismo resultado, es decir, . Sin embargo, la segunda forma es más eficiente de calcular que la primera, porque cada una requiere reconstruir una lista completa desde cero. Por lo tanto, los compiladores intentarán transformar la primera forma en la segunda; este tipo de optimización se conoce como fusión de mapas y es el análogo funcional de la fusión de bucles . [2]map
Las funciones de mapa se pueden definir, y a menudo se definen, en términos de un pliegue como foldr, lo que significa que se puede hacer una fusión de mapa-pliegue : foldr f z . map ges equivalente a foldr (f . g) z.
La implementación del mapa anterior en listas enlazadas simples no es recursiva en la cola , por lo que puede generar una gran cantidad de marcos en la pila cuando se llama con una lista grande. Muchos lenguajes proporcionan de manera alternativa una función de "mapa inverso", que es equivalente a invertir una lista mapeada, pero es recursiva en la cola. Aquí hay una implementación que utiliza la función fold -left.
reverseMap f = foldl ( \ ys x -> f x : ys ) [] Dado que invertir una lista simplemente enlazada también es recursivo en la cola, se pueden componer reverse y reverse-map para realizar un mapa normal de forma recursiva en la cola, aunque requiere realizar dos pasadas sobre la lista.
La función de mapa se originó en los lenguajes de programación funcional .
El lenguaje Lisp introdujo una función de mapa llamada maplist[3] en 1959, con versiones ligeramente diferentes que ya aparecían en 1958. [4] Esta es la definición original de maplist, que mapea una función sobre listas de descansos sucesivas:
maplist[x;f] = [null[x] -> NIL;T -> cons[f[x];maplist[cdr[x];f]]]
La función maplisttodavía está disponible en Lisp más nuevos como Common Lisp , [5] aunque serían preferibles funciones como mapcaro más genéricas .map
El cuadrado de los elementos de una lista maplistse escribiría en notación de expresión S de la siguiente manera:
( maplist ( lambda ( l ) ( sqr ( car l ))) ' ( 1 2 3 4 5 )) Usando la función mapcar, el ejemplo anterior se escribiría así:
( mapcar ( función sqr ) ' ( 1 2 3 4 5 )) En la actualidad, las funciones de mapeo también son compatibles (o pueden definirse) en muchos lenguajes procedimentales , orientados a objetos y multiparadigma : en la biblioteca estándar de C++ , se denomina , en la biblioteca LINQ de C# (3.0), se proporciona como un método de extensión denominado . Map también es una operación utilizada con frecuencia en lenguajes de alto nivel como ColdFusion Markup Language (CFML), Perl , Python y Ruby ; la operación se llama en los cuatro lenguajes. También se proporciona un alias para en Ruby (de Smalltalk ). Common Lisp proporciona una familia de funciones similares a map; la que corresponde al comportamiento descrito aquí se denomina ( que indica acceso mediante la operación CAR ). También hay lenguajes con construcciones sintácticas que proporcionan la misma funcionalidad que la función map.std::transformSelectmapcollectmapmapcar-car
Map se generaliza a veces para aceptar funciones diádicas (de 2 argumentos) que pueden aplicar una función proporcionada por el usuario a los elementos correspondientes de dos listas. Algunos lenguajes usan nombres especiales para esto, como map2 o zipWith . Los lenguajes que usan funciones variádicas explícitas pueden tener versiones de map con aridad variable para admitir funciones de aridad variable . Map con 2 o más listas se enfrenta al problema del manejo cuando las listas tienen longitudes diferentes. Varios lenguajes difieren en esto. Algunos lanzan una excepción. Algunos se detienen después de la longitud de la lista más corta e ignoran los elementos adicionales en las otras listas. Algunos continúan hasta la longitud de la lista más larga y, para las listas que ya terminaron, pasan algún valor de marcador de posición a la función que indica que no hay valor.
En los lenguajes que admiten funciones de primera clase y currying , mapse puede aplicar parcialmente para elevar una función que funciona solo en un valor a un equivalente elemento por elemento que funciona en un contenedor completo; por ejemplo, map squarees una función Haskell que eleva al cuadrado cada elemento de una lista.
fmapes estricto. Wadler, Philip (septiembre de 1989). ¡Teoremas gratis! (PDF) . 4º Simposio Internacional sobre Lenguajes de Programación Funcional y Arquitectura de Computadoras. Londres: Association for Computing Machinery .