Discussion :

[Dark3]

Bonsoir,
j'essaye comme le titre l'indique de supprimer les doublons dans une liste de pairs.
J'ai essayé sans trop de succés.
Merci de votre aide.
Dark3

[gorgonite]

si tu montrais ton code, on essaierait de le corriger... mais on ne va pas te le faire


l'algo simple serait de cette forme :

Code :

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

1
2
3
4
5
6
7
8
9
10
 
L = liste
res = Liste vide
tant que L non vide faire
    a = tete de L
    si a n'appartient pas à queue de L 
    alors ajoute a dans res
    L = queue de L
fait
renvoyer res

bien entendu le traitement doit être récursif avec une filtrage... mais c'est à toi de le coder

[Dark3]

Bonsoir,
oui effectivement je n'avais pas mis mon code dsl :

Code :

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

1
2
3
4
 
let rec enleve l = match l with
  []->[]
| (a,b)::(c,d)::l' -> if a=c && b=d then (a,b)::(enleve l') else (a,b)::(c,d)::(enleve l');;

Dans ce code il manque le fait de tester les elements avec chaque autre pair dans la liste, c'est à dire que si les elements identiques ne sont pas consécutifs, ma fonction ne marche pas.
Je prefererai avoir une solution fonctionnel.
Merci de votre aide.
Dark3

[gorgonite]

Je prefererai avoir une solution fonctionnel.

j'ai fait exprès de ne pas te donner la version fonctionnelle, ce qui aurait été équivalent à te donner le programme déjà coder... traduis toi-même


nb: on se moque du type de l'élément, ocaml réussira à déterminer l'égalité... donc fait comme si on avait une liste d'éléments d'un type quelconque

[Dark3]

Je comprend bien l'algo, mais je ne saisis pas comment tester l'appartenance d'un element dans la liste de retour si celle si n'est pas déclaré et n'est créer qu'avec la recursivité (a:enleve l))
Merci de ton aide en tout cas (c bientot l'exam de caml :/)
Dark3

[gorgonite]

Code :

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

1
2
3
4
5
6
7
 
let rec appartient e l =
   match l with
      [] -> false
     |a::_ where a=e -> true
     |_::q -> appartient e q
;;

[gorgonite]

étant donné que ce n'est qu'un bloc utile, je te le donne... même si avec un peu de reflexion, tu aurais du y arriver (ou alors tu as de gros soucis à te faire pour ton exam !!!)

Code :

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

1
2
3
4
5
6
7
 
let rec appartient e l =
   match l with
      [] -> false
     |a::_ when a=e -> true
     |_::q -> appartient e q
;;

[Dark3]

Non je pense que tu n'as pas compris ce que j'ai voulu dire.
Cette fonction appartient ne me pose pas de problème.
Ce que je ne comprend pas c'est comment peut on tester l'appartenance d'un element dans une liste sans définir de liste auxiliaire, et que la liste de retour n'est défini qu'avec la récursivité.
Ou alors dans ce cas on est obligé de le faire comme celà.
Pour ma part j'aurai penser à l'utilisation d'un List.map avec une fonction à appliquer bien choisi à chaque element de la liste, mais je manque de pratique avec ce genre de fonctions.
Dark3

[gorgonite]

Code :

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

1
2
3
4
5
let rec elimine_doublon l =
   match l with
      [] -> []
     |a::q -> if (appartient a q) then elimine_doublon q else a::(elimine_doublon q)
;;

je fais avoir du mal à croire que tu aies cherché...


maintenant, ai-je glissé une erreur dans le code ? fais-nous la preuve de la fonction... juste pour t'en assurer (et vérifier que tu as compris )

[Dark3]

Je trouve que tu n'as pas beaucoup de tolérance envers moi, mais je te remercie quand même.
Je ne te demandais pas la solution mais juste un peu d'aide comme ce forum nous le propose quand on a un souci.
Bref, sans doute un malentendu.
Dark3

[gorgonite]

Je trouve que tu n'as pas beaucoup de tolérance envers moi, mais je te remercie quand même.

sans doute, il est tard et j'ai eu une très mauvaise semaine...

Je ne te demandais pas la solution mais juste un peu d'aide comme ce forum nous le propose quand on a un souci.

j'ai bien compris que tu cherchais de l'aide. d'ailleurs, tu avais commencé à coder quelque chose... je t'avais l'algo itératif qui permettait de trouver le résultat (le récursif aurait été une traduction du caml en pseudo-code), je voyais mal comment t'aider plus


maintenant, reprends cette fonction et fais nous les preuves de terminaison et de correction... ça t'aidera à en cerner les détails (j"attends la réponse dans 1 heure )

[Dark3]

Et bien on fait pas vraiment ça en cours donc je sais pas vraiment ce que tu attends.
Pour la terminaison :
Etant donné les differents matching il est clair que l'on va parcourir toute la liste donné en argument et on arrivera à la liste vide qui renvoi quelque chose.
Pour la correction je ne sais pas ce que ce terme signifie en algorithmie.
Dark3

[gorgonite]

Pour la terminaison :
Etant donné les differents matching il est clair que l'on va parcourir toute la liste donné en argument et on arrivera à la liste vide qui renvoi quelque chose.

pas mal, c'est l'idée... j'aurais préféré que tu dises que :
1) la longueur de l'argument passé en paramètre lors des appels récursifs est strictement décroissante.
2) toute suite d'entiers naturels strictement décroissante converge (car strictement monotone et minorée par 0).
3) la limite de la suite est 0 (à faire)
4) 0 est le cas de terminaison de la fonction, donc ça termine...

Pour la correction je ne sais pas ce que ce terme signifie en algorithmie.
Dark3

je veux que tu prouves que le résultat renvoyé est bien celui qu'on attend

[Dark3]

Pour la correction :
Si la liste est vide on renvoie la liste vide, c'est bien le resultat attendu, sinon :
On recherche si l'element appartient au reste de la liste si c'est le cas on continue sur le reste de la liste sans rajouter d'élement, ce qui va supprimer le doublon au fur et à mesure sinon on rajouter l'element à la liste de retour.
Dark3

[Garulfo]

Je trouve que tu n'as pas beaucoup de tolérance envers moi, mais je te remercie quand même.
[...]
Dark3

Moi je trouve qu'il fait un excellent travail comme aide.

Tu veux venir icite pour être assistant ??

[gorgonite]

Moi je trouve qu'il fait un excellent travail comme aide.

il était tard, et j'étais énervé... donc j'ai répondu un peu vite, et donné la solution au bout de quelques minutes de reflexion. j'aurais du lui en faire baver un peu plus

Tu veux venir icite pour être assistant ??

gni ?

[alex_pi]

Code :

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

1
2
3
4
5
let rec elimine_doublon l =
   match l with
      [] -> []
     |a::q -> if (appartient a q) then elimine_doublon q else a::(elimine_doublon q)
;;

Si je puis me permettre, cette fonction à le gros désavantage de ne pas être "tail-recursive" (c'est à dire de ne renvoyer directement le résultat de l'appel récursif) ce qui est généralement considéré comme mauvais lorsqu'on explore une structure de taille arbitraire. En effet, on peut se retrouver avec un stack-overflow alors qu'on ne manque pas de mémoire. La version suivante est peut être un tout petit peu plus lente, mais tail recursive :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
let rec contient e = function
  | [] -> false
  | t::q when t = e -> true
  | _::q -> contient e q
 
let elimine_doublon l = 
  let rec aux acc = function
    | [] -> List.rev acc
    | t::q when contient t acc -> aux acc q
    | t::q -> aux (t::acc) q in
  aux [] l

(J'appelle contient sur l'accumulateur, car dans le cas où la liste contient effectivement des répétitions, il est plus petit que la liste elle même)

[gorgonite]

Si je puis me permettre, cette fonction à le gros désavantage de ne pas être "tail-recursive" (c'est à dire de ne renvoyer directement le résultat de l'appel récursif) ce qui est généralement considéré comme mauvais lorsqu'on explore une structure de taille arbitraire. En effet, on peut se retrouver avec un stack-overflow alors qu'on ne manque pas de mémoire.

avec les optimisations d'un compilateur non... suffit qu'elle soit primitive

l'écriture telle que tu le fais sera en revanche bien plus performant dans la boucle d'interprétation

[alex_pi]

avec les optimisations d'un compilateur non... suffit qu'elle soit primitive

l'écriture telle que tu le fais sera en revanche bien plus performant dans la boucle d'interprétation

Euh... non Test fait avec

Code :

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

1
2
3
4
 
let rec recopie = function
  | [] -> []
  | t::q -> t::(recopie q)

versus

Code :

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

1
2
3
4
5
6
 
let rec recopie_tail l = 
  let rec aux acc = function
    | [] -> List.rev acc
    | t::q -> aux (t::acc) q in
    aux [] l

Pour une liste de 2000000 éléments, la version non tail recursive (compilée avec ocamlopt) lance Fatal error: exception Stack_overflow alors que la version tail recursive passe sans soucis

[gorgonite]

Pour une liste de 2000000 éléments, la version non tail recursive (compilée avec ocamlopt) lance Fatal error: exception Stack_overflow alors que la version tail recursive passe sans soucis

pas cool... pourtant l'optimisation existe belle et bien, j'avais pensé qu'elle serait déjà dans ocaml