[Ocaml] Eliminer les doublons dans une ('a * 'b)list

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

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:

---

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 ;)

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

Code:

---

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

Citation:

---

Envoyé par Dark3

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

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

Code:

---

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

---

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

---

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

---

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

Code:

---

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é... :roll:


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 ;))

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

Citation:

---

Envoyé par Dark3

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

Citation:

---

Envoyé par Dark3

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 ;))

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

Citation:

---

Envoyé par Dark3

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

Citation:

---

Envoyé par Dark3

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 ;)

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

Citation:

---

Envoyé par Dark3

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

Citation:

---

Envoyé par Garulfo

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 ;)

Citation:

---

Envoyé par Garulfo

Tu veux venir icite pour être assistant ??

---

gni 8O ?

Citation:

---

Envoyé par gorgonite

Code:

---

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:

---

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)

Citation:

---

Envoyé par alex_pi

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

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

Citation:

---

Envoyé par gorgonite

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

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:

---

1 2 3 4

let rec recopie = function | [] -> [] | t::q -> t::(recopie q)

---

versus

Code:

---

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

Citation:

---

Envoyé par alex_pi

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