Syndrome terminal blanc

Bonjour,

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

Cependant je bloque sur une partie de ce projet,

VOICI

Code:

---

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:

---

substituer :: Substi -> Terme -> Terme

---

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

Code:

---

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

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

Merci de votre intérêt

Voila

Code:

---

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

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:

---

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:

---

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

---

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

Code:

---

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

---

est strictement équivalente à l'expression :

Code:

---

NOM term xs

---

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

Code:

---

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:

---

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.

Merci pour votre aide et vos conseils.

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

Utilise des balises de code !

-----

Code:

---

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:

---

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:

---

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:

---

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:

---

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:

---

soustermes :: [Terme]

---

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

Code:

---

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:

---

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...

merci beaucoup pour votre aide