Expressions de cas et correspondance de modèles

Nous avons donné précédemment plusieurs exemples de correspondance de motifs dans la définition de fonctions, par exemple length et fringe. Dans cette page, nous examinerons le processus de correspondance de motifs plus en détail. (La correspondance de motifs dans Haskell est différente de celle que l'on trouve dans les langages de programmation logique tels que Prolog ; en particulier, elle peut être considérée comme une correspondance «unidirectionnelle», alors que Prolog permet une correspondance «bidirectionnelle» (via l'unification), ainsi qu'un retour en arrière implicite dans son mécanisme d'évaluation.)

Les motifs ne sont pas «de première classe» ; il n'existe qu'un ensemble fixe de différents types de motifs. Nous avons déjà vu plusieurs exemples de motifs de constructeur de données; length et fringe définis précédemment utilisent tous deux de tels motifs, le premier sur les constructeurs d'un type «intégré» (listes), le second sur un type défini par l'utilisateur (Tree). En effet, la correspondance est autorisée en utilisant les constructeurs de tout type, défini par l'utilisateur ou non. Cela inclut les tuples, les chaînes, les nombres, les caractères,... Par exemple, voici une fonction artificielle qui correspond à un tuple de «constantes» :

Cet exemple démontre également que l'imbrication de modèles est autorisée (à une profondeur arbitraire).

Techniquement parlant, les paramètres formels (le rapport appelle ces variables) sont également des modèles --- c'est juste qu'ils ne manquent jamais de correspondre à une valeur. En tant qu'«effet secondaire» de la correspondance réussie, le paramètre formel est lié à la valeur à laquelle il est comparé. Pour cette raison, les modèles dans une équation ne sont pas autorisés à avoir plus d'une occurrence du même paramètre formel.

Les modèles tels que les paramètres formels ne manquant jamais de correspondre sont dits irréfutables, contrairement aux modèles réfutables pouvant ne pas correspondre. Le modèle utilisé dans l'exemple artificiel ci-dessus est réfutable. Il existe trois autres types de modèles irréfutables, dont deux que nous allons présenter maintenant.

Modèles As

Parfois, il est pratique de nommer un modèle à utiliser sur le côté droit d'une équation. Par exemple, une fonction dupliquant le premier élément d'une liste pourrait s'écrire comme suit :

(Rappelez-vous que ":" s'associe à droite.) Notez que x:xs apparaît à la fois comme un motif sur le côté gauche et comme une expression sur le côté droit. Pour améliorer la lisibilité, nous préférerions peut-être écrire x:xs une seule fois, ce que nous pouvons réaliser en utilisant un modèle as comme suit : (Un autre avantage de cette méthode est qu'une implémentation naïve pourrait reconstruire complètement x:xs plutôt que de réutiliser la valeur à laquelle la correspondance est faite.)

Techniquement parlant, les modèles as-patterns aboutissent toujours à une correspondance réussie, bien que le sous-modèle (dans ce cas x:xs) puisse, bien sûr, échouer.

Caractères génériques

Une autre situation courante est la correspondance avec une valeur dont nous ne nous soucions pas vraiment. Par exemple, les fonctions head et tail définies dans la page Valeurs, types et autres avantages peuvent être réécrites comme suit :

dans lequel nous avons «annoncé» le fait que nous ne nous soucions pas de ce qu'est une certaine partie de l'entrée. Chaque caractère générique correspond indépendamment à n'importe quoi, mais contrairement à un paramètre formel, chacun ne lie rien ; pour cette raison, plus d'un est autorisé dans une équation.

Sémantique de la correspondance de motifs

Jusqu'à présent, nous avons discuté de la manière dont les motifs individuels sont mis en correspondance, de la manière dont certains sont réfutables, d'autres irréfutables,... Mais qu'est-ce qui motive le processus global ? Dans quel ordre les correspondances sont-elles tentées ? Que se passe-t-il si aucune ne réussit ? Cette section aborde ces questions.

La correspondance de motifs peut échouer, réussir ou diverger. Une correspondance réussie lie les paramètres formels dans le motif. La divergence se produit lorsqu'une valeur requise par le motif contient une erreur (_|_). Le processus de correspondance lui-même se produit « de haut en bas, de gauche à droite ». L'échec d'un motif n'importe où dans une équation entraîne l'échec de l'équation entière, et l'équation suivante est alors essayée. Si toutes les équations échouent, la valeur de l'application de fonction est _|_ et entraîne une erreur d'exécution.

Par exemple, si [1,2] est mis en correspondance avec [0,bot], alors 1 ne parvient pas à correspondre à 0, donc le résultat est une correspondance ratée. (Rappelons que bot, défini précédemment, est une variable liée à _|_.) Mais si [1,2] est mis en correspondance avec [bot,0], alors la mise en correspondance de 1 avec bot provoque une divergence (c'est-à-dire _|_).

L'autre particularité de cet ensemble de règles est que les modèles de niveau supérieur peuvent également avoir une protection booléenne, comme dans cette définition d'une fonction formant une version abstraite du signe d'un nombre :

Notez qu'une séquence de gardes peut être fournie pour le même motif ; comme pour les motifs, ils sont évalués de haut en bas, et le premier étant évalué à True donne une correspondance réussie.

Un exemple

Les règles de correspondance de motifs peuvent avoir des effets subtils sur la signification des fonctions. Par exemple, considérons cette définition de take :

et cette version légèrement différente (les 2 premières équations ont été inversées) :

Notez maintenant ce qui suit :

Nous voyons que take est «plus défini» par rapport à son deuxième paramètre, alors que take1 est plus défini par rapport à son premier. Il est difficile de dire dans ce cas quelle définition est la meilleure. Rappelez-vous simplement que dans certaines applications, cela peut faire une différence. (Le prélude standard inclut une définition correspondant à take.)

Expressions de cas

La correspondance de motifs fournit un moyen de «répartir le contrôle» en fonction des propriétés structurelles d'une valeur. Dans de nombreuses circonstances, nous ne souhaitons pas définir une fonction à chaque fois que nous devons le faire, mais jusqu'à présent, nous avons seulement montré comment effectuer une correspondance de motifs dans les définitions de fonctions. L'expression de cas de Haskell fournit un moyen de résoudre ce problème.

En effet, la signification de la correspondance de motifs dans les définitions de fonctions est précisée dans le rapport en termes d'expressions de cas, qui sont considérées comme plus primitives. En particulier, une définition de fonction de la forme :

où chaque pij est un motif, est sémantiquement équivalent à :

où les xi sont de nouveaux identifiants. Par exemple, la définition de take donnée précédemment est équivalente à :

Un point n'ayant pas été mentionné plus tôt est que, pour la correction de type, les types des membres droits d'une expression de cas ou d'un ensemble d'équations comprenant une définition de fonction doivent tous être identiques ; plus précisément, ils doivent tous partager un type principal commun.

Les règles de correspondance de motifs pour les expressions de cas sont les mêmes que celles que nous avons données pour les définitions de fonction, il n'y a donc vraiment rien de nouveau à apprendre ici, à part noter la commodité que les expressions de cas offrent. En effet, il existe une utilisation d'une expression de cas étant si courante qu'elle a une syntaxe spéciale : l'expression conditionnelle. En Haskell, les expressions conditionnelles ont la forme familière :

ce qui est en réalité une abréviation de :

De cette extension, il devrait être clair que e1 doit avoir le type Bool, et e2 et e3 doivent avoir le même type (mais sinon arbitraire). En d'autres termes, if-then-else lorsqu'il est vu comme une fonction a le type Bool->a->a->a.

Motifs paresseux

Il existe un autre type de motif autorisé dans Haskell. Il s'appelle un motif paresseux et a la forme ~pat. Les motifs paresseux sont irréfutables : la correspondance d'une valeur v avec ~pat réussit toujours, indépendamment de pat. D'un point de vue opérationnel, si un identifiant dans pat est ensuite "utilisé" sur le côté droit, il sera lié à la partie de la valeur résultant si v devait correspondre avec succès à pat, et _|_ sinon.

Les motifs paresseux sont utiles dans les contextes où des structures de données infinies sont définies de manière récursive. Par exemple, les listes infinies sont un excellent véhicule pour écrire des programmes de simulation et, dans ce contexte, les listes infinies sont souvent appelées flux de données. Considérons le cas simple de la simulation des interactions entre un processus serveur et un processus client, où le client envoie une séquence de requêtes au serveur et le serveur répond à chaque requête par une sorte de réponse. Cette situation est illustrée par une image suivante (Notez que le client prend également un message initial comme paramètre) :

En utilisant des flux pour simuler les séquences de messages, le code Haskell correspondant à ce diagramme est :

Ces équations récursives sont une translittération lexicale directe du diagramme.

Supposons en outre que la structure du serveur et du client ressemble à ceci :

où nous supposons que next est une fonction qui, à partir d'une réponse du serveur, détermine la requête suivante, et process est une fonction traitant une requête du client, renvoyant une réponse appropriée.

Malheureusement, ce programme a un sérieux problème : il ne produira aucune sortie ! Le problème est que client, tel qu'il est utilisé dans le cadre récursif de reqs et resps, tente une correspondance sur la liste de réponses avant d'avoir soumis sa première requête ! En d'autres termes, la correspondance de motifs est effectuée «trop tôt». Une façon de résoudre ce problème est de redéfinir client comme suit :

Bien que réalisable, cette solution n'est pas aussi lisible que celle donnée précédemment. Une meilleure solution consiste à utiliser un modèle paresseux :

Les modèles paresseux étant irréfutables, la correspondance réussira immédiatement, permettant à la requête initiale d'être «soumise», ce qui permettra à son tour de générer la première réponse ; le moteur est maintenant «amorcé» et la récursivité s'occupe du reste.

À titre d'exemple de ce programme en action, si nous définissons :

alors on voit que :

Comme autre exemple de l'utilisation de modèles paresseux, considérons la définition de Fibonacci donnée précédemment :

Nous pourrions essayer de réécrire ceci en utilisant un modèle as :

Cette version de fib a le (petit) avantage de ne pas utiliser tail sur le côté droit, puisqu'elle est disponible sous forme "déstructurée" sur le côté gauche sous le nom de tfib.

[Ce type d'équation est appelé une liaison de motif car il s'agit d'une équation de niveau supérieur dans laquelle tout le côté gauche est un motif ; c'est-à-dire que fib et tfib deviennent liés dans le cadre de la déclaration.]

Maintenant, en utilisant le même raisonnement que précédemment, nous devrions être amenés à croire que ce programme ne générera aucune sortie. Curieusement, cependant, c'est le cas, et la raison est simple : en Haskell, les liaisons de motif sont supposées avoir un ~ implicite devant elles, reflétant le comportement le plus courant attendu des liaisons de motif, et évitant certaines situations anormales qui dépassent le cadre de ce tutoriel. Ainsi, nous voyons que les motifs paresseux jouent un rôle important dans Haskell, ne serait-ce que de manière implicite.

Portée lexicale et formes imbriquées

Il est souvent souhaitable de créer une portée imbriquée dans une expression, dans le but de créer des liaisons locales non vues ailleurs, c'est-à-dire une sorte de forme de «structuration en blocs». En Haskell, il existe deux façons d'y parvenir :

Expressions Let

Les expressions let de Haskell sont utiles chaque fois qu'un ensemble imbriqué de liaisons est requis. À titre d'exemple simple, considérons :

L'ensemble des liaisons créées par une expression let est mutuellement récursif et les liaisons de motifs sont traitées comme des motifs paresseux (c'est-à-dire qu'elles comportent un ~ implicite). Les seuls types de déclarations autorisés sont les signatures de type, les liaisons de fonction et les liaisons de motifs.

Clauses Where

Il est parfois pratique de définir la portée des liaisons sur plusieurs équations protégées, ce qui nécessite une clause where :

Notez que cela ne peut pas être fait avec une expression let, ne s'étendant qu'à l'expression qu'elle entoure. Une clause where n'est autorisée qu'au niveau supérieur d'un ensemble d'équations ou d'une expression case. Les mêmes propriétés et contraintes sur les liaisons dans les expressions let s'appliquent à celles des clauses where.

Ces deux formes de portée imbriquée semblent très similaires, mais rappelez-vous qu'une expression let est une expression, alors qu'une clause where ne l'est pas - elle fait partie de la syntaxe des déclarations de fonction et des expressions case.

Disposition

Le lecteur s'est peut-être demandé comment il se fait que les programmes Haskell évitent l'utilisation de points-virgules, ou d'un autre type de terminateur, pour marquer la fin des équations, des déclarations,... Par exemple, considérez cette expression let de la section précédente :

Comment l'analyseur sait-il qu'il ne doit pas analyser ceci comme :

La réponse est que Haskell utilise une syntaxe bidimensionnelle appelée layout reposant essentiellement sur des déclarations «alignées en colonnes». Dans l'exemple ci-dessus, notez que y et f commencent dans la même colonne. Les règles de layout sont expliquées en détail dans le rapport, mais en pratique, l'utilisation de layout est plutôt intuitive. Rappelez-vous simplement deux choses :

• Premièrement, le caractère suivant l'un des mots-clefs where, let ou of détermine la colonne de départ pour les déclarations dans l'expression where, let ou case en cours d'écriture. Ainsi, nous pouvons commencer les déclarations sur la même ligne que le mot-clef, la ligne suivante,... (Le mot-clef do, étant abordé plus tard, utilise également layout).
• Deuxièmement, assurez-vous simplement que la colonne de départ est plus à droite que la colonne de départ associée à la clause immédiatement environnante (sinon, elle serait ambiguë). La «fin» d'une déclaration se produit lorsque quelque chose apparaît à gauche ou à la hauteur de la colonne de départ associée à cette forme de liaison. (Haskell respecte la convention selon laquelle les tabulations comptent pour 8 espaces ; il faut donc faire attention lors de l'utilisation d'un éditeur pouvant respecter une autre convention.)

Layout est en fait un raccourci pour un mécanisme de regroupement explicite, méritant d'être mentionné car il peut être utile dans certaines circonstances. L'exemple let ci-dessus est équivalent à :

Notez les accolades et les points-virgules explicites. Cette notation explicite est particulièrement utile lorsque plusieurs déclarations sont souhaitées sur une ligne. Par exemple, voici une expression valide :

Pour un autre exemple de l'extension de layout en délimiteurs explicites.

L'utilisation de layout réduit considérablement l'encombrement syntaxique associé aux listes de déclarations, améliorant ainsi la lisibilité. Il est facile à apprendre et son utilisation est encouragée.