Techniquement, une Higher Order Function est simplement une fonction qui fait au moins l'une des choses suivantes :
- Elle accepte une fonction comme l'un de ses arguments.
- Elle renvoie une fonction comme résultat.
Dans le monde de la programmation fonctionnelle, l'usage tend à être plus restreint.
Le terme désigne généralement des fonctions telles que filter, map et reduce, qui appliquent une fonction passée en argument aux éléments d'une collection.
Opérations sur des collections
À ce stade du programme, on a déjà vu différentes façons d'appliquer une opération à tous les éléments d'une collection itérable, comme un Vector :
- Utiliser une boucle (comme la plupart des langages de programmation depuis l'aube de l'informatique).
- Utiliser une compréhension (à la Python).
- Utiliser le broadcasting (une syntaxe propre à Julia, bien qu'avec une grande dette envers R, Matlab et NumPy).
Ce concept se concentre sur les fonctions d'ordre supérieur (que l'on connaît dans tout langage fonctionnel, comme Haskell ou F#).
D'autres approches sont également possibles :
- La récursion (comme dans les langages de la famille ML).
- Julia le permet, mais sans optimisation des appels terminaux, cela risque de provoquer un débordement de pile.
- La métaprogrammation avec des macros (une caractéristique traditionnelle de Lisp).
- Elle est largement utilisée dans la programmation Julia avancée, mais à aborder avec prudence dans la plupart des cas.
- Les autres options seront probablement plus faciles à écrire et bien plus faciles à déboguer.
Filtrage
La fonction filter() prend une fonction passée en argument, dont la valeur de retour est un booléen, et l'applique à une collection.
Seuls les éléments qui renvoient true sont inclus dans la valeur de retour, qui est du même type de base que l'entrée (voir ci-dessous).
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)
Avec des tableaux multidimensionnels, filter aplatit les dimensions d'entrée et renvoie un Vector : la principale exception à toute règle sur la correspondance entre le type de sortie et le type d'entrée.
julia> m
2×3 Matrix{Int64}:
1 2 3
4 5 6
julia> filter(isodd, m)
3-element Vector{Int64}:
1
5
3
Les exemples ci-dessus utilisent des fonctions intégrées, mais l'usage de fonctions anonymes est très courant dans ce contexte.
julia> filter(x -> x % 3 == 0, 1:20)
6-element Vector{Int64}:
3
6
9
12
15
18
Il existe aussi une version en place, filter!(), comme pour beaucoup de fonctions de ce concept.
Application
La fonction map() transforme une collection en appliquant une fonction à chaque élément.
Dans les cas simples, cela peut ressembler au broadcasting, avec une forme de sortie qui correspond à celle de l'entrée.
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() peut aussi opérer élément par élément sur plusieurs collections.
julia> map(*, [1, 2], [3, 4])
2-element Vector{Int64}:
3
8
D'un point de vue conceptuel, on peut y voir l'équivalent d'un zip() sur les différentes collections d'entrée, puis d'un map() sur chaque élément du résultat intermédiaire.
Ce n'est qu'une analogie approximative, qui n'implique rien quant à l'implémentation !
Comme pour zip(), les collections dont les formes ne correspondent pas sont tronquées à la ou aux dimensions de la plus petite.
Parfois, seuls les effets de bord de la fonction passée sont nécessaires, comme une écriture dans une base de données ou un push! dans un tableau.
Dans ce cas, on dispose de la fonction d'ordre supérieur foreach(), qui renvoie toujours nothing.
Réduction
La fonction reduce() prend une fonction à deux arguments et l'applique à une collection, ce qui réduit le nombre de dimensions.
Cela peut sembler abstrait et déroutant, mais pense aux fonctions comme sum() ou prod() qui prennent une collection et renvoient une seule valeur.
julia> sum(1:4) # add
10
julia> prod(1:4) # multiply
24
Ces fonctions spéciales sont hautement optimisées et doivent toujours être utilisées lorsqu'elles sont disponibles.
On peut aussi citer maximum() et minimum(), les fonctions logiques all() et any(), et de nombreuses fonctions statistiques.
À titre d'illustration uniquement, considère la même fonctionnalité implémentée avec la fonction plus générique reduce() (rappelle-toi que les opérateurs infixes + et * sont en réalité des fonctions en interne).
julia> reduce(+, 1:4) # add
10
julia> reduce(*, 1:4) # multiply
24
Comme sum() et les autres fonctions d'agrégation, reduce() peut prendre un argument nommé facultatif dims, pour préciser la ou les dimensions à réduire.
julia> m
2×3 Matrix{Int64}:
1 2 3
4 5 6
julia> reduce(+, m; dims=1)
1×3 Matrix{Int64}:
5 7 9
Ce sont des exemples simples, car l'addition et la multiplication sont toutes deux commutatives (1+2 == 2+1) et associatives ( (1+2)+3 == 1+(2+3) ).
Cela est loin d'être universel !
Même des opérations aussi courantes que la soustraction et la division ne sont pas associatives.
S'ajoute à cela le problème que les erreurs de virgule flottante peuvent s'accumuler sur de grandes collections, si bien qu'une réduction de gauche à droite peut donner une réponse légèrement différente d'une réduction de droite à gauche.
Le sens de parcours de la fonction reduce de Julia dépend de l'implémentation et n'est pas garanti.
Pour contrôler explicitement le sens, il existe les fonctions foldl() et foldr(), qui commencent respectivement à la « gauche » et à la « droite » (en réalité en haut et en bas, pour un Vector).
julia> foldl(-, 1:3) # (1 - 2) - 3
-4
julia> foldr(-, 1:3) # 1 - (2 - 3)
2
Note que ces fonctions sont prévues pour des collections que l'on peut traiter comme unidimensionnelles, et renvoient un résultat scalaire.
L'utilisation d'un argument dims n'est pas prise en charge pour foldl et foldr, uniquement pour reduce.
MapReduce
Combiner une opération map avec un reduce est très courant dans divers domaines de la programmation.
On pourrait exécuter map de manière séquentielle, puis reduce sur une collection intermédiaire.
Cependant, c'est au mieux inefficace, et cela ne passe pas bien à l'échelle quand la collection grandit.
Il est fortement recommandé d'utiliser plutôt la fonction combinée mapreduce().
Elle peut mettre en œuvre un algorithme bien plus performant, qui entrelace les opérations map et reduce.
Le premier argument est la fonction à appliquer, le second est l'opérateur de réduction.
julia> mapreduce(x -> x^2 + 1, +, 1:3)
17
# equivalent to (2 + 5 + 10)
julia> sum(map(x -> x^2 + 1, 1:3))
17
Comme on peut s'y attendre, Julia dispose aussi des fonctions mapfoldl() et mapfoldr() pour les situations où le sens a son importance.
Exercice d'apprentissage
