Discussion :

[gomisse]

le type liste defini par :

Code :

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

   type  'a liste= Vide|Cons of 'a*'a liste;;

Je souhaite faire un tri par fusion, selection et tri rapide:

Code :

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

1
2
3
4
let rec insert elt liste  = match liste with 
    |Vide-> [elt]
    |Cons(a,l) -> if elt<a then elt::a::l
                  else a::(insert_ala_pos elt  l );;

Error: This expression has type 'a liste
       but an expression was expected of type 'a list

Code :

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

1
2
3
4
5
6
let rec tri_fusion l1 =match l1 with 
        |Vide -> Vide
        |Cons(a,l)-> insert a (tri_fusion l)
        and insert elt l2 = match l2 with 
        |Vide -> Vide
        |Cons(a1,l) ->if elt<a1 then elt::l2 else a1:: insert elt l;;

Erreur :

Error: The variant type liste has no constructor ::
# 

Je souhaite trier ma liste polymorphe , Merci d'y contribuer ?

[SpiceGuid]

D'une part :

• [] et :: sont des constructeurs pour le type prédéfini 'a list
• Vide et Cons sont des constructeurs pour le type utilisateur 'a liste

Ces deux types, bien que similaires, sont considérés comme totalement différents.

D'autre part tu n'es pas au bout de ta peine car :

• le premier extrait de code ressemble à une insertion mais ne fait pas de tri par insertion
• le second extrait de code ne ressemble en rien à un tri fusion

[gomisse]

Comment faire un tri par insertion et fusion en ocaml ? avec le type liste definie par :

Code :

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

 type a' liste= Vide|Cons 'a*'a liste ;;

[SpiceGuid]

• Pour le tri par insertion il te faut d'abord une fonction d'insertion d'un élément dans une liste triée
• Pour le tri par fusion il te faut une fonction qui fusionne deux listes triées en une seule liste triée

[gomisse]

Merci pour ces reponses .
est il possible que tu me fasse une partie du code ( tri par insertion avec le type polymorphe)?

[gomisse]

type 'a liste= Vide|Cons of 'a*'a liste;;

Code :

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

1
2
3
let rec insert_ e l = match l with 
  |Vide -> Cons(e,Vide)
  |Cons(b,l)-> if e<b then Cons(e,Cons(b,l)) else Cons(b,(insert_ e l));;

Error: Syntax error

[cvanaret]

Non non, ça fonctionne très bien.

[SpiceGuid]

Bravo

Le squelette de la fonction de fusion de 2 listes triées (pointillés à compléter) :

Code OCaml :

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

1
2
3
4
5
6
7
let rec merge la lb =
   match la,lb with
   | _,Vide -> la   
   | Vide,_ -> lb
   | Cons(ha,ta),Cons(hb,tb) -> 
      if ha < hb then ...
      else ...

Edit: cette fonction termine toujours parce que la fonction List.length la + List.length lb est strictement décroissante.

[gomisse]

Trie fusion

Code :

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

1
2
3
4
5
6
7
8
let rec merge la lb =
   match la,lb with
   | _,Vide -> la   
   | Vide,_ -> lb
   | Cons(ha,ta),Cons(hb,tb) -> 
      if ha < hb then Cons(ha,(merge ta lb))
      else Cons(hb, ( merge ta lb));;  
;;

#

[gomisse]

Code :

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

1
2
3
4
5
 
let rec divise_list l = function 
  |Vide -> Vide, Vide
  |Cons(a,Vide)-> Cons(a,Vide),Vide
  |Cons(b,Cons(a1,l))-> let ( l1,l2)= divise_list l in Cons(b,l1),Cons(a1,l2);;

Characters 130-143:
|Cons(b,Cons(a1,l))-> let ( l1,l2)= divise_list l in Cons(b,l1),Cons(a1,l2);;
^^^^^^^^^^^^^
Error: This expression has type 'a liste -> 'a liste * 'b liste
but an expression was expected of type 'c * 'd


pas d erreur:

Code :

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

1
2
3
4
5
6
7
8
9
 
let rec fusion la lb =
   match la,lb with
   | _,Vide -> la   
   | Vide,_ -> lb
   | Cons(ha,ta),Cons(hb,tb) -> 
      if ha < hb then Cons(ha,(fusion ta lb))
      else Cons(hb, (fusion ta lb));;  
;;

Characters 62-67:
|Cons(a,l) -> begin
^^^^^
Syntax error: 'end' expected, the highlighted 'begin' might be unmatched

Code :

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

1
2
3
4
5
6
let rec tri_fusion = function
	 |Vide -> Vide
	 |Cons(a,l) -> begin  
	   let  (liste1,liste2)= divise_list l in 
           fusion (tri_fusion liste1) (tri_fusion liste2)
;;

[SpiceGuid]

Vocabulaire
Un trie est une structure de données arborescente (et d'ailleurs on peut les fusionner).
Ce qui nous occupe ici c'est plus simplement un tri, ranger dans l'ordre les éléments d'un (multi-)ensemble

merge
La ligne 7 est incorrecte car l'élément hb est présent 2 fois dans la liste renvoyée.

divise_list
C'est correct.
Il suffit soit d'effacer l soit de remplacer function par match l with.

tri_fusion
Pas besoin de begin.
Que devient a
Sinon c'est presque correct : que se passe-t-il avec tri_fusion (Cons(1,Vide))

[gomisse]

a doit etre concatené à l'une de liste : liste1 ou liste2. mais :

Error: This expression has type 'a list liste
but an expression was expected of type 'a list
#

Code :

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

1
2
3
4
5
6
let rec tri_fusion = function
	 Vide -> Vide
         |Cons(a1,Vide)->Cons(a1,Vide) 
	 |Cons(a,l) -> let  (liste1,liste2)= divise_list l in 
          (fusion (a@(tri_fusion liste1)) (tri_fusion liste2))
;;

[SpiceGuid]

Corrige d'abord fusion à la ligne 7 qui comporte deux erreurs :

• hb est présent une seconde fois dans la liste renvoyée, par l'intermédiaire de lb.
• ha est absent de la liste renvoyée.

Après je t'invite à réfléchir sur tri_fusion :

Code OCaml :

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

1
2
3
4
5
let rec tri_fusion = function
   | Vide -> Vide
   | Cons(a,Vide) -> Cons(a,Vide)
   | l -> let la,lb = divise_list l in 
          fusion (tri_fusion la) (tri_fusion lb)

[gomisse]

correction de fusion .

Code :

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

1
2
3
4
5
6
7
 
let rec fusion la lb =match la,lb with
   | _,Vide -> la   
   | Vide,_ -> lb
   | Cons(ha,ta),Cons(hb,tb) -> 
      if ha < hb then Cons(ha,(fusion ta tb))
      else Cons(hb, (fusion ta tb));;

[SpiceGuid]

Code OCaml :

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

1
2
3
4
5
6
7
let rec fusion la lb =
   match la,lb with
   | _,Vide -> la   
   | Vide,_ -> lb
   | Cons(ha,ta),Cons(hb,tb) -> 
      if ha < hb then Cons(ha,(fusion ta lb))
      else Cons(hb,(fusion la tb))

[gomisse]

Merci pour votre aide .