Tecnicamente, uma Higher Order Function é simplesmente uma função que faz pelo menos uma destas coisas:
- Aceita uma função como um dos seus argumentos.
- Devolve uma função como resultado.
No mundo da programação funcional, o uso tende a ser mais restrito.
O termo refere-se geralmente a funções como filter, map e reduce, que aplicam uma função passada aos elementos de uma coleção.
Operar sobre coleções
A esta altura do programa, já vimos várias formas de aplicar uma operação a todos os elementos de uma coleção iterável, como um Vector:
- Usar um ciclo (como a maioria das linguagens de programação desde o início da computação digital).
- Usar uma compreensão (ao estilo do Python).
- Usar broadcasting (sintaxe característica de Julia, embora com uma grande dívida ao R, ao Matlab e ao NumPy).
Este conceito centra-se nas funções de ordem superior (familiares de qualquer linguagem funcional, como Haskell ou F#).
Outras abordagens possíveis incluem:
- Recursão (como nas linguagens da família ML).
- Julia permite isto, mas sem otimização de chamadas em cauda corre o risco de provocar um transbordo da pilha.
- Metaprogramação com macros (tradicionalmente uma característica do Lisp).
- É amplamente utilizada na programação avançada em Julia, mas usa-a com cautela na maioria dos casos.
- As outras opções são provavelmente mais fáceis de escrever e muito mais fáceis de depurar.
Filtragem
A função filter() recebe uma função cujo valor de retorno é Boolean e aplica-a a uma coleção.
Só os elementos que devolvem true são incluídos no valor devolvido, que é do mesmo tipo básico que a coleção de entrada (ver abaixo).
julia> filter(iseven, 1:6)
3-element Vector{Int64}:
2
4
6
# String is a collection of Chars, so String in -> String out
julia> filter(!isascii, "Hrōðgār")
"ōðā"
# tuple input -> tuple output
julia> filter(iseven, (1, 2, 3, 4, 5))
(2, 4)
Com arrays multidimensionais, filter achata as dimensões de entrada e devolve um Vector: a principal exceção a qualquer regra sobre o tipo de saída corresponder ao tipo de entrada.
julia> m
2×3 Matrix{Int64}:
1 2 3
4 5 6
julia> filter(isodd, m)
3-element Vector{Int64}:
1
5
3
Os exemplos acima usam funções incorporadas, mas o uso de funções anónimas é muito comum neste contexto.
julia> filter(x -> x % 3 == 0, 1:20)
6-element Vector{Int64}:
3
6
9
12
15
18
Existe também uma versão que atua no local, filter!(), tal como acontece com muitas das funções deste conceito.
Mapeamento
A função map() transforma uma coleção aplicando uma função a cada elemento.
Em casos simples, isto pode ser semelhante ao broadcasting, com a forma da saída a corresponder à da entrada.
julia> map(√, [1, 4, 9])
3-element Vector{Float64}:
1.0
2.0
3.0
julia> map(x -> x^2 + 1, 1:4)
4-element Vector{Int64}:
2
5
10
17
julia> m
2×3 Matrix{Int64}:
1 2 3
4 5 6
julia> map(√, m)
2×3 Matrix{Float64}:
1.0 1.41421 1.73205
2.0 2.23607 2.44949
map() também opera elemento a elemento sobre várias coleções.
julia> map(*, [1, 2], [3, 4])
2-element Vector{Int64}:
3
8
Conceptualmente, podemos pensar nisto como equivalente a executar zip() sobre as várias coleções de entrada e depois map() sobre cada elemento do resultado intermédio.
Isto é apenas uma analogia aproximada, que não diz nada sobre a implementação!
Tal como acontece com zip(), as coleções com formas diferentes são truncadas para a(s) dimensão(ões) da mais pequena.
Por vezes, só são necessários os efeitos secundários da função passada, como uma escrita numa base de dados ou um push! para um array.
Nesse caso, está disponível a função de ordem superior foreach(), que devolve sempre nothing.
Redução
A função reduce() recebe uma função de 2 argumentos e aplica-a a uma coleção, o que provoca uma redução de dimensionalidade.
Isto pode soar confuso em abstrato, mas pensa em funções como sum() ou prod(), que recebem uma coleção e devolvem um único valor.
julia> sum(1:4) # add
10
julia> prod(1:4) # multiply
24
Estas funções especiais são altamente otimizadas e devem ser sempre usadas quando existem.
Outros exemplos incluem maximum() e minimum(), as funções lógicas all() e any() e muitas funções estatísticas.
Apenas a título ilustrativo, considera a mesma funcionalidade implementada com a reduce(), mais genérica (lembra-te de que os operadores infixos + e * são, na realidade, funções internamente).
julia> reduce(+, 1:4) # add
10
julia> reduce(*, 1:4) # multiply
24
Tal como sum() e outras funções de agregação, reduce() pode receber um argumento de palavra-chave opcional, dims, para especificar a(s) dimensão(ões) a reduzir.
julia> m
2×3 Matrix{Int64}:
1 2 3
4 5 6
julia> reduce(+, m; dims=1)
1×3 Matrix{Int64}:
5 7 9
Estes exemplos são fáceis, porque a adição e a multiplicação são comutativas (1+2 == 2+1) e associativas ( (1+2)+3 == 1+(2+3) ).
Isto está longe de ser universal!
Até operações tão comuns como a subtração e a divisão são não associativas.
Há ainda o problema adicional de os erros de vírgula flutuante se poderem acumular ao longo de coleções grandes, pelo que uma redução da esquerda para a direita pode dar uma resposta ligeiramente diferente de uma da direita para a esquerda.
A direção da função reduce de Julia depende da implementação e não é garantida.
Para controlar a direção explicitamente, existem as funções foldl() e foldr(), que começam, na teoria, na "esquerda" e na "direita", respetivamente (na prática, em cima e em baixo, no caso de um Vector).
julia> foldl(-, 1:3) # (1 - 2) - 3
-4
julia> foldr(-, 1:3) # 1 - (2 - 3)
2
Repara que estas funções se destinam a coleções que podem ser tratadas como unidimensionais, devolvendo um resultado escalar.
O uso de um argumento dims não é suportado em foldl e foldr, só em reduce.
MapReduce
Combinar uma operação map com uma reduce é muito comum em vários domínios da programação.
Podíamos executar map sequencialmente e depois reduce sobre uma coleção intermédia.
No entanto, isto é, na melhor das hipóteses, ineficiente, e escala muito mal à medida que a coleção cresce.
Recomenda-se vivamente a utilização da função combinada mapreduce().
Pode implementar um algoritmo com um desempenho muito melhor, que intercala as operações de map/reduce.
O primeiro argumento é a função com que se faz o map e o segundo é o operador de redução.
julia> mapreduce(x -> x^2 + 1, +, 1:3)
17
# equivalent to (2 + 5 + 10)
julia> sum(map(x -> x^2 + 1, 1:3))
17
Como seria de esperar, Julia também tem as funções mapfoldl() e mapfoldr() para as situações em que a direção é importante.
Exercício de aprendizagem
