Mapa (função de ordem superior) - Map (higher-order function)

Em muitas linguagens de programação , map é o nome de uma função de ordem superior que aplica uma determinada função a cada elemento de um functor , por exemplo, uma lista , retornando uma lista de resultados na mesma ordem. Freqüentemente, é chamado de aplicar a todos quando considerado na forma funcional .

O conceito de um mapa não se limita a listas: ele funciona para contêineres sequenciais , contêineres em forma de árvore ou mesmo contêineres abstratos, como futuros e promessas .

Exemplos: mapeamento de uma lista

Suponha que temos uma lista de inteiros [1, 2, 3, 4, 5]e gostaríamos de calcular o quadrado de cada inteiro. Para fazer isso, primeiro definimos uma função para squareum único número (mostrado aqui em Haskell ):

square x = x * x

Depois podemos ligar

>>> map square [1, 2, 3, 4, 5]

que rende [1, 4, 9, 16, 25], demonstrando que mappercorreu toda a lista e aplicou a função squarea cada elemento.

Exemplo visual

Abaixo, você pode ver uma visão de cada etapa do processo de mapeamento para uma lista de inteiros X = [0, 5, 8, 3, 2, 1]que queremos mapear em uma nova lista de X'acordo com a função  : ${\ displaystyle f (x) = x + 1}$

Visualização das etapas de processamento ao aplicar a função de mapa em uma lista

O mapé fornecido como parte do prelúdio base do Haskell (ou seja, "biblioteca padrão") e é implementado como:

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

Generalização

Em Haskell, a função polimórfica map :: (a -> b) -> [a] -> [b] é generalizada para uma função politípica fmap :: Functor f => (a -> b) -> f a -> f b , que se aplica a qualquer tipo pertencente à classe de tipo . Functor

O construtor de tipo de listas []pode ser definido como uma instância da Functorclasse de tipo usando a mapfunção do exemplo anterior:

instance Functor [] where
  fmap = map

Outros exemplos de Functorinstâncias incluem árvores:

-- a simple binary tree
data Tree a = Leaf a | Fork (Tree a) (Tree a)

instance Functor Tree where  
  fmap f (Leaf x) = Leaf (f x)
  fmap f (Fork l r) = Fork (fmap f l) (fmap f r)

O mapeamento de uma árvore produz:

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

Para cada instância da Functorclasse de tipo, fmapé contratualmente obrigado a obedecer às leis do functor:

fmap id      ≡ id              -- identity law
fmap (f . g) ≡ fmap f . fmap g -- composition law

onde .denota a composição da função em Haskell.

Entre outros usos, isso permite definir operações de elementos para vários tipos de coleções .

Além disso, se F e G são dois functores, uma transformação natural é uma função do tipo polimórfico que respeita fmap : ${\ displaystyle h: \ forall TF (T) \ to G (T)}$

${\ displaystyle h_ {Y} \ circ \ operatorname {fmap} (f) = \ operatorname {fmap} (f) \ circ h_ {X}}$para qualquer função .${\ displaystyle f: X \ a Y}$

Se a função h for definida por polimorfismo paramétrico como na definição de tipo acima, esta especificação é sempre satisfeita.

Otimizações

A base matemática dos mapas permite várias otimizações . A lei de composição garante que ambos

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

levar ao mesmo resultado; isto é ,. No entanto, o segundo formulário é mais eficiente de calcular do que o primeiro, porque cada um requer a reconstrução de uma lista inteira do zero. Portanto, os compiladores tentarão transformar a primeira forma na segunda; esse tipo de otimização é conhecido como fusão de mapa e é o análogo funcional da fusão de loop . ${\ displaystyle \ operatorname {mapa} (f) \ circ \ operatorname {mapa} (g) = \ operatorname {mapa} (f \ circ g)}$map

As funções de mapa podem ser e frequentemente são definidas em termos de uma dobra como foldr, o que significa que se pode fazer uma fusão de dobra do mapa : foldr f z . map gé equivalente a foldr (f . g) z.

A implementação do mapa acima em listas unidas individualmente não é recursiva no final , portanto, pode acumular muitos quadros na pilha quando chamado com uma lista grande. Muitos idiomas fornecem alternadamente uma função de "mapa reverso", que é equivalente a reverter uma lista mapeada, mas é recursiva na cauda. Aqui está uma implementação que utiliza a função fold -left.

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

Visto que a reversão de uma lista unida individualmente também é recursiva na cauda, ​​o mapa reverso e reverso pode ser composto para executar o mapa normal de uma forma recursiva na cauda, ​​embora exija a execução de duas passagens sobre a lista.

Comparação de linguagem

A função de mapa originou-se em linguagens de programação funcionais .

A linguagem Lisp introduziu uma função de mapa chamada maplistem 1959, com versões ligeiramente diferentes já aparecendo em 1958. Esta é a definição original para maplist, mapear uma função em listas de resto sucessivas:

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

A função maplistainda está disponível em Lisps mais recentes, como Common Lisp , embora funções como mapcarou mais genéricas mapsejam preferidas.

Quadrar os elementos de uma lista usando maplistseria escrito em notação de expressão S assim:

(maplist (lambda (l) (sqr (car l))) '(1 2 3 4 5))

Usando a função mapcar, o exemplo acima seria escrito assim:

(mapcar (function sqr) '(1 2 3 4 5))

Hoje funções de mapeamento são suportadas (ou pode ser definida), em muitos processuais , orientada a objeto , e multi-paradigma línguas também: Em C ++ 's biblioteca padrão , ele é chamado std::transform, em C # (3,0)' s biblioteca LINQ, é fornecido como um método de extensão chamado Select. Map também é uma operação freqüentemente usada em linguagens de alto nível, como ColdFusion Markup Language (CFML), Perl , Python e Ruby ; a operação é chamada mapem todos esses quatro idiomas. Um collectalias para maptambém é fornecido em Ruby (de Smalltalk ). Common Lisp fornece uma família de funções semelhantes a mapas; é chamado aquele que corresponde ao comportamento aqui descrito mapcar( -carindicando o acesso através da operação CAR ). Existem também linguagens com construções sintáticas que fornecem a mesma funcionalidade que a função de mapa.

O mapa às vezes é generalizado para aceitar funções diádicas (2 argumentos) que podem aplicar uma função fornecida pelo usuário a elementos correspondentes de duas listas. Alguns idiomas usam nomes especiais para isso, como map2 ou zipWith . As linguagens que usam funções variáveis explícitas podem ter versões de mapa com aridade variável para suportar funções de aridade variável . O mapa com 2 ou mais listas encontra o problema de manuseio quando as listas são de comprimentos diferentes. Vários idiomas diferem nisso. Alguns levantam uma exceção. Alguns param após o comprimento da lista mais curta e ignoram os itens extras nas outras listas. Alguns continuam com o comprimento da lista mais longa e, para as listas que já terminaram, passam algum valor de espaço reservado para a função que não indica nenhum valor.

Em linguagens que suportam funções de primeira classe e currying , mappode ser parcialmente aplicado para levantar uma função que funciona em apenas um valor para um equivalente elementar que funciona em um contêiner inteiro; por exemplo, map squareé uma função Haskell que quadrada cada elemento de uma lista.

Veja também

• Functor (programação funcional)
• Convolução (ciência da computação) , também chamada de conv ou zip
• Filtro (função de ordem superior)
• Dobrar (função de ordem superior)
• para cada
• Monóide grátis
• Programação funcional
• Função de ordem superior
• Compreensão de lista
• Mapa (padrão paralelo)

Referências