Mapa (función de orden superior)

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 , devolviendo los resultados en una colección del mismo tipo. A menudo se la denomina `apply-to-all` cuando se considera en forma funcional .

El concepto de mapa no se limita a las listas: funciona para contenedores secuenciales , contenedores con estructura de árbol o incluso contenedores abstractos como futuros y promesas .

Supongamos que hay una lista de números enteros [1, 2, 3, 4, 5]. Para calcular el cuadrado de cada número entero, primero se definiría una función para squareun solo número (mostrada aquí en Haskell ):

x al cuadrado = x * x

Después, llame a:

>>> mapa cuadrado [ 1 , 2 , 3 , 4 , 5 ]

lo que produce [1, 4, 9, 16, 25], demostrando que mapha recorrido toda la lista y aplicado la función squarea cada elemento.

Ejemplo visual

A continuación, se muestra una vista de cada paso del proceso de mapeo para una lista de enteros X = [0, 5, 8, 3, 2, 1]que se mapea en una nueva lista X'según la función.${\displaystyle f(x)=x+1}$ :

Se mapproporciona como parte del preludio base de Haskell (es decir, la "biblioteca estándar") y se implementa de la siguiente manera:

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

En Haskell, la función polimórfica se generaliza a una función politípica , que se aplica a cualquier tipo que pertenezca a la clase de tipos .map::(a->b)->[a]->[b]fmap::Functorf=>(a->b)->fa->fbFunctor

El constructor de tipos de listas []se puede definir como una instancia de la Functorclase de tipos utilizando la mapfunción del ejemplo anterior:

instancia Functor [] donde fmap = mapa

Otros ejemplos de Functorcasos incluyen árboles:

-- un árbol binario simple datos Árbol a = Hoja a | Bifurcación ( Árbol a ) ( Árbol a )instancia Functor Tree donde fmap f ( Leaf x ) = Leaf ( f x ) fmap f ( Fork l r ) = Fork ( fmap f l ) ( fmap f r )

El mapeo sobre un árbol produce:

>>> 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 de tipo, fmapestá obligada contractualmente a obedecer las leyes del functor:

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 a elemento para varios tipos de colecciones .

La base matemática de los mapas permite una serie de optimizaciones . La ley de composición asegura que ambos

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

conducen al mismo resultado; es decir,${\displaystyle \operatorname {map} (f)\circ \operatorname {map} (g)=\operatorname {map} (f\circ g)}$Sin embargo, la segunda forma es más eficiente de calcular que la primera, ya que cada una maprequiere 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 ]}

Las funciones de mapeo pueden definirse, y a menudo se definen, en términos de un pliegue como foldr, lo que significa que se puede realizar una fusión de pliegue de mapeo : foldr f z . map ges equivalente a foldr (f . g) z.

La implementación de `map` en listas enlazadas simples no es recursiva de cola , por lo que puede acumular muchos marcos en la pila al llamarla con una lista grande. Muchos lenguajes ofrecen como alternativa una función `reverse map`, que es equivalente a invertir una lista mapeada, pero sí es recursiva de cola. Aquí se muestra una implementación que utiliza la función `fold -left`.

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

Dado que invertir una lista enlazada simple también es recursiva de cola, se pueden combinar `reverse` y `reverse-map` para realizar un mapeo normal de forma recursiva de cola, aunque requiere realizar dos pasadas sobre la lista.

La función map se originó en los lenguajes de programación funcional .

El lenguaje Lisp introdujo una función de mapeo 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 restos sucesivas:

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

La función maplistaún está disponible en versiones más recientes de Lisp como Common Lisp , ^{[ 5 ]} aunque se preferirían funciones como mapcaro la más genérica .map

Elevar al cuadrado los elementos de una lista usando maplistse escribiría en notación de expresión S de esta manera:

( lista de mapas ( lambda ( l ) ( sqr ( car l ))) ' ( 1 2 3 4 5 ))

Utilizando la función mapcar, el ejemplo anterior se escribiría así:

( mapcar ( función sqr ) ' ( 1 2 3 4 5 ))

Hoy en día, las funciones de mapeo son compatibles (o pueden definirse) en muchos lenguajes procedimentales , orientados a objetos y multiparadigmáticos también: En la biblioteca estándar de C++ , se llama o , en la biblioteca LINQ de C# (3.0), se proporciona como un método de extensión llamado . Map también es una operación de uso frecuente 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 llama ( indicando 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::transformstd::ranges::transformSelectmapcollectmapmapcar-car

A veces, `map` se generaliza para aceptar funciones diádicas (de dos argumentos) que pueden aplicar una función proporcionada por el usuario a 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 dos o más listas encuentra el problema de manejar cuando las listas tienen diferentes longitudes. Varios lenguajes difieren en esto. Algunos lanzan una excepción. Otros se detienen después de la longitud de la lista más corta e ignoran los elementos adicionales en las otras listas. Otros continúan hasta la longitud de la lista más larga, y para las listas que ya han terminado, pasan un valor de marcador de posición a la función que indica que no hay ningún valor.

En lenguajes que admiten funciones de primera clase y currificación , mapse puede aplicar parcialmente para elevar una función que trabaja en un solo valor a un equivalente elemento a elemento que trabaja en un contenedor completo; por ejemplo, map squarees una función de Haskell que eleva al cuadrado cada elemento de una lista.

• Functor (programación funcional)
• Zipping (informática) o zip, mapeo de 'lista' sobre múltiples listas.
• Filtro (función de orden superior)
• Plegado (función de orden superior)
• bucle foreach
• monoide libre
• Programación funcional
• Función de orden superior
• Comprensión de listas
• Mapa (patrón paralelo)