4 votes

Une fonction Haskell est d'ordre supérieur si et seulement si son type possède plus d'une flèche ?

Un professeur enseignant un cours auquel je participe a déclaré ce qui suit.

Une fonction d'ordre supérieur ne peut avoir qu'une seule flèche lors de la vérification de son type.

Je ne suis pas d'accord avec cette déclaration, j'ai essayé de prouver qu'elle est fausse. J'ai essayé de mettre en place des fonctions mais j'ai découvert que mes fonctions ne sont probablement pas des fonctions d'ordre supérieur. Voici ce que j'ai :

f x y z = x + y + z
f :: a -> a->  a -> a

g = f 3
g :: a -> a -> a

h = g 5
h :: a -> a

En fin de compte, je pense que ma preuve était fausse, mais je ne suis toujours pas convaincu que les fonctions d'ordre supérieur ne peuvent avoir qu'une seule flèche lors de la vérification du type.

Alors, existe-t-il une ressource ou peut-être quelqu'un pourrait-il prouver que les fonctions d'ordre supérieur ne peuvent avoir qu'une seule flèche ?

5voto

Robin Zigmond Points 14030

A proprement parler, l'affirmation est correcte. En effet, la définition habituelle du terme "fonction d'ordre supérieur", tirée ici de Wikipedia est une fonction qui effectue l'une ou les deux choses suivantes :

  • prend une fonction comme argument, ou
  • renvoie une fonction comme résultat

Il est donc clair qu'aucune fonction avec une seule flèche dans sa signature de type ne peut être une fonction d'ordre supérieur, car dans une signature a -> b il n'y a pas de "place" pour créer quelque chose de cette forme. x -> y de chaque côté d'une flèche - il n'y a tout simplement pas assez de flèches.

(Cet argument comporte en fait une faille importante, que vous avez peut-être repérée, et que j'aborderai ci-dessous. Mais il est probablement vrai "dans l'esprit" pour ce que votre professeur voulait dire).

L'inverse est aussi, à proprement parler, vrai en Haskell - mais pas dans la plupart des autres langages. La caractéristique distinctive de Haskell ici est que les fonctions sont curry . Par exemple, une fonction comme (+) dont la signature est :

a -> a -> a

(avec un Num a que j'ignorerai parce qu'elle pourrait simplement embrouiller la question si nous sommes censés compter les "flèches"), est généralement considérée comme une fonction de deux arguments : elle prend 2 a et produit un autre a . Dans la plupart des langages, qui ont bien sûr tous une fonction/opérateur analogue, cela ne serait jamais décrit comme une fonction d'ordre supérieur. Mais en Haskell, comme les fonctions sont curées, la signature ci-dessus n'est qu'un raccourci pour la version entre parenthèses :

a -> (a -> a)

qui clairement est une fonction d'ordre supérieur. Elle prend un a et produit une fonction de type a -> a . (Rappelez-vous, d'après ce qui précède, que renvoyer une fonction est l'une des choses qui caractérisent un HOF). En Haskell, comme je l'ai dit, ces deux signatures sont une seule et même chose. (+) vraiment est une fonction d'ordre supérieur - souvent, nous ne le remarquons pas parce que nous avons l'intention de lui fournir deux arguments, ce qui signifie en réalité lui fournir un argument, obtenir une fonction, puis lui fournir un argument. que le deuxième argument. Grâce à la syntaxe pratique de Haskell, sans parenthèses, pour appliquer des fonctions aux arguments, il n'y a pas vraiment de distinction. (Ceci contraste encore une fois avec les langages non fonctionnels : l'ajout d'une "fonction" prend toujours exactement 2 arguments, et ne lui en donner qu'un seul sera généralement une erreur. Si le langage possède des fonctions de première classe, vous pouvez effectivement définir la forme curée, par exemple ceci en Python :

def curried_add(x):
    return lambda y: x + y

mais il s'agit clairement d'une fonction différente de la fonction simple à deux arguments que vous utiliseriez normalement, et généralement moins pratique à utiliser car vous devez l'appeler en tant que curried_add(x)(y) plutôt que de dire simplement add(x,y) .

Donc, si on prend en compte le curry, la déclaration de votre professeur est strictement vraie.

Eh bien, à l'exception suivante, à laquelle j'ai fait allusion ci-dessus. J'ai supposé que quelque chose avec une signature de la forme

a -> b

n'est pas une HOF*. Bien sûr, cela ne s'applique pas si a o b est une fonction. Souvent, le type de cette fonction comprendra une flèche, et nous supposons tacitement ici que ni l'une ni l'autre de ces fonctions n'a de sens. a o b contient des flèches. Eh bien, Haskell a des synonymes de type, donc nous pourrions facilement définir, disons :

type MyFunctionType = Int -> Int

et ensuite une fonction avec la signature MyFunctionType -> a o a -> MyFunctionType est très certainement une HOF, même s'il n'en a pas "l'air" à la vue de la signature.

*Pour être clair ici, a y b se réfèrent à des types spécifiques qui ne sont pas encore spécifiés - je ne me réfère pas à une signature réelle a -> b ce qui signifie une fonction polymorphe qui s'applique à tout types a y b qui ne seraient pas nécessairement des fonctions.

1voto

CommuSoft Points 6439

Vos fonctions sont d'ordre supérieur. En effet, prenez par exemple votre fonction :

f :: a -> a -> a -> a
f x y z = x + y + z

C'est une forme moins verbeuse de :

f :: a -> (a -> (a -> a))

Il s'agit donc d'une fonction qui prend un a y renvoie une fonction . Une fonction d'ordre supérieur est une fonction qui (a) prend une fonction comme paramètre, ou (b) renvoie une fonction. Les deux peuvent être vraies en même temps. Ici, votre fonction f renvoie une fonction.

Une fonction a donc toujours le type a -> b con a le type d'entrée, et b le type de retour. Dans le cas a a une flèche (comme (c -> d) -> b ), alors il s'agit d'une fonction d'ordre supérieur, puisqu'elle prend une fonction comme paramètre.

Si b a une flèche, comme a -> (c -> d) alors il s'agit également d'une fonction d'ordre supérieur, puisqu'elle renvoie une fonction.

1voto

Damian Lattenero Points 8950

Oui, comme les fonctions Haskell sont toujours curées, je peux proposer des exemples minimaux de fonctions d'ordre supérieur et des exemples :

1) Les fonctions qui prennent une fonction au moins comme paramètre, telles que :

apply :: (a -> b) -> a -> b
apply f x = f x

2) au moins 3 arguments :

sum3 :: Int -> Int -> Int
sum3 a b c = a + b + c

donc ça peut être lu comme :

sum3 :: Int -> (Int -> Int)

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X