Programação · conceitos · Haskell

O que é uma função de ordem superior?

Na maioria das linguagens, uma função é algo que se chama. Na programação funcional, uma função também é um valor: pode-se guardá-la numa variável, passá-la a outra função e receber uma como resultado. Uma função de ordem superior é exatamente a que faz uma destas duas últimas coisas. Este guia explica o que é uma função de ordem superior, por que map, filter e fold são os exemplos clássicos, como substituem os laços e como aparecem em Haskell.

A definição curta

Uma função de ordem superior é uma função que recebe uma ou mais funções como argumento, devolve uma função como resultado, ou ambas. Uma função que não faz nenhuma das duas — que só recebe e devolve valores simples como números ou cadeias — diz-se de primeira ordem. O termo «ordem superior» significa simplesmente que opera sobre funções, tal como uma função comum opera sobre dados.

Isto só funciona numa linguagem em que as funções são valores de primeira classe: coisas que se podem nomear, passar e devolver, tal como um inteiro. Haskell, JavaScript, Python, Swift e muitas outras tratam as funções assim, e é isso que torna as funções de ordem superior possíveis.

As três clássicas: map, filter e fold

Quase toda a base de código funcional se apoia em três funções de ordem superior. Cada uma recebe uma função como argumento e aplica-a a uma coleção:

• map aplica uma função a cada elemento de uma lista e devolve uma nova lista com os resultados. map (+1) [1,2,3] dá [2,3,4] — a função (+1) é o argumento.
• filter mantém apenas os elementos para os quais uma função devolve verdadeiro. filter even [1,2,3,4] dá [2,4] — aqui even é a função que passas.
• fold (também chamado reduce) reduz uma lista a um único valor combinando os elementos dois a dois. foldr (+) 0 [1,2,3] soma-os até 6 — o passo de combinação (+) é a função passada como argumento.

Em cada caso, fornece o pequeno pedaço de lógica — incrementar, «é par», somar — e a função de ordem superior trata de percorrer a lista. Descreve o quê fazer a cada elemento, não a mecânica do como percorrê-los.

Como substituem os laços

Numa linguagem imperativa escrever-se-ia um laço com um contador, um acumulador e um índice explícito. A mesma intenção expressa com uma função de ordem superior cabe numa só linha, porque a iteração já está integrada em map ou fold. Por isso o código puramente funcional, que evita contadores de laço mutáveis, se apoia tanto nestas funções e na recursão — juntas cobrem o trabalho que noutros lugares os laços fazem. As compreensões de listas são muitas vezes um atalho legível para a mesma combinação de map e filter.

Devolver uma função: onde se torna poderoso

A outra metade da definição — funções que devolvem funções — é igualmente comum. Uma função pode construir e devolver uma nova função especializada. Um exemplo clássico é o «criador de multiplicadores»: dás-lhe um número e ele devolve uma função que multiplica a sua entrada por esse número. Chama-o com 3 e obténs uma função «vezes três» utilizável como qualquer outra. O criador é de ordem superior porque o seu resultado é, por sua vez, uma função.

Em Haskell, isto está entrelaçado na linguagem através do currying: toda a função de vários argumentos é, na verdade, uma cadeia de funções de um só argumento, cada uma devolvendo a seguinte. Por isso map (+1) funciona — (+1) é a função de adição com um argumento já fornecido, que devolve uma função que ainda espera o outro. Esta aplicação parcial são as funções de ordem superior em ação, muitas vezes sem se dar conta.

Funções de ordem superior em Haskell

Haskell torna a ideia explícita nas suas assinaturas de tipo. O tipo de map escreve-se map :: (a -> b) -> [a] -> [b]. Lê da esquerda para a direita: o primeiro argumento (a -> b) é, por sua vez, uma função — essa é a parte de ordem superior — seguido de uma lista de a, produzindo uma lista de b. As setas tornam visível no papel que se está a passar uma função. O mesmo padrão aparece em filter :: (a -> Bool) -> [a] -> [a] e em toda a biblioteca padrão.

Muitas vezes passas estas funções em linha como lambdas, pequenas funções anónimas escritas com uma barra invertida, como map (\x -> x * x) [1,2,3] para elevar ao quadrado cada elemento. Quer passes uma função com nome, uma secção de operador como (*2) ou uma lambda, é o mesmo mecanismo: uma função a viajar como valor para dentro de uma função de ordem superior.

Por que importam

As funções de ordem superior permitem isolar a forma comum de um cálculo — «fazer algo a cada elemento», «manter os que correspondem», «combiná-los todos» — e reutilizá-la com uma lógica diferente ligada. O resultado: menos código repetido, código que se lê mais perto da sua intenção e pequenos blocos de lógica testáveis e componíveis. São o tijolo sobre o qual grande parte da programação funcional de Haskell se exprime, e combinadas com a avaliação preguiçosa de Haskell permitem até mapear e filtrar listas conceptualmente infinitas.

Os compromissos honestos

As funções de ordem superior exigem alguma habituação: ler um foldr ou uma cadeia map . filter é uma competência, e lambdas profundamente aninhadas podem tornar-se difíceis de seguir. Passar funções por todo o lado também pode tornar um stack trace menos evidente quando algo corre mal. O ganho — muito menos código de iteração repetitivo e uma lógica recombinável — explica por que se espalharam muito para além das linguagens funcionais, até ao JavaScript, Python e Swift do dia a dia. Usadas com moderação, tornam o código mais curto e claro; usadas em excesso, podem obscurecê-lo como qualquer outra ferramenta.

Perguntas frequentes

Explore mais explicações claras no nosso índice de guias.