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

[Ptival]

Utilise des balises de code !

-----

Code :

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

1
2
3
 
Substituer :: Substi -> Terme -> Terme
Substituer [] term = term

Déjà c'est bizarre qu'on te laisse nommer une fonction avec une majuscule... Sinon ça semble bien.

-----

Code :

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

1
2
3
 
Substituer substs (NOM term soustermes) = NOM term ( substitut substs soustermes)
  where substitut substs soustermes = [Substituer substs term | term <- soustermes]

Cette partie du code, bien que (peut-être) correcte, est vraiment très loin de ce qu'on écrirait. D'une part, tu n'as pas besoin de passer des paramètres aussi triviaux à une fonction définie localement dans un where, puisqu'elle a dans sa portée les variables substs et soustermes. C'est-à-dire que ce code devrait fonctionner pareil :

Code :

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

1
2
3
 
Substituer substs (NOM term soustermes) = NOM term substitution
  where substitution = [Substituer substs term | term <- soustermes] -- ici, substs, term et soustermes sont visibles

Ensuite, il faut remarquer que tu essaies d'appliquer une fonction à tous les éléments d'une liste. C'est un motif récurrent en programmation, qui est capturé par la fonction d'ordre supérieur map :

Code :

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

map :: (a -> b) -> [a] -> [b]

Le type dévoile bien la fonction : elle prend une fonction de a vers b, une liste de a, et retourne une liste de b. Pour ce faire, on se doute bien qu'elle applique la fonction sur chaque élément !

On aurait donc écrit :

Code :

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

1
2
 
Substituer substs (NOM term soustermes) = NOM term (map (Substituer substs) soustermes)

Une remarque ici : la fonction que je mappe n'est pas "Substituer", mais bien "Substituer substs" ! En effet, puisqu'on veut mapper sur la liste :

Code :

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

soustermes :: [Terme]

Et qu'on veut obtenir en résultat une liste de Terme, il faut une fonction de type Terme -> Terme.

Code :

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

1
2
3
4
5
 
Substituer :: Substi -> Terme -> Terme
substs :: Substi
impliquent
Substituer substs :: Terme -> Terme

Tu peux lire "je mappe la fonction (Substituer substs) sur la liste soustermes", où "mapper f sur l" signifie "appliquer f sur chacun des éléments de l".

Ceci étant, je ne suis pas sûr que tu n'omettes pas un détail, cf. plus bas [1]

-----

Code :

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

1
2
3
4
5
 
Substituer ((sNom, sTerme):substs) (VARIABLE var) =
  if sNom == var
  then Substituer substs sTerme
  else Substituer substs (VARIABLE var)

Je me permets d'indenter ton code, je ne supporte pas les lignes à rallonge, et tu ferais bien d'en faire autant. Plus lisible ainsi, non ?
Attention ceci dit, une mauvaise indentation rendra Haskell grognon.

Dans le cas où sNom == var, tu remplaces (VARIABLE var) par sTerme, et cela semble correct, par contre, tu continues à substituer le reste des substitutions dans sTerme, es-tu sûr de vouloir faire ça ? Est-ce que c'est logique dans ton projet ?

Si tu t'es trompé, alors on pourra retravailler ce bout de code (qui ne serait alors qu'un map). Si tu veux vraiment faire ce que tu fais là, alors on peut réécrire ça comme un fold je crois. Mais pose-toi déjà cette question.

-----

[1] :
Que signifie ton "NOM Terme [Terme]" ? Si c'est censé représenter une abstraction au sens lambda-calcul, déjà ça a une drôle de tête, et ensuite au niveau de la substitution il faudra faire du travail en plus pour respecter les portées des noms. Enfin bon, ce serait bien d'expliquer ce que tu fais que je ne te dise pas de bêtises...

[marincuveur]

merci beaucoup pour votre aide