Les fonctions

Le Haskell étant un langage fonctionnel, on pourrait s'attendre à ce que les fonctions jouent un rôle majeur, et c'est effectivement le cas. Dans cette page, nous examinons plusieurs aspects des fonctions dans Haskell.

Premièrement, considérons cette définition d'une fonction additionnant ses deux paramètres :

Voici un exemple de fonction curry. (Le nom curry vient de la personne ayant popularisé l'idée : Haskell Curry. Pour obtenir l'effet d'une fonction non curry, nous pourrions utiliser un tuple, comme dans :

Mais nous voyons alors que cette version de add n'est en réalité qu'une fonction d'un seul paramètre !) Une application de add a la forme add e1 e2, et est équivalente à (add e1) e2, puisque la fonction application s'associe à gauche. En d'autres termes, l'application de add à un paramètre produit une nouvelle fonction étant ensuite appliquée au second paramètre. Ceci est cohérent avec le type de add, Integer->Integer->Integer, étant équivalent à Integer->(Integer->Integer); c'est-à-dire -> s'associe à droite. En effet, en utilisant add, nous pouvons définir inc d'une manière différente de précédemment :

Il s'agit d'un exemple d'application partielle d'une fonction curryfiée, et d'une façon de renvoyer une fonction sous forme de valeur. Considérons un cas dans lequel il est utile de passer une fonction en tant que paramètre. La fonction map bien connue en est un parfait exemple :

[L'application de fonction a une priorité plus élevée que n'importe quel opérateur infixe, et donc le côté droit de la seconde équation s'analyse comme (f x) : (map f xs).] La fonction map est polymorphe et son type indique clairement que son premier paramètre est une fonction ; notez également que les deux a doivent être instanciés avec le même type (de même pour les b). Comme exemple d'utilisation de map, nous pouvons incrémenter les éléments d'une liste :

Ces exemples démontrent la nature de première classe des fonctions, qui lorsqu'elles sont utilisées de cette manière sont généralement appelées fonctions d'ordre supérieur.

Abstractions lambda

Au lieu d'utiliser des équations pour définir des fonctions, nous pouvons également les définir «anonymement» via une abstraction lambda. Par exemple, une fonction équivalente à inc pourrait s'écrire comme \x -> x+1. De même, la fonction add est équivalente à \x -> \y -> x+y. Les abstractions lambda imbriquées telles que celle-ci peuvent être écrites en utilisant la notation abrégée équivalente \x y -> x+y. En fait, les équations :

sont en réalité des raccourcis pour :

Nous reviendrons plus loin sur ces équivalences.

En général, étant donné que x est de type t1 et exp de type t2, alors \x->exp est de type t1->t2.

Opérateurs infixes

Les opérateurs infixes ne sont en réalité que des fonctions et peuvent également être définis à l'aide d'équations. Par exemple, voici une définition d'un opérateur de concaténation de liste :

[D'un point de vue lexical, les opérateurs infixes sont entièrement constitués de «symboles», contrairement aux identifiants normaux étant alphanumériques. Le Haskell n'a pas d'opérateurs préfixes, à l'exception du moins (-), qui est à la fois infixe et préfixe.]

Autre exemple, un opérateur infixe important sur les fonctions est celui de la composition de fonctions :

Sections

Les opérateurs infixes étant en réalité de simples fonctions, il est logique de pouvoir également les appliquer partiellement. En Haskell, l'application partielle d'un opérateur infixe est appelée une section. Par exemple :

[Les parenthèses sont obligatoires.]

La dernière forme de section donnée ci-dessus contraint essentiellement un opérateur infixe à une valeur fonctionnelle équivalente, et est pratique pour passer un opérateur infixe comme argument à une fonction, comme dans map (+) [1,2,3] (le lecteur doit vérifier que cela renvoie une liste de fonctions !). Elle est également nécessaire pour donner une signature de type de fonction, comme dans les exemples de (++) et (.) donnés précédemment.

Nous pouvons maintenant voir que add défini précédemment est juste (+), et inc est juste (+1) ! En effet, ces définitions feraient très bien l'affaire :

Nous pouvons contraindre un opérateur infixe à devenir une valeur fonctionnelle, mais pouvons-nous faire l'inverse ? Oui, nous enfermons simplement un identifiant lié à une valeur fonctionnelle entre guillemets inversés. Par exemple, x `add` y est identique à add x y. (Notez bien que add est entouré de guillemets inversés, et non d'apostrophes comme dans la syntaxe des caractères ; par exemple, 'f' est un caractère, alors que `f` est un opérateur infixe. Certaines fonctions se lisent mieux de cette façon. Un exemple est le prédicat d'appartenance à une liste prédéfinie elem ; l'expression x `elem` xs peut être lue intuitivement comme "x est un élément de xs".

[Il existe quelques règles spéciales concernant les sections impliquant l'opérateur préfixe/infixe.]

A ce stade, le lecteur peut être confus d'avoir autant de façons de définir une fonction ! La décision de fournir ces mécanismes reflète en partie les conventions historiques et en partie le désir de cohérence (par exemple, dans le traitement des fonctions infixes par rapport aux fonctions régulières).

Déclarations de fixité

Une déclaration de fixité peut être donnée pour tout opérateur ou constructeur infixe (y compris ceux créés à partir d'identifiants ordinaires, tels que «elem»). Cette déclaration spécifie un niveau de priorité de 0 à 9 (9 étant le plus fort ; une application normale est supposée avoir un niveau de priorité de 10), et une associativité à gauche, à droite ou non. Par exemple, les déclarations de fixité pour ++ et . sont :

Ces deux règles spécifient l'associativité à droite, la première avec un niveau de priorité de 5, l'autre de 9. L'associativité à gauche est spécifiée via infixl, et la non-associativité par infix. De plus, la fixité de plusieurs opérateurs peut être spécifiée avec la même déclaration de fixité. Si aucune déclaration de fixité n'est donnée pour un opérateur particulier, la valeur par défaut est infixl 9.

Les fonctions ne sont pas strictes

Supposons que bot soit défini par :

En d'autres termes, bot est une expression non terminale. De manière abstraite, nous désignons la valeur d'une expression non terminale par _|_ (lire "bottom"). Les expressions aboutissant à une sorte d'erreur d'exécution, telle que 1/0, ont également cette valeur. Une telle erreur n'est pas récupérable : les programmes ne continueront pas au-delà de ces erreurs. Les erreurs rencontrées par le système d'entrées/sorties, telles qu'une erreur de fin de fichier, sont récupérables et sont traitées d'une manière différente. (Une telle erreur d'entrées/sorties n'est en réalité pas une erreur du tout, mais plutôt une exception.

Une fonction f est dite stricte si, lorsqu'elle est appliquée à une expression non terminale, elle ne parvient pas non plus à se terminer. En d'autres termes, f est stricte ssi la valeur de f bot est _|_. Pour la plupart des langages de programmation, toutes les fonctions sont strictes. Mais ce n'est pas le cas en Haskell. Comme exemple simple, considérons const1, la fonction constante 1, définie par :

La valeur de const1 bot en Haskell est 1. D'un point de vue opérationnel, puisque const1 n'a pas «besoin» de la valeur de son paramètre, il ne tente jamais de l'évaluer et ne se retrouve donc jamais pris dans un calcul non final. Pour cette raison, les fonctions non strictes sont également appelées «fonctions paresseuses» et sont censées évaluer leurs arguments «paresseusement» ou «par nécessité».

Étant donné que les valeurs d'erreur et non finales sont sémantiquement les mêmes en Haskell, le paramètre ci-dessus est également valable pour les erreurs. Par exemple, const1 (1/0) s'évalue également correctement à 1.

Les fonctions non strictes sont extrêmement utiles dans divers contextes. Le principal avantage est qu'elles libèrent le programmeur de nombreuses préoccupations concernant l'ordre d'évaluation. Des valeurs coûteuses en calcul peuvent être passées en tant que paramètres aux fonctions sans craindre qu'elles soient calculées si elles ne sont pas nécessaires. Un exemple important de cela est une structure de données potentiellement infinie.

Une autre façon d'expliquer les fonctions non strictes est que Haskell calcule en utilisant des définitions plutôt que les affectations trouvées dans les langages traditionnels. Lisez une déclaration telle que :

comme `define v as 1/0' au lieu de `compute 1/0 and store the result in v'. L'erreur de division par zéro ne se produit que si la valeur (définition) de v est nécessaire. En soi, cette déclaration n'implique aucun calcul. La programmation utilisant des affectations nécessite une attention particulière à l'ordre des affectations : la signification du programme dépend de l'ordre dans lequel les affectations sont exécutées. Les définitions, en revanche, sont beaucoup plus simples : elles peuvent être présentées dans n'importe quel ordre sans affecter la signification du programme.

Structures de données «infinies»

L'un des avantages de la nature non stricte de Haskell est que les constructeurs de données ne sont pas non plus stricts. Cela ne devrait pas être surprenant, car les constructeurs ne sont en réalité qu'un type particulier de fonction (la caractéristique distinctive étant qu'ils peuvent être utilisés dans la recherche de motifs). Par exemple, le constructeur des listes, (:), n'est pas strict.

Les constructeurs non stricts permettent la définition de structures de données (conceptuellement) infinies. Voici une liste infinie de uns :

La fonction numsFrom est peut-être plus intéressante :

Ainsi numsFrom n est la liste infinie des entiers successifs commençant par n. À partir de là, nous pouvons construire une liste infinie de carrés :

(Notez l'utilisation d'une section ; ^ est l'opérateur d'exponentiation infixe.)

Bien sûr, nous nous attendons éventuellement à extraire une partie finie de la liste pour le calcul réel, et il existe de nombreuses fonctions prédéfinies dans Haskell faisant ce genre de choses : take, takeWhile, filter, et d'autres. La définition de Haskell comprend un large ensemble de fonctions et de types intégrés --- c'est ce qu'on appelle le «prélude standard». Par exemple, take supprime les n premiers éléments d'une liste :

La définition de ones ci-dessus est un exemple de liste circulaire. Dans la plupart des cas, la paresse a un impact important sur l'efficacité, car on peut s'attendre à ce qu'une implémentation implémente la liste comme une véritable structure circulaire, économisant ainsi de l'espace.

Pour un autre exemple d'utilisation de la circularité, la séquence de Fibonacci peut être calculée efficacement comme la séquence infinie suivante :

où zip est une fonction Prelude standard renvoyant l'entrelacement par paires de ses deux paramètres de liste :

Notez comment fib, une liste infinie, est définie en termes d'elle-même, comme si elle «poursuivait sa queue».

La fonction Error

Le Haskell possède une fonction intégrée appelée error dont le type est String->a. C'est une fonction quelque peu étrange : d'après son type, elle semble renvoyer une valeur d'un type polymorphe dont elle ne sait rien, puisqu'elle ne reçoit jamais de valeur de ce type en paramètre !

En fait, il existe une valeur «partagée» par tous les types : _|_. En effet, sémantiquement, c'est exactement la valeur étant toujours renvoyée par error (rappelons que toutes les erreurs ont la valeur _|_). Cependant, nous pouvons nous attendre à ce qu'une implémentation raisonnable affiche le paramètre string de error à des fins de diagnostic. Ainsi, cette fonction est utile lorsque nous souhaitons terminer un programme lorsque quelque chose «s'est mal passé». Par exemple, la définition réelle de head tirée du Standard Prelude est :