Quelles sont les utilisations intéressantes des fonctions d'ordre supérieur?

de nombreuses techniques utilisées dans la programmation OO sont des solutions de rechange pour le manque de fonctions d'ordre supérieur.

Cela inclut un certain nombre de modèles de conception qui sont omniprésents dans la programmation fonctionnelle. Par exemple, le pattern des visiteurs est une façon assez compliquée d'implémenter un fois. La solution de contournement consiste à créer une classe avec des méthodes et passez un élément de la classe comme un argument comme un substitut pour le passage d'une fonction.

le stratégie pattern est un autre exemple de schéma qui passe souvent des objets en arguments pour remplacer ce qui est réellement prévu, des fonctions.

Même injection de dépendance implique souvent un schéma de passe-droit pour passer un proxy pour des fonctions alors qu'il serait souvent préférable de simplement passer dans les fonctions directement comme arguments.

Donc, ma réponse serait que les fonctions d'ordre supérieur sont souvent utilisés pour effectuer les mêmes types de tâches Oo programmeurs effectuer, mais directement, et avec beaucoup moins boilerplate.

j'ai vraiment commencé à ressentir le pouvoir quand j'ai appris qu'une fonction peut faire partie d'une structure de données. Voici un "Monad consommateur" (technobabble: monad libre sur (i ->)).

data Coro i a
    = Return a
    | Consume (i -> Coro i a)

Coro peut soit donner instantanément une valeur, soit être un autre Coro dépendant d'une entrée. Par exemple, c'est un Coro Int Int:

Consume $ \x -> Consume $ \y -> Consume $ \z -> Return (x+y+z)

cela consomme trois entrées entières et renvoie leur somme. Vous pouvez également le faire se comporter différemment selon le entrées:

sumStream :: Coro Int Int
sumStream = Consume (go 0)
    where
    go accum 0 = Return accum
    go accum n = Consume (\x -> go (accum+x) (n-1))

cela consomme un Int et puis consomme que beaucoup plus D'Ints avant de céder leur somme. Ceci peut être considéré comme une fonction qui prend arbitrairement beaucoup d'arguments, construits sans aucune magie de langage, juste des fonctions d'ordre supérieur.

les fonctions dans les structures de données sont un outil très puissant qui ne faisait pas partie de mon vocabulaire avant que je commence à faire Haskell.

consulter le document 'fonctions D'Ordre encore plus élevé pour L'analyse ou pourquoi Quelqu'un voudrait jamais Utiliser une fonction de sixième ordre?' par Chris Okasaki. C'est écrit avec ML, mais les idées s'appliquent également à Haskell.

Joel Spolsky a écrit un célèbre essai démontrer comment Map-Reduce fonctionne avec les fonctions D'ordre supérieur de Javascript. Une lecture incontournable pour quiconque pose cette question.

fonctions d'ordre Supérieur sont également nécessaires pour lancer, que Haskell utilise partout. Essentiellement, une fonction prenant deux arguments est équivalente à une fonction prenant un argument et retournant une autre fonction prenant un argument. Lorsque vous voyez une signature de type comme celle-ci dans Haskell:

f :: A -> B -> C

...(->) peut être lue comme droite-associative, montrant qu'il s'agit en fait d'une fonction d'ordre supérieur retournant une fonction de type B -> C:

f :: A -> (B -> C)

une fonction non-curried de deux arguments aurait à la place un type comme ceci:

f' :: (A, B) -> C

donc chaque fois que vous utilisez une application partielle dans Haskell, vous travaillez avec des fonctions d'ordre supérieur.

Martín Escardó fournit un exemple intéressant d'une fonction d'ordre supérieur:

equal :: ((Integer -> Bool) -> Int) -> ((Integer -> Bool) -> Int) -> Bool

Donné deux fonctionnelles f, g :: (Integer -> Bool) -> Int, puis equal f g décide si f et g sont (extensionally) égale ou non, même si f et g n'ont pas fini de domaine. En fait, l'arrivée, Int peut être remplacé par n'importe quel type avec un decidable l'égalité.

le code Escardó donne est écrit en Haskell, mais le même algorithme devrait fonctionner dans n'importe quel langage fonctionnel.

vous pouvez utiliser les mêmes techniques que Escardó décrit pour calculer les intégrales définies de n'importe quelle fonction continue à la précision arbitraire.

une chose intéressante et un peu folle que vous pouvez faire est simuler un système orientée objet à l'aide d'une fonction et de stockage des données en fonction de la portée (en fermeture). C'est un ordre supérieur dans le sens où la fonction de générateur d'objet est une fonction qui renvoie l'objet (une autre fonction).

mon Haskell est plutôt rouillé donc je ne peux pas facilement vous donner un exemple de Haskell, mais voici un exemple simplifié de Clojure qui, je l'espère, communique le concept:

(defn make-object [initial-value]
  (let [data (atom {:value initial-value})]
      (fn [op & args]
        (case op 
          :set (swap! data assoc :value (first args))
          :get (:value @data)))))

Utilisation:

(def a (make-object 10))

(a :get)
=> 10

(a :set 40)

(a :get)
=> 40

même principe fonctionnerait dans Haskell (sauf que vous auriez probablement besoin de changer l'opération de jeu pour retourner une nouvelle fonction puisque Haskell est purement fonctionnelle)

je suis particulièrement fan de l'ordre supérieur memoization:

memo :: HasTrie t => (t -> a) -> (t -> a)

(pour n'importe quelle fonction, retourner une version memoized de cette fonction. Limitée par le fait que les arguments de la fonction doit pouvoir être codées dans un trie.)

C'est à partir de http://hackage.haskell.org/package/MemoTrie

Il y a plusieurs exemples ici: http://www.haskell.org/haskellwiki/Higher_order_function

de plus, je recommande ce livre: http://www.cs.nott.ac.uk/~gmh/book.html qui est une excellente introduction à l'ensemble de Haskell et couvre des fonctions d'ordre supérieur.

les fonctions D'ordre supérieur utilisent souvent un accumulateur et peuvent donc être utilisées pour former une liste d'éléments qui se conforment à une règle donnée à partir d'une liste plus large.

Voici une petite paraphrasé code extrait de code:

rays :: ChessPieceType -> [[(Int, Int)]]
rays Bishop = do
  dx <- [1, -1]
  dy <- [1, -1]
  return $ iterate (addPos (dx, dy)) (dx, dy)
...  -- Other piece types

-- takeUntilIncluding is an inclusive version of takeUntil
takeUntilIncluding :: (a -> Bool) -> [a] -> [a]

possibleMoves board piece = do
  relRay <- rays (pieceType piece)
  let ray = map (addPos src) relRay
  takeUntilIncluding (not . isNothing . pieceAt board)
    (takeWhile notBlocked ray)
  where
    notBlocked pos =
      inBoard pos &&
      all isOtherSide (pieceAt board pos)
    isOtherSide = (/= pieceSide piece) . pieceSide

cela utilise plusieurs fonctions "d'ordre supérieur":

iterate :: (a -> a) -> a -> [a]
takeUntilIncluding  -- not a standard function
takeWhile :: (a -> Bool) -> [a] -> [a]
all :: (a -> Bool) -> [a] -> Bool
map :: (a -> b) -> [a] -> [b]
(.) :: (b -> c) -> (a -> b) -> a -> c
(>>=) :: Monad m => m a -> (a -> m b) -> m b

(.) est le . opérateur, et (>>=) est le do-notation "opérateur de rupture de ligne".

quand vous programmez à Haskell, vous n'avez qu'à les utiliser. Là où vous n'avez pas les fonctions d'ordre supérieur, c'est quand vous réalisez à quel point elles étaient incroyablement utiles.

voici un modèle que je n'ai vu personne d'autre mentionner encore qui m'a vraiment surpris la première fois que je l'ai appris. Envisagez un paquet de statistiques où vous avez une liste d'échantillons comme votre entrée et vous voulez calculer un tas de statistiques différentes sur eux (il ya aussi beaucoup d'autres façons de motiver cela). Le résultat est que vous avez une liste de fonctions que vous voulez exécuter. Comment voulez-vous exécuter?

statFuncs :: [ [Double] -> Double ]
statFuncs = [minimum, maximum, mean, median, mode, stddev]

runWith funcs samples = map ($samples) funcs

Il y a toutes sortes d'ordre supérieur la bonté continue ici, dont certaines ont été mentionnées dans d'autres réponses. Mais je tiens à souligner la fonction"$". Quand j'ai vu cette utilisation de"$", j'ai été époustouflé. Avant cela, je ne l'avais pas considéré comme très utile autre que comme un remplacement commode pour les parenthèses...mais c'était presque magique...

Une chose qui est amusant, si pas particulièrement pratique, est Chiffres De L'Église. C'est une façon de représenter des entiers en n'utilisant que des fonctions. Fou, je sais. < shamelessPlug>voici un implémentation en JavaScript que j'ai fait. Cela pourrait être plus facile à comprendre qu'une mise en œuvre Lisp/Haskell. (Mais non, sans doute, pour être honnête. JavaScript n'était pas vraiment fait pour ce genre de choses.) < / shamelessPlug>

il a été mentionné que Javascript supporte certaines fonctions d'ordre supérieur, y compris un essai de Joel Spolsky. Mark Jason Dominus a écrit un livre entier intitulé Perl D'Ordre Supérieur; le livre de la source est disponible en téléchargement gratuit dans une grande variété de formats, include PDF.

depuis au moins Perl 3, Perl a pris en charge des fonctionnalités plus réminiscentes de Lisp que de C, mais ce N'était pas avant Perl 5 ce soutien total aux fermetures et tout ce qui en découle était disponible. Et ne des premières implémentations de Perl 6 a été écrit dans Haskell, qui a eu beaucoup d'influence sur la façon dont la conception de ce langage a progressé.

des exemples d'approches de programmation fonctionnelle en Perl apparaissent dans la programmation quotidienne, en particulier avec map et grep:

@ARGV    = map { /\.gz$/ ? "gzip -dc < $_ |" : $_ } @ARGV;

@unempty = grep { defined && length } @many;

Depuis sort admet également une fermeture, le map/sort/map le motif est super fréquent:

@txtfiles = map { $_->[1] }
            sort { 
                    $b->[0]  <=>     $a->[0]
                              ||
                 lc $a->[1]  cmp  lc $b->[1]
                              ||
                    $b->[1]  cmp     $a->[1]
            }
            map  { -s => $_ } 
            grep { -f && -T }
            glob("/etc/*");

ou

@sorted_lines = map { $_->[0] }
                sort {
                     $a->[4] <=> $b->[4] 
                             ||
                    $a->[-1] cmp $b->[-1]
                             ||
                     $a->[3] <=> $b->[3]
                             ||
                     ...
                }
                map { [$_ => reverse split /:/] } @lines;

reduce la fonction rend la liste hackery facile sans boucle:

$sum = reduce { $a + $b } @numbers;

$max = reduce { $a > $b ? $a : $b } $MININT, @numbers;

il y a bien plus que cela, mais ce n'est qu'un avant-goût. Les fermetures facilitent la création de générateurs de fonctions, en écrivant vos propres fonctions d'ordre supérieur, et pas seulement en utilisant les builtins. En fait, l'un des modèles d'exception les plus courants,

try {
   something();
} catch {
   oh_drat();
};

construit. Elle est toutefois définie de façon presque insignifiante. try avoir une fonction qui prend deux arguments: une fermeture dans le premier arg et une fonction qui prend une fermeture dans le second.

Perl 5 n'a pas de currying intégré, bien qu'il y ait un module pour cela. Perl 6, cependant, a currying et les continuations de première classe intégrés à droite dans elle, plus beaucoup plus.