Discussion :

[marincuveur]

Bonjour,

je suis étudiant et je dois réaliser un projet en Haskell.

Cependant je bloque sur une partie de ce projet,

VOICI

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
data Terme = VARIABLE String | NOM String [Terme]
             deriving (Eq,Show)
type Substi = [(String,Terme)]

Et je dois écrire une fonction qui effectue la substitution d'un terme

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

substituer :: Substi -> Terme -> Terme

Idéalement, cette fct devrait faire qqch comme ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
*Main> substituer [("var",NOM "l" [])] (NOM "m" [VARIABLE "var"]) 
           donnera (NOM "m" [NOM "l" []])

Cependant, après plusieurs tentatives et pas mal d'heures passées à bosser sur ce problème, je n'ai pas réussi à produire une fonction réalisant la spécification, et je me retrouve à court d'idées.

Pourriez-vous, s'il vous plait, m'aider, m'indiquer une piste, me donner un conseil ou une idée, n'importe quoi qui m'aide à avancer?

Merci d'avoir lu ma requête, et encore merci de la prendre en considération

Bien à vous, marincuveur

[Ptival]

Peux-tu poster ton meilleur essai qu'on ait une idée de ce qui ne va pas ?

[marincuveur]

Merci de votre intérêt

Voila

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
termToString :: Terme -> String
termToString (VARIABLE var) = var
termToString (NOM term []) = term
termToString (NOM term (x:xs)) = term
 
 
substituer :: Substi -> Terme -> Terme
substituer [] (NOM term xs) = if xs == [] then (NOM term []) else (NOM term xs)
--substituer [(balise, (NOM newTerm (ys)) )] (NOM term xs) =  if balise == term then (NOM newTerm (ys)) else error "error"
substituer [(balise, (NOM newTerm (y:ys)) )] (NOM term (x:xs)) =  if balise == term then (NOM newTerm (y:ys)) else substituer [(balise, (NOM newTerm (y:ys)) )] (NOM (termToString x) xs)

Bien à vous, Marincuveur

[Ptival]

Pour termToString, je ne sais pas ce que c'est censé faire, mais je remarque que tu n'affiches pas les sous-termes d'un nom, c'est voulu ?

Si oui, alors tu pourrais te contenter de :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
termToString :: Terme -> String
termToString (VARIABLE var) = var
termToString (NOM term _) = term

Sinon, il faut appeler récursivement termToString sur la liste d'une façon ou d'une autre.

---

Quant à substituer, là encore je ne suis pas certain de ce que tu veux faire, mais quelques remarques :

- tu ne traites pas tous les cas :

• tu ne traites que la substitution vide et les substitutions avec un seul élément dans la liste.
• tu ne traites pas les substitutions pour un terme de la forme "VARIABLE".
• même pour une substitution à un élément, tu ne traites pas les termes de la forme "NOM" dont la liste est vide.

Egalement, tu déconstruis y:ys pour ne jamais utiliser y et ys... Es-tu sûr que c'est ce que tu veux faire ? (Quid de la liste vide ?)

---

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

substituer [] (NOM term xs) = if xs == [] then (NOM term []) else (NOM term xs)

Cette ligne est affreusement compliquée pour rien ! L'expression :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

if xs == [] then (NOM term []) else (NOM term xs)

est strictement équivalente à l'expression :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

NOM term xs

De plus, je suis presque sûr que ce que tu veux c'est encore plus général :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

substituer [] t = t

---

Tu devrais donc repartir sur un schéma exhaustif, et remplir les cas ou les couper en deux si besoin seulement :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
substituer :: Substi -> Terme -> Terme
substituer [] t = error "TODO1"
substituer [(sNom, sTerme):substs] (NOM terme soustermes) = error "TODO2"
substituer [(sNom, sTerme):substs] (VARIABLE nom) = error "TODO3"

Pour TODO1, la réponse n'est pas compliquée... si tu as lu mon post.

Pour TODO2, a priori, tu ne vas pas toucher à NOM et à terme, et tu vas appliquer les substitutions à tous les éléments de la liste soustermes. J'espère que tu as entendu parler de fonctions comme map.

Pour TODO3, tu vas devoir tenter d'appliquer, une à une, toutes les substitutions de la liste. C'est à dire que tu vas chercher à appliquer la subsitution (sNom, sTerme) si nom == sNom, et tu vas essayer de substituer substs (le reste des substitutions à effectuer) dans le résultat de ce premier calcul.

Je crois que tu n'auras pas besoin de cas en plus que ceux que j'ai mis là. Les cas 1 et 2 devraient être faciles. Le cas 3 sera récursif.

---

Note au passage que l'ordre d'application des substitutions peut avoir de l'importance, il faudrait donc savoir si tu commences par appliquer (sNom, sTerme), puis tu traites substs (le reste); ou si tu appliques d'abord le reste, puis en dernier la tête de liste des substitutions.

[marincuveur]

Merci pour votre aide et vos conseils.

[marincuveur]

voila,

après avoir passé ces derniers jours à me documenter et à travailler sur ce (qui est pour moi un vrai casse tête) problème, voici le résultat :

Substituer :: Substi -> Terme -> Terme
Substituer [] term = term
Substituer substs (NOM term soustermes) = NOM term ( substitut substs soustermes)
where substitut substs soustermes = [Substituer substs term | term <- soustermes]
Substituer ((sNom, sTerme):substs) (VARIABLE var) = if sNom == var then Substituer substs sTerme else Substituer substs (VARIABLE var)

ca à l'air de fonctionner...du moins jusque là car je ne l'ai pas testé exhaustivement(ca pique les yeux ces termes)
Cependant, je me demandais comment j'aurais pu utiliser des fonctions comme map ou foldl,... pour arriver au même résultat...
J'avais essayé cette approche au départ mais je n'arrivais à rien.

Pourriez vous, s'il vous plait, m'expliquer?

En vous remerciant d'avance,

Bien à vous, Marincuveur

[marincuveur]

merci beaucoup pour votre aide