Langues de programmation
Fernando López Ostenenero et Ana García Serrano
Le concours bien connu « Figures and Lyrics » propose deux types de tests à ses participants: l’une des figures dans lesquelles ils devraient être approchés autant que possible sur une composition de base du numéro cible sur un certain nombre de chiffres et un test de lettres, où ils doivent trouver lapalabra ( valide) plus longtemps qu’il est possible d’écrire avec une série de lettres.
Dans cette pratique, nous allons créer un programme qui résoudra la seconde de ces tests. Le programme recevra une série de lettres et retournera Tous les mots valides sont construits avec eux. Pour vérifier si un mot est valide ou non, il est essentiel d’utiliser un dictionnaire.
Pour ce faire, un fichier sera fourni avec le dictionnaire 79517 motsPene au dictionnaire. de la rae afin que les étudiants puissent Testez votre programme. Par lavage des problèmes dues au codage de caractères, tous les mots ont été supprimés et les accents graphiques ont été supprimés.
Ainsi, la pratique sera divisée en deux phases différentes:
- Création du dictionnaire: Un fichier texte contenant les mots que nous allons envisager de prendre en compte valide (un mot par ligne) sera inséré et que chacun d’entre eux sera inséré dans une structure de dictionnaire sur laquelle les mots possibles seront consultés.
- recherche des mots: Une fois que le dictionnaire est disponible, le programme demandera à l’utilisateur la séquence des lettres d’analyser et de renvoyer tous les mots valides possibles pouvant être construits à partir de ces lettres, commandé par ordre alphabétique et groupé par la taille de la taille. plus haut à mineur.
Affaires que l’entrée / sortie dans le paradigme fonctionnel ne fait pas partie de l’ordre du jour qui est étudié le sujet, toutes les fonctions responsables de la lecture du dictionnaire d’un fichier ou de l Les affaires avec l’utilisateur seront programmées pour les étudiants. Dans cette déclaration, il y aura l’explication du fonctionnement desdites fonctions.
Déclaration de pratique
La pratique consiste à élaborer un programme de haskell qui charge un fichier texte de conspalabra valide et croit un dictionnaire . Une fois que cela est terminé, le programme demandera à l’utilisateur de différentes séquences de lettres et renvoyera les mots valides (ceux présents dans l’oncdictionnaire) qui peuvent être construits en fonction des lettres disponibles.
Exemple 1: Le programme cherche le programme Fichier de dictionnaire par mots (Dictionary.txt), crée le dictionnaire et attend que l’utilisateur entrait une séquence de lettres:
* Main > Liste de mots de Maincargo du Fichier dictionnaire.txt79517 Lire les mots
Entrez la séquence de lettres:
Exemple 2: Avec le dictionnaire déjà chargé déjà chargé, l’utilisateur entre la séquence de lettres « ACOS » et le programme renvoie tout le programme. mots du dictionnaire qui peuvent être construits en utilisant des lettres:
Nous pouvons voir le dictionnaire résultant graphiquement représenté dans une forme d’arborescence. Comme précédemment, les nœuds intermédiaires (à l’exception de la racine, représentés comme rn) sont le Unique qui connaissez des personnages. Et la concaténation des caractères qui forment le chemin de la racine accessible aux nœuds de feuilles (représentées comme wn) indique les mots présents dans le mental.
pour une meilleure compréhension de la structure de données à utiliser, nous Suggérez des étudiants qui exécutent une tournée de temps le dictionnaire illustré à la figure 1 pour vérifier exactement les onze mots indiqués dans la liste utilisée pour la créer.
2.2 Structure des modules de pratique
La pratique est divisée en deux modules, chacune dans un fichier indépendant dont le nom (y compris majuscule et minuscule) avec le nom du module et dont l’extension est .HS:
- Dictionnaire de module: dans cette Module, les fonctions de construction et d’accès au dictionnaire seront programmées. Il inclut également la définition du type de données de dictionnaire.
- Module principal: Ce module contient le programme principal et toutes les fonctions responsables de la chargement de la liste des mots et d’interagir avec l’utilisateur.
Étant donné qu’une étude plus profonde des modules de Haskell est en dehors du champ d’origine de laassignature, nous n’indiquerons que chaque module importe une série de modules nécessaires à leur fonctionnement. Dans notre pratique, le module principal importe (en plus du module de module) des modules supplémentaires pour pouvoir fonctionner avec la sortie, les fichiers et convertir toutes les lettres AMINISSUS. De plus, la liste des identifiants entre parenthèses qui accompagne l’anneau du module de dictionnaire représente les définitions de types et de fonctions que le ModuleExport.Toute autre définition sera considérée comme privée, ne sera accessible que par le module.
Figure 1: Dictionnaire représenté dans l’arborescence en forme d’arborescence façonnée
2.3 Type de données de dictionnaire (module de dictionnaire)
Dans cette section, nous allons introduire le type de données que nous allons utiliser pour se stocker dans la pratique. Il est défini dans la partie du module de dictionnaire qui fournit à Eleger enseignant. Comme nous l’avons vu dans la section précédente, un dictionnaire sera un arbre dans lequel les nœuds intermédiaires contiendront un caractère, tandis que les nœuds de feuilles nous donnent la formation de quels mots ils appartiennent au dictionnaire. Donc, la définition du type de dictionnaire:
Dictionnaire de données = rootnode | Letternode char | WordNode
IE, un dictionnaire est un dictionnaire de racine (nœud racine) contenant une liste de dictionnaires , Unletternode (lettre de nœud) contenant une liste de caractères de caractère et de dictionnaires, soit un nœud WordNode (noeud de mots) qui sera un nœud de feuille qui nous marquera que la concaténation de toutes les lettresConensens dans les nœuds de la racine (qui ne fait pas ne contient aucun) jusqu’au père du nœud de la feuille formulaire un mot valide du dictionnaire.
Ce type de données est ajouté à l’instance de la classe Afficher, pour pouvoir afficher le contenu d’un type de dictionnaire Élément et faciliter ainsi la tâche de programmer les fonctions Dictionnaire Decreies.
La représentation interne du dictionnaire de la figure 1 serait la suivante:
rootnode]]], le redeverode ‘c’ ], Letternode ‘S’, Letternode ‘C’], Letterde ‘O’]]]]]]]]]], letterde ‘O’]]]], letterde ‘s’]] ], Letternode ‘o’]]]]]]]
qui est un peu plus compliqué à lire que votre représentation graphique.
2.4 Programme principal (module principal)
Le module principal contient le programme principal, déjà prévu par l’équipe d’enseignement. Hayfunctions qui utilisent des monades et sont écrites à l’aide de la « notation de faire », qui est une notation pour faciliter la rédaction de la concaténation de fonctions monopdistes. Sans pénétrer trop. Prendre le fonctionnement des monades, nous expliquerons les types de données définis et que chaque fonction.
Types de données
- mots: représente une liste de mots. Nous utiliserons ce type pour faire référence à une liste de toutes les mêmes longueurs et arrangées par ordre alphabétique. .
- mots: représente une liste des mots. Nous allons utiliser ce type pour vous reporter à une liste de mots regroupés dans des listes de mots de longueur égale et arrangé par ordre alphabétique.
Fonction d’insertion
votre genre serait insertionItree :: string – > Dictionnaire – > Dictionnaire. Cette fonction est la une insérant un mot dans le dictionnaire mais a déjà pensé comme un arbre. Le premierparamètre devrait être Le reste du mot qui reste à insérer et le deuxième paramètre de l’arbre nodododel à partir duquel un autre point de repos doit être inséré.
fonction insertchild
de type insertchild :: Char – > – > – >. Dans le premierparamètre, il reçoit le premier caractère du reste du mot à insérer, le deuxième paramètre le reste du mot à insérer (sans ce premier caractère), le troisième paramètre une liste d’éléments du titring (qui sera le enfants d’un nœud). Renvoie la liste des enfants du nœud correctement modifié.
Cette fonction est responsable de la recherche de l’enfant du nœud actuel où l’insertion des caractères qui reste toujours du mot actuel sont poursuivies. Si l’enfant n’existe pas, la fonction lodéreuse créera. Une fois localisé (ou créé) le bon enfant, la fonction doit continuer le reste des caractères de mots de cet enfant. À ce stade, nous suggérons les étudiantsCreate « à la main » du dictionnaire représenté sur la figure 1 pour une meilleure compréhension du processus insérant des mots dans le dictionnaire.
2.6 requêtes au dictionnaire (module de dictionnaire)
Dans cette section, nous essaierons des consultations au dictionnaire. Notre objectif sera de programmer la recherche de la séquence qui reçoit une séquence de caractères et un dictionnaire. Il est renvoyé par la liste des scutrices, commandé par ordre alphabétique, qui figure dans Le dictionnaire et qui peut être converti avec les caractères de séquence.
Rechercher :: String – > Dictionnaire – >
Par exemple, si nous recherchons la séquence « Cascao » du dictionnaire représentées à la figure 1, nous devrions obtenir la liste des mots suivants:
Notez que « cas » et » Coucher de soleil « , présent dans le dictionnaire, ne peut-on pas être formé avec les lettres de la plasques, car elle ne contient que » S « (et » cas « a deux) et Un ‘O’ (et « Sundo » en a deux).
Comment allons-nous prendre la recherche?Nous allons supposer que nous avons déjà fait une route antérieure, cela nous a amené à un nœud d’arbre (ce qui n’est pas une feuille). Par conséquent, nous aurons des caractères de séquençage toujours non utilisés et le début d’un mot formé par les caractères présente le chemin de la racine du nœud actuel.
Nous analysons tous les enfants du nœud actuel:
- Si un enfant est un mot de mot, cela signifiera que le mot que nous avons déjà formé appartient au dictionnaire, avec lequel, il sera nécessaire de l’ajouter.
- Si un enfant est un letternode, il contiendra un personnage. Seulement si ce personnage appartient à la séquence non encore explorée (dans n’importe quelle position, pas nécessairement le premier), nous devons explorer de manière récursive cet enfant, l’ajout au mot déjà formé le caractère de la lettre et éliminer ledit caractère de la séquence toujours non explorée. .
Nous recommandons à nouveau que les étudiants investissent un temps dans l’exécution de ce gommage sur l’arborescence de la figure 1 pour la séquence « Cascao » et vérifiez donc les mots indiqués.
Comme dans la section précédente, la fonction de recherche nécessitera une série de fonctions (qui ne sera pas visible de l’extérieur du module). Les plus importants sont les lasdos suivants:
Fonction RechercheRee
Votre genre serait fouetterree :: string – > string – > Dictionnaire – >. Dans le premierparamètre, il reçoit les caractères de la séquence mais il n’utilise pas Deuxièmement, dans la seconde reçoit le mot qui a déjà été formé jusqu’à ce qu’il atteigne le nœud d’arbre reçu en tant que troisième paramètre.
Vous devez renvoyer tous les mots contenus dans le dictionnaire dont le début est le contenu Découvrez le paramètre et continuer à partir du nœud actuel (troisième paramètre) en utilisant uniquement des chandelets de séquence non encore explorés (premier paramètre).
Fonction de recherche de la fonction
searchschild :: String – > String – > Dictionnaire – >. La fonction ne reçoit toujours pas une séquence explorée, le début du mot déjà construit (basé sur la route utilisée pour atteindre ce nœud de la racine) et un nœud (fils du nœud actuellement exploré). C’est la fonction qui va être appliqué l’algorithme expliqué ci-dessus pour renvoyer la liste scutraire qui peut être formée avec le début déjà construit et avec les caractères qui ne sont pas encore utilisés.
problèmes sur la pratique
la réponse à ces questions est facultatif. Toutefois, si l’étudiant ne répond pas à ces questions, la qualification de la pratique ne peut atteindre 6 points que sur 10.
- (1’5 points). Supposons une mise en œuvre de la pratique dans une langue non déclarative (telle que Java, Pascal, C …). Commentaire Quels avantages et quels inconvénients je aurais devant la mise en œuvre de Haskell. Détendez ces avantages du point de vue de l’efficacité en ce qui concerne la programmation et l’exécution. Quel serait le point principal en faveur de la mise en œuvre dans les langues non déclaratives? Et la mise en œuvre dans HASKELLL?
- (1’5 points). Indiquez, avec vos mots, ce qui vous permet de gérer le prédicat non logique prédéfini, coupez (!), En Proll. Comment cet effet serait-il effectué en Java? Justifier votre réponse.
- (1 point). Pour les types de problèmes du problème défini dans HASKELLL (dans les deux modules), indiquez quels types de bâtiments de type ont été utilisés dans chaque cas (voir le chapitre 5 du livre du sujet).
Documentation à livrer
Chaque élève doit fournir la documentation suivante à son tuteur pratique: – code source dans HASKELL qui résout le problème posé. Pour ce faire, les fichiers lyriques.hs et dictionary.hs doivent être livrés, avec les fonctions décrites dans cette déclaration, ainsi que toutes les fonctions auxiliaires nécessaires. – une mémoire avec: – une petite description des fonctions planifiées. – les réponses aux problèmes sur la pratique.