Syndrome terminal blanc [Résolu]

[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 :

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

[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 :

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 :

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.

[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 :

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

[marincuveur]

merci beaucoup pour votre aide