Pourquoi des procédures d'ordre supérieur?

StackOverflow https://stackoverflow.com/questions/832668

Question

Donc, si une langue fournit une procédure d'ordre supérieur, alors je peux avoir une procédure qui renvoie une procédure. Quelque chose comme: 

(define (Proc a b c)
  (lambda (x) ( #| method body here in terms of a b c and x |# )))

Pour créer une nouvelle procédure, je voudrais juste faire quelque chose comme: 

(define ProcA (Proc a1 b1 c1)) ; Would create ProcA that has 1 argument

Une tâche similaire pourrait être effectuée dans un langage qui ne prend pas en charge les procédures d'ordre supérieur en définissant Proc prenant 4 arguments au lieu de 3 arguments et en appelant cette procédure pour définir ProcA . comme: 

(define (Proc a b c x) ( #| method body -- does not return any procedure |# )
(define (ProcA x) (Proc a1 b1 c1 x))

Alors pourquoi y a-t-il tant de fuzz sur la procédure d'ordre supérieur? Est-ce que je manque quelque chose?

Était-ce utile?

La solution

C'est une bonne observation qu'une fonction qui renvoie une autre fonction est identique à une fonction qui prend deux arguments. Cela s'appelle "Currying". En d'autres termes, une fonction de A à B est la preuve d'une implication logique, que A implique B, ou: 

A => B.

Comme vous le constatez, si A implique que B implique C, alors A et B implique C ou: 

(A => (B => C)) <==> ((A, B) => C)

Mais une fonction d'ordre supérieur n'est pas nécessairement une fonction qui renvoie une autre fonction. Une fonction d'ordre supérieur est une fonction qui prend pour argument une autre fonction . C'est une différence importante et les HOF sont des outils de programmation extrêmement puissants.

Par exemple, considérons cette fonction Haskell: 

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

Cette fonction d'ordre supérieur prend une fonction f et l'applique à tous les éléments d'une liste. Dans les langues sans HOF, vous feriez ce que cette fonction fait avec une boucle ou quelque chose de similaire, mais dans une langue comportant des HOF, vous pouvez appeler f pour chaque élément de la liste avec un appel simple comme celui-ci. : 

map f myList

Bien sûr, les constructions de contrôle dans les langues vous permettent d'approcher les fonctions d'ordre supérieur, mais un langage doté de fonctions d'ordre supérieur vous permet d'inventer vos propres constructions de contrôle . Le régime est certainement admissible.

Autres conseils

C’est plus une question de mentalité que de faisabilité. Il vous permet de traiter les fonctions comme des citoyens de première classe et de penser en termes de fonctions qui agissent sur des fonctions pour créer d'autres fonctions, etc.

Évidemment, vous pouvez le faire ou le simuler avec d'autres langages, mais si ce n'est pas un mécanisme syntaxique, c'est en quelque sorte traité comme un ajout ou un hack.

OK, mais dans le deuxième exemple, vous créez cette procédure à la compilation avec une liste pré-ordonnée de a1 , b1 et c1 . Dans le premier exemple, vous le créez au moment de l'exécution lorsque vous appelez ProcA . Vous pouvez en créer autant que vous le souhaitez afin de pouvoir réaliser des tâches beaucoup plus intéressantes.

Pensez à une fonction de transformation ou à un algorithme de tri via un tableau. Maintenant, vous voulez faire en sorte que l'utilisateur de votre fonction puisse spécifier le comportement de votre fonction en lui laissant passer une fonction en tant qu'argument.

Vous écrivez un algorithme de tri avec le prototype procédural suivant: 

sort(Array a, void (*fn)(a::element_type, a::element_type));

L'utilisateur de cette fonction peut spécifier, en passant le fn approprié, s'il souhaite un ordre décroissant ou croissant.

Vous auriez besoin d’une classe interne pour bien simuler cela. Le premier cas, Proc est fermé sur a, b et c. Dans le second cas, l'appelant de ProcA ne peut pas contrôler la manière dont a1, b1 et c1 sont passés à l'autre procédure, il ne peut que contrôler x. Ainsi, vous contrôlez a1, b1 et c1 en utilisant les variables d’utilisation plus étendues (niveau du module ou autre), ce qui rend votre fonction non pure. Dans ce cas, vous ne pouvez pas vous assurer que ProcA renvoie le même résultat avec les mêmes arguments d'un appel à l'autre. Où, comme avec Proc, vous pouvez toujours être sûr que si vous l'appelez avec les mêmes arguments, les mêmes résultats se produiront.

J'utilise des fonctions d'ordre supérieur en javascript, par exemple, lorsque j'utilise une zone de sélection. Je peux transmettre la fonction qui sera appelée lorsqu’une option est sélectionnée, la seule différence étant que, ce qui simplifie mon code, réduit la redondance.

Je vois la même chose dans d'autres langues que j'utilise qui prend en charge les fonctions d'ordre supérieur, car je peux alors commencer à regarder comment nettoyer mon code, où il existe une certaine redondance pouvant être localisée, et toute différence pouvant être fait dans une fonction.

Une fois que C # avait soutenu cela, je savais que c’était désormais plus courant. :)

Si une fonction accepte et / ou retourne une fonction, elle est appelée fonction d'ordre supérieur. (HOF). Pour les programmeurs inexpérimentés, issus de C, C ++ ou Java, les fonctions d'ordre supérieur paraissent magiques, mais elles sont très simples. Imaginez une fonction simple qui renvoie le résultat de 2 + 3: 

(define (foo) (+ 2 3)) ;; (foo) => 5

C’est une fonction ennuyeuse, elle ajoute toujours 2 à 3. Et si on la généralisait, elle ajoute donc 2 non seulement à 3, mais à n’importe quel numéro fourni par l’utilisateur? 

(define (foo n) (+ 2 n)) ;; (foo 10) => 12

Lorsqu'un langage ne prend pas en charge les fonctions d'ordre supérieur, vous êtes obligé de penser que les fonctions et les valeurs (par exemple, les nombres, les booléens, les listes) sont deux choses distinctes. Mais la programmation fonctionnelle (FP) estompe la distinction entre eux. Imaginons que la seule différence entre une fonction et une valeur réside dans le fait qu’une fonction peut être appelée, mais que vous pouvez modifier ce que vous pouvez avec une fonction 2 ou #t ou '(abc) : vous pouvez le donner sous forme d'argument, revenir d'une fonction, stocker dans une variable ou le placer dans une liste. Par exemple, généralisons davantage notre petite fonction afin qu'elle ne puisse pas seulement ajouter 2 à n , mais multiplier 2 par n , ou appliquer toute autre fonction acceptant deux nombres. : 

(define (foo f n) (f 2 n))
;; (foo + 10) => 12
;; (foo * 10) => 20
;; (foo expt 10) => 1024

Lorsque vous réalisez qu'une fonction peut être traitée de la même manière qu'un numéro ou une chaîne, anonymous Les fonctions (appelées "lambdas" en jargon FP) ont tout leur sens. Les fonctions anonymes sont en réalité plus élémentaires et & # 8220; normales & # 8221; que les fonctions nommées ordinaires, les fonctions nommées ne sont que des fonctions anonymes placées dans une variable, comme nous plaçons un nombre dans une variable pour l’utiliser plusieurs fois. 

(+ 2 2) ;; is no different from:
(let ((a 2)) (+ a a))
(lambda (x y) (* x y)) ;; is no different from:
(define (foo x y) (* x y)) ;; which is an abbreviation for:
(define foo (lambda (x y) (* x y))).

Ainsi, les HOF nous permettent de généraliser nos fonctions pour les rendre super flexibles. Si vous examinez votre fonction, voyez la logique qui la sous-tend, vous réaliserez que si quelque chose agit sur vos données, alors autre chose pourrait probablement aussi l'être. Si vous additionnez 2 nombres ensemble, vous pouvez probablement les multiplier, ou les soustraire, ou les exposer les uns aux autres, ou peu importe. Au lieu d'écrire une nouvelle fonction pour chaque cas à chaque fois, vous pouvez simplement accepter un paramètre supplémentaire, qui doit être une fonction.

En FP, nous utilisons tout le temps les HOF, par exemple lors de la manipulation de listes. Les 3 fonctions sont le pain du beurre de FP: map , filtre et foldl . map accepte une fonction avec 1 argument, applique cette fonction à chaque élément de la liste et renvoie une nouvelle liste avec les éléments modifiés. filter accepte un prédicat (fonction renvoyant un booléen) avec 1 argument, applique le prédicat à chaque élément d'une liste et renvoie une nouvelle liste contenant des éléments ne satisfaisant pas le prédicat supprimé. 

(map (lambda (n) (+ n 1)) '(1 2 3 4 5) ;; '(2 3 4 5 6)
(define (foo n) (+ n 1))
(map foo '(1 2 3 4 5)) ;; '(2 3 4 5 6)
(filter (lambda (n) (> n 3)) '(1 2 3 4 5)) ;; '(4 5)
(define (bar n) (> n 3))
(filter bar '(1 2 3 4 5)) ;; '(4 5)

Imaginez-vous, vous avez à nouveau une liste de fonctions à une entité, vous pouvez faire ce que vous voulez avec une fonction et la stocker dans une structure de données aussi, et vous souhaitez toutes les appliquer au même numéro et obtenir une liste des résultats. 

(let ((xs (list (lambda (x) (+ x 1))
                (lambda (x) (* x 2))
                (lambda (x) (- x)))))
  (map (lambda (f) (f 10)) xs)) ;; => (11 20 -10)

Conclusion: lorsqu'un langage de programmation prend en charge correctement les concepts de programmation fonctionnels, les fonctions d'ordre supérieur offrent souplesse et généralité, ce qui rend votre code plus puissant (vous pouvez utiliser la même fonction pour différents cas d'utilisation). ) et concis (inutile d’écrire 10 versions d’une fonction). Certaines fonctions d'ordre supérieur sont fortement utilisées dans la programmation fonctionnelle. Vous vous débarrassez donc des boucles forbalètes de niveau bas et verbeuses et écrivez des lignes uniques qui font tout à la place.

Remarque: foldl , identique à & # 8220; pli gauche & # 8221; ou & # 8220; left réduire & # 8221 ;, est encore plus puissant. Si vous êtes vraiment intéressé et que vous avez le temps, veuillez lire la première partie de ma réponse à l'aide de . Bien qu’il ne soit pas écrit pour Scheme / Racket, mais plutôt pour Common Lisp / Emacs Lisp, vous pouvez toujours comprendre l’idée qui se cache derrière fold / réduire.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top